Rank monotonicity in centrality measures

Datos 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)
Año2017
Volumen5
Número4
Páginas529-550
Fecha de publicación2017-07-26
Peer ReviewedSí
Open AccessSí
TipoARTICLE
RevistaNetwork Science (JOURNAL)
Identificadores de la revistaISSN: 2050-1250 • E-ISSN: 2050-1242
EditorialCambridge University Press (PUBLISHER • US)
DOI10.1017/nws.2017.21
OpenAlexW2737856238
IdiomaEN
Citas recibidas4
Referencias 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