Associate Professor (Reader) in Machine Learning
School of Mathematics, The University of Edinburgh
The Maxwell Institute for Mathematical Sciences
Alan Turing Institute | Bayes Centre | Gen AI Lab
School of Mathematics, Gran Sasso Science Institute
email: f dot tudisco at ed.ac.uk
Happy to share that our paper Generalized Friendship Paradoxes in Network Science has been accepted for publication in the SIAM Journal on Matrix Analysis and Applications.
Joint work with Desmond J. Higham and Francesco Hrobat.
The classic friendship paradox is the observation that, on average, your friends have more friends than you do. In this paper we take a linear algebra perspective and ask when a paradox of this kind is inevitable once “number of friends” is replaced by more general node attributes. Building on Feld’s seminal 1991 work, we distinguish two ways of averaging — global and local — and show that a generalized friendship paradox holds for a large family of walk-based centralities, including Katz centrality and total subgraph communicability, as well as for nonbacktracking eigenvector centrality. We also prove a “loneliness” counterpart: measuring loneliness as the reciprocal of the number of friends, the paradox always holds in reverse, so on average we are lonelier than our friends.
The code to reproduce all the experiments — and to run the paradox analysis on your own networks — is available on GitHub. It includes a GraphCentralityAnalyzer class computing the degree, Katz, exponential (total subgraph communicability), and nonbacktracking eigenvector centralities together with the corresponding paradox margins, the scripts that generate all figures and tables in the paper, and six real-world networks to play with.