In this paper, we consider fairness for link analysis and in particular for the celebrated PageRank algorithm. We provide definitions of fairness, both for PageRank and Personalized PageRank. We propose two families of fair PageRank algorithms: the first (Fairness-Sensitive PageRank) modifies the jump vector of the PageRank algorithm to enforce fairness; the second (Locally Fair PageRank) imposes a fair behavior per node. We prove that the Locally Fair algorithms achieve also personalized fairness, and that this is the only family of algorithms that is personalized fair, establishing an equivalence between personalized fairness and local fairness. We also consider the problem of achieving fairness while minimizing the utility loss with respect to the original algorithm. The utility loss for a network can be seen as a measure of the cost of being fair. We present experiments with real and synthetic graphs that examine the fairness of the original PageRank and demonstrate qualitatively and quantitatively the properties of our algorithms.

2021 THE WEB CONFERENCE NEWSLETTER
The Web Conference is announcing latest news and developments biweekly or on a monthly basis. We respect The General Data Protection Regulation 2016/679.