The Friendship Paradox for Sparse Random Graphs

We consider undirected simple graphs with a large number of vertices. For each vertex we consider its friendship bias, defined as the difference between the average degree of the neighbors of that vertex and the degree of the vertex itself (when the vertex is not isolated), and zero otherwise. We are interested in the empirical distribution of the friendship biases of all the vertices. The friendship paradox says that the empirical distribution has a non-negative mean, with equality if and only if in each connected component of the graph all the degrees are the same.

We show that if a sequence of sparse random graphs converges to a rooted random tree in the sense of local weak convergence, then the empirical distribution of the friendship biases converges weakly to a limiting measure that is expressible in terms of the law of the rooted random tree. We quantify the properties of the limiting measure for four classes of sparse random graphs.