January 14, 2016

Rank monotonicity in centrality measures

Here you can find my first contribution to the academic word! :)
Too bad I found only afterwards the quote from Bertrand Russell: "The axiomatic method has many advantages over honest work." Indeed, I think this might be a case in point.

The following summary is an excerpt from a report on my research. Enjoy!

I proved whether a dozen of centrality measures satisfy a property called rank-monotonicity. After 70 years of research there is not a unanimous agreement on the definition of centrality. Several measures are often only vaguely related to the intuitive ideas they purport to index, and many are so complex that it is difficult or impossible to discover what, if anything, they are measuring \cite{freeman}. In "Axioms for Centrality" [1] the authors conducted an axiomatic approach to centrality measures, stating three properties (called axioms) that a centrality measure should satisfy in order to be considered valid. I extended the previous work, as suggested by the authors, with a fourth axiom: rank-monotonicity. A centrality measure satisfies the rank-monotonicity axiom if for every graph $G$ and every pair of nodes $x, y$ such that there's no arc between $x$ and $y$, when we add $x \rightarrow y$ to $G$ the following happens:
  •   if the score $z$ was strictly smaller than the score of $y$, this remains true after adding $x \rightarrow y$
  •   if the score of $z$ was smaller than or equal to the score of $y$, this remains true after adding $x \rightarrow y$.
In other words, the rank of a node $z$ relative to $y$ cannot improve because of the addition of an arc $x \rightarrow y$. I proved for the most important algorithms used in graph analysis whether they have this property, exhibiting counterexamples where needed. For instance, I generalized the results of Chien [2] for the much quoted PageRank algorithm used in Google [3], which was stated using the language of Markov chains, and only on strongly connected graphs. I went further, and I proved the same property for weakly and not connected graphs.

[1] Boldi, Paolo, and Sebastiano Vigna. "Axioms for centrality." Internet Mathematics 10.3-4 (2014): 222-262.
[2] Chien, Steve, et al. "Link evolution: Analysis and algorithms." Internet mathematics 1.3 (2004): 277-304.
[3] Page, Lawrence, et al. "The PageRank citation ranking: bringing order to the Web." (1999).