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

EUROCOMB’23

Babak Ghanbari David Hartman Vít Jelínek Aneta Pokorná Robert Šámal Pavel Valtr

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-066

PDF
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 $\alpha$ for any rational number $\alpha$ from the interval $(\frac{3}{4}, \infty)$ by showing that only very few betweenness centrality values below $\frac{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.

Pages:
478–484
References

J. C. Birk, C. J. Bresloff, and R. Darbali-Zamora. Electric Grid Vulnerability Analysis to Identify Communities Prone to Wildfres. IEEE Access, 2023.

C. C. Chou, C.-S. Teng, and H. H. Tung. How do alliances trade arms? Political alliance networks and global arms transfers. PLOS ONE , 18(3): 1-14, 2023.
https://doi.org/10.1371/journal.pone.0282456

F. Comellas and S. Gago. Spectral bounds for the betweenness of a graph. Linear Algebra and its Applications , 423(1): 74-80, 2007. Special Issue devoted to papers presented at the Aveiro Workshop on Graph Spectra.
https://doi.org/10.1016/j.laa.2006.08.027

L. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40: 35-41, 1977.
https://doi.org/10.2307/3033543

S. Gago. Métodos espectrales y nuevas medidas, modelos y parámetros en grafos pequeño-mundo invariantes de escala. PhD thesis, Universitat Politècnica de Catalunya, 2006.

S. Gago, J. Hurajova-Coronicova, and T. Madaras. On betweenness-uniform graphs. Czechoslovak Mathematical Journal , 63(3): 629-642, 2013.
https://doi.org/10.1007/s10587-013-0044-y

D. Hartman, A. Pokorná, and P. Valtr. On the connectivity and the diameter of betweenness-uniform graphs. In A. Mudgal and C. R. Subramanian, editors, Algorithms and Discrete Applied Mathematics, pages 317-330, Cham, 2021. Springer.
https://doi.org/10.1007/978-3-030-67899-9_26

J. Hurajova-Coronicova and T. Madaras. More on betweenness-uniform graphs. Czechoslovak Mathematical Journal, 68(2): 293-306, 2018.
https://doi.org/10.21136/CMJ.2018.0087-16

R. Lopez, J. Worrell, H. Wickus, R. Florez, and D. A. Narayan. Towards a characterization of graphs with distinct betweenness centralities. Australasian Journal Of Combinatorics , 68(2): 285-303, 2017.

A. Ouellet and M. Badri. Combining object-oriented metrics and centrality measures to predict faults in object-oriented software: An empirical validation. Journal of Software: Evolution and Process, 2023.
https://doi.org/10.1002/smr.2548

A. Pokorná. Characteristics of network centralities. Master's thesis, Charles University, Prague, Czech Republic, 2020.

Y. Sarabi and M. Smith. Gender diversity and publication activity-an analysis of STEM in the UK. Research Evaluation, 2023.
https://doi.org/10.1093/reseval/rvad008

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Babak Ghanbari, David Hartman, Vít Jelínek, Aneta Pokorná, Robert Šámal, Pavel Valtr

PDF