On the structure and values of betweenness centrality in dense betweenness-uniform graphs

Authors: B. Ghanbari, David Hartman, V. Jelínek, Aneta Pokorná, R. Šámal, P. Valtr
Publication year: 2023
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications
Projects: Symmetries of brain connectivity
Bibliographic citation: GHANBARI, B., HARTMAN, David, JELÍNEK, V., POKORNÁ, Aneta, ŠÁMAL, R., VALTR, P. On the structure and values of betweenness centrality in dense betweenness-uniform graphs. In: KRÁĽ, D., NEŠETŘIL, J., eds. EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. Brno: MUNI Press, 2023, S. 478-484. E-ISSN 2788-3116
Dostupné z: doi:10.5817/CZ.MUNI.EUROCOMB23-066.
DOI: 10.5817/CZ.MUNI.EUROCOMB23-066
ID: 573762
Online record: View online record

Abstract

Betweenness centrality is a network centrality measure based on the amount of shortest paths passing through a given vertex. A graph is betweenness-uniform (BUG)if all vertices have an equal value of betweenness centrality. In this contribution, we focus on betweenness-uniform graphs with betweenness centrality below one. We disprove a conjecture about the existence of a BUG with betweenness value α for any rational numberαfrom the interval (3/4,∞) by showing that only very few betweenness centrality values below 6/7 are attained for at least one BUG. Furthermore, among graphs with diameter at least three, there are no betweenness-uniform graphs with a betweenness centrality smaller than one. In graphs of smaller diameter, the same can be shown under a uniformity condition on the components of the complement.