Název: On the structure and values of betweenness centrality in dense betweenness-uniform graphs
Autoři: Ghanbari, B. ; Hartman, David ; Jelínek, V. ; Pokorná, Aneta ; Šámal, R. ; Valtr, P.
Typ dokumentu: Příspěvky z konference
Konference/Akce: EUROCOMB 2023: European Conference on Combinatorics, Graph Theory and Applications /12./, Prague (CZ), 20230828
Rok: 2023
Jazyk: eng
Abstrakt: Betweenness centrality is a network centrality measure based on the amount ofshortest 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, wefocus on betweenness-uniform graphs with betweenness centrality below one. Wedisprove a conjecture about the existence of a BUG with betweenness valueαforany rational numberαfrom the interval (3/4,∞) by showing that only very few be-tweenness 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 graphswith a betweenness centrality smaller than one. In graphs of smaller diameter, thesame can be shown under a uniformity condition on the components of the comple-ment.
Číslo projektu: GA23-07074S (CEP)
Poskytovatel projektu: GA ČR
Zdrojový dokument: EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications
Poznámka: Související webová stránka: https://journals.muni.cz/eurocomb/article/view/35600/31477

Instituce: Ústav informatiky AV ČR (web)
Informace o dostupnosti dokumentu: Dokument je dostupný v repozitáři Akademie věd.
Původní záznam: https://hdl.handle.net/11104/0344131

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-528992


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Ústav informatiky
Konferenční materiály > Příspěvky z konference
 Záznam vytvořen dne 2023-07-23, naposledy upraven 2023-12-06.


Není přiložen dokument
  • Exportovat ve formátu DC, NUŠL, RIS
  • Sdílet