Rank monotonicity in centrality measures. (26th July 2017)

• Record Type: Journal Article
• Authors: BOLDI, PAOLO; LUONGO, ALESSANDRO; VIGNA, SEBASTIANO
• Is Part Of: Network science. Volume 5:Number 4(2017)
• Page Start: 529
• Page End: 550
• Publication Date: 2017-07-26
• Subjects: centrality, -- network analysis, -- rank monotonicity; Social networks -- Research -- Periodicals; System analysis -- Periodicals; System theory -- Periodicals; Computer science -- Periodicals; 003.72
• DOI: 10.1017/nws.2017.21
• Languages: English
• ISSNs: 2050-1242

Abstract

Abstract: 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.