Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
betweenness centrality; betweenness-uniform graph
betweenness centrality; betweenness-uniform graph
Summary:
The betweenness centrality of a vertex of a graph is the fraction of shortest paths between all pairs of vertices passing through that vertex. In this paper, we study properties and constructions of graphs whose vertices have the same value of betweenness centrality (betweenness-uniform graphs); we show that this property holds for distance-regular graphs (which include strongly regular graphs) and various graphs obtained by graph cloning and local join operation. In addition, we show that, for sufficiently large $n$, there are superpolynomially many betweenness-uniform graphs on $n$ vertices, and explore the structure of betweenness-uniform graphs having a universal or sub-universal vertex.
References:
[1] Comellas, F., Gago, S.: Spectral bounds for the betweenness of a graph. Linear Algebra Appl. 423 (2007), 74-80. MR 2312324 | Zbl 1114.05058
[2] Diestel, R.: Graph Theory. Transl. from the German. Graduate Texts in Mathematics 173. Springer New York (1997). MR 1448665
[3] Everett, M. G., Borgatti, S. P.: Ego network betweenness. Social Networks 27 (2005), 31-38. DOI 10.1016/j.socnet.2004.11.007
[4] Everett, M. G., Sinclair, P., Dankelmann, P.: Some centrality results---new and old. J. Math. Sociol. 28 (2004), 215-227. DOI 10.1080/00222500490516671 | Zbl 1134.91576
[5] Freeman, L. C.: A set of measures of centrality based on betweenness. Sociometry 40 (1977), 35-41. DOI 10.2307/3033543
[6] Gago, S.: Métodos Espectrales y Nuevas Medidas Modelos y Parámetros en Grafos Pequeño-mundo Invariantes de escala. Ph.D. Thesis Univ. Politècnica de Catalunya, Barcelona (2006), Spanish.
[7] Gago, S., Hurajová, J., Madaras, T.: Notes on the betweenness centrality of a graph. Math. Slovaca 62 (2012), 1-12. DOI 10.2478/s12175-011-0065-7 | MR 2886647
[8] Gethner, E., Sulanke, T.: Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs. Graphs Comb. 25 (2009), 197-217. DOI 10.1007/s00373-008-0833-5 | MR 2511878 | Zbl 1223.05195
[9] Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004). MR 2282139
[10] Phelps, K. T.: Latin square graphs and their automorphism groups. Ars Comb. 7 (1979), 273-299. MR 0539719 | Zbl 0421.05036
[11] Sinclair, P.: Betweenness centralization for bipartite graphs. J. Math. Sociol. 29 (2005), 25-31. DOI 10.1080/00222500590889730 | Zbl 1079.05517
Search
Partner of
