In the study of the behavior of centrality measures with respect to network modifications, score monotonicity means that adding an arc increases the centrality score of the target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the arc relative to the remaining nodes. It is known [7, 8] that score and rank monotonicity hold in directed graphs for almost all the classical centrality measures. In undirected graphs one expects that the corresponding properties (where both endpoints of the new edge enjoy the increase in score/rank) hold when adding a new edge. However, recent results [6] have shown that in undirected networks this is not true: for many centrality measures, it is possible to find situations where adding an edge reduces the rank of one of its two endpoints. In this paper we introduce a weaker condition for undirected networks, semi-monotonicity, in which just one of the endpoints of a new edge is required to enjoy score or rank monotonicity. We show that this condition is satisfied by closeness and betweenness centrality, and that harmonic centrality satisfies it in an even stronger sense.
Score and Rank Semi-monotonicity for Closeness, Betweenness and Harmonic Centrality / P. Boldi, D. D'Ascenzo, F. Furia, S. Vigna (STUDIES IN COMPUTATIONAL INTELLIGENCE). - In: Complex Networks & Their Applications XII / [a cura di] H. Cherifi, L.M. Rocha, C. Cherifi, M. Donduran. - [s.l] : Springer Nature Switzerland, 2024. - ISBN 978-3-031-53472-0. - pp. 102-113 (( Intervento presentato al 12. convegno Complex Networks and Their Applications tenutosi a Menton nel 2023 [10.1007/978-3-031-53472-0_9].
Score and Rank Semi-monotonicity for Closeness, Betweenness and Harmonic Centrality
P. BoldiPrimo
;D. D'AscenzoSecondo
;F. FuriaPenultimo
;S. VignaUltimo
2024
Abstract
In the study of the behavior of centrality measures with respect to network modifications, score monotonicity means that adding an arc increases the centrality score of the target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the arc relative to the remaining nodes. It is known [7, 8] that score and rank monotonicity hold in directed graphs for almost all the classical centrality measures. In undirected graphs one expects that the corresponding properties (where both endpoints of the new edge enjoy the increase in score/rank) hold when adding a new edge. However, recent results [6] have shown that in undirected networks this is not true: for many centrality measures, it is possible to find situations where adding an edge reduces the rank of one of its two endpoints. In this paper we introduce a weaker condition for undirected networks, semi-monotonicity, in which just one of the endpoints of a new edge is required to enjoy score or rank monotonicity. We show that this condition is satisfied by closeness and betweenness centrality, and that harmonic centrality satisfies it in an even stronger sense.File | Dimensione | Formato | |
---|---|---|---|
semi.pdf
accesso aperto
Tipologia:
Pre-print (manoscritto inviato all'editore)
Dimensione
269.2 kB
Formato
Adobe PDF
|
269.2 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.