Rank monotonicity in centrality measures. (26th July 2017) - BOLDI, PAOLO
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.