The friendship paradox for sparse random graphs

Abstract

Let $G_n$ be an undirected finite graph on $n\in \mathbb{N}$ vertices labelled by $[n]=\{1,\dots ,n\}$. For $i\in [n]$, let $\hat{I}{”}_{i,n}$ be the friendship bias of vertex $i$, defined as the difference between the average degree of the neighbours of vertex $i$ and the degree of vertex $i$ itself when $i$ is not isolated, and zero when $i$ is isolated. Let $\hat{I}{¼}_n$ denote the friendship-bias empirical distribution, i.e., the measure that puts mass $\frac{1}{n}$ at each $\hat{I}{”}_{i,n}$, $i\in [n]$. The friendship paradox says that ${\int }_{\mathbb{R}}x\hat{I}{¼}_n(\mathrm{d}x)\ge 0$, with equality if and only if in each connected component of $G_n$ all the degrees are the same. We show that if $(G_n{)}_{n\in \mathbb{N}}$ is a sequence of sparse random graphs that converges to a rooted random tree in the sense of convergence locally in probability, then $\hat{I}{¼}_n$ converges weakly to a limiting measure $\hat{I}¼$ that is expressible in terms of the law of the rooted random tree. We study $\hat{I}¼$ for four classes of sparse random graphs: the homogeneous Erdős-Rényi random graph, the inhomogeneous Erdős-Rényi random graph, the configuration model and the preferential attachment model. In particular, we compute the first two moments of $\hat{I}¼$, identify the right tail of $\hat{I}¼$, and argue that $\hat{I}¼([0,\infty ))\ge \frac{1}{2}$, a property we refer to as friendship paradox significance.

To appear in Probability Theory and Related Fields