Rank monotonicity in centrality measures

Dados Bibliográficos

ID6161403
AutoresPaolo Boldi (0000-0002-8297-6255, University of Milan), Alessandro Luongo (0000-0002-5746-3167, University of Milan), Sebastiano Vigna (0000-0002-3257-651X, University of Milan)
Ano2017
Volume5
Fascículo4
Páginas529-550
Data de publicação2017-07-26
Peer ReviewedSim
Open AccessSim
TipoARTICLE
PeriódicoNetwork Science (JOURNAL)
Identificadores do periódicoISSN: 2050-1250 • E-ISSN: 2050-1242
EditoraCambridge University Press (PUBLISHER • US)
DOI10.1017/nws.2017.21
OpenAlexW2737856238
IdiomaEN
Citações recebidas4
Referências citadas31

A measure of centrality is rank monotone if after adding an arc x → y , all nodes with a score smaller than (or equal to) y have still a score smaller than (or equal to) y . If, in particular, all nodes with a score smaller than or equal to y get a score smaller than y (i.e., all ties with y are broken in favor of y ), the measure is called strictly rank monotone . We prove that harmonic centrality is strictly rank monotone, whereas closeness is just rank monotone on strongly connected graphs, and that some other measures, including betweenness, are not rank monotone at all (sometimes not even on strongly connected graphs). Among spectral measures, damped scores such as Katz's index and PageRank are strictly rank monotone on all graphs, whereas the dominant eigenvector is strictly monotone on strongly connected graphs only

Betweenness centrality · Centrality · Closeness · Combinatorics · Discrete mathematics · Mathematical analysis · Measure (data warehouse · Monotone polygon · Monotonic function · PageRank · Rank (graph theory · Advanced Graph Theory Research · Complex Network Analysis Techniques · Computer Science · Graph theory and applications · Mathematics · Theoretical Computer Science