The generalized friendship paradox for spectral centralities

Abstract We revisit the classical friendship paradox which states that on an average one’s friends have at least as many friends as oneself and generalize it to a variety of network centrality indices. For a broad class of spectral centralities on connected undirected graphs—degree, eigenvector centrality, walk counts, Katz centrality and PageRank, we show that the average centrality of a node’s neighbours always exceeds the global average centrality. We further prove an analogous result for PageRank on strongly connected directed graphs. For degree, this recovers the classical friendship paradox, while for the other centralities it yields new instances of what we call the centrality paradox. We also compare our neighbour-averaged formulation with edge-sampled versions studied previously in the literature.