Berlin 2024 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
SOE: Fachverband Physik sozio-ökonomischer Systeme
SOE 10: Sociophysics Approaches to Diversity and Equality (Accompanying Session to the Symposium Diversity and Equality in Physics)
SOE 10.2: Talk
Tuesday, March 19, 2024, 13:30–13:45, PTB HS HvHB
Toward Fairness in Network Algorithms: Rankings by Biased Random Walks — •Elisabetta Salvai1, Jacob Aarup Dalsgaard2,3, Giovanni Petri4,5,6, and Roberta Sinatra2,3,7,8 — 1University of Turin — 2SODAS, University of Copenhagen — 3IT University of Copenhagen — 4Network Science Institute, Northeastern University London — 5CENTAI Institute — 6IMT Lucca Institute — 7ISI Foundation — 8Complexity Science Hub
Ranking algorithms play a significant role in ordering information in networks and identifying important and influential nodes. In this study, we investigate the fairness of the widely used PageRank algorithm in networks of nodes with binary attributes. We propose a new fairness definition rooted in demographic parity in the top-ranked positions, where the observer's attention is predominantly concentrated. This definition is based on the idea that a fair ranking has the same proportion of attributes in the top-ranked positions as in the whole network. To improve the fairness of rankings, we then study a modification of the PageRank algorithm where we add a parameter that biases the random walk exploration at the core of the algorithm. This parameter changes the choice probability of the random walkers based on the degree of the neighbouring nodes. We study this biased PageRank algorithm, in both synthetic and real-word networks, for different values of the bias parameter. We analyze the degree-attribute correlations to explore how the structure of networks impacts the biased random walk ranking. We can forecast the most suitable biased parameter value by comprehending network structures.
Keywords: PageRank; algorithmic fairness; random walks; homophily; networks