Uniform edge betweenness centrality
Abstract
The edge betweenness centrality of an edge is loosely defined as the fraction of shortest paths between all pairs of vertices passing through that edge. In this paper, we investigate graphs where the edge betweenness centrality of edges is uniform. It is clear that if a graph G is edge-transitive (its automorphism group acts transitively on its edges) then G has uniform edge betweenness centrality. However this sufficient condition is not necessary. Graphs that are not edge-transitive but have uniform edge betweenness centrality appear to be very rare. Of the over 11.9 million connected graphs on up to ten vertices, there are only four graphs that are not edge-transitive but have uniform edge betweenness centrality. Despite this rarity among small graphs, we present methods for creating infinite classes of graphs with this unusual combination of properties.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.2.7
References
L. D. Andersen, S. Ding, G. Sabidussi, and P. D. Vestergaard, Edge Orbits and Edge-Deleted Subgraphs, Graphs and Combinatorics 8, (1992), 31-44.
J. M. Anthonisse, The Rush in a Directed Graph, Technical report, Amsterdam: University of Amsterdam Mathematical Centre, (1971).
S. P. Borgatti, M. G. Everett, and J. C. Johnson, Analyzing social networks. SAGE Publications Limited, (2013).
U. Brandes, S. Borgatti, L. Freeman, Maintaining the Duality of Closeness and Betweenness Centrality, Social Networks, 44 (2016), 153--159.
E. Bullmore and O. Sporns, Complex brain networks: graph theoretical analysis of structural and functional systems, Nature 10 (2009), 186-196.
L. Freeman, A set of measures of centrality based upon betweenness, Sociometry 40 (1977), 35--41.
J. Coronicova Hurajova and T. Madaras, The Edge Betweenness Centrality - Theory and Applications, JIAS 5 Cslo 1, (2015), 20-29.
L. Freeman, Centrality in social networks conceptual clarification, Social Networks, 1 (1978/79) 215--239.
L. C. Freeman, S. P. Borgatti, and D. R. White, Centrality in valued graphs: A measure of betweenness based on network flow, Social Networks}, 13 No 2, (1991), 141--154.
F. Comellas and S. Gago, Spectral bounds for the betweenness of a graph, Linear Algebra and its Applications 423 (2007), 74--80.
S. Gago, J. Coronicova Hurajova , and T. Madaras, Betweenness centrality in graphs. Chapter 7: Quantitative graph theory, Discrete Math. Appl., (Boca Raton), CRC Press, Boca Raton, FL, (2015), 233--257.
S.Gago, J. Coronicova Hurajova, and T. Madaras, On Betweenness Uniform Graphs, Czechoslovak Mathematical Journal, 63 (138) (2013), 629--642.
S. Gago, J. Hurajova, and T. Madaras, Notes on the betweenness centrality of a graph, (English summary) Mathematica Slovaca 62 (2012), 1--12.
D. Gleich, https://www.mathworks.com/matlabcentral/fileexchange/10922-matlabbgl.
R. Grassi, R. Scapellato, S. Stefani, and A. Torriero, Networks, Topology and Dynamics, Springer (Berlin), (2009), 161--175.
http://users.cecs.anu.edu.au/symbol{126}bdm/data/graphs.html.
S. Miklavic, P. Potocnik, Distance-regular circulants, European Journal of Combinatorics, 24 (2003), 777-784.
S. Nicoloso, U. Pietropaoli, Isomorphism Testing for Circulant Graphs C_{n}(a,b), Utilitas Mathematica, 87 (2012), 165.
D. Schoch and U. Brandes, Re-conceptualizing centrality in social networks, Euro. J. Applied Mathematics 27 (2016), 971--985.
S. Wilson and P. Potocnik, Recipes for Edge-Transitive Tetravalent Graphs, arXiv preprint arXiv:1608.04158 (2016).
D. R. White and S. P. Borgatti. Betweenness centrality measures for directed graphs, Social Networks, 16 No. 4, (1994), 335--346.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.