The friendship paradox for sparse random graphs

Abstract Let $$G_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> be an undirected finite graph on $$n\in {\mathbb {N}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:math> vertices labelled by $$[n] = \{1,\ldots ,n\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> . For $$i \in [n]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> , let $$\Delta _{i,n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Δ</mml:mi> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> </mml:math> 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 $$\mu _n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> denote the friendship-bias empirical distribution , i.e., the measure that puts mass $$\frac{1}{n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>n</mml:mi> </mml:mfrac> </mml:math> at each $$\Delta _{i,n}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>Δ</mml:mi> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> </mml:math> , $$i \in [n]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> . The friendship paradox says that $$\int _{\mathbb {R}}x\mu _n(\textrm{d}x) \ge 0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>∫</mml:mo> <mml:mi>R</mml:mi> </mml:msub> <mml:mi>x</mml:mi> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mtext>d</mml:mtext> <mml:mi>x</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> </mml:math> , with equality if and only if in each connected component of $$G_n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> all the degrees are the same. We show that if $$(G_n)_{n\in {\mathbb {N}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> </mml:msub> </mml:math> is a sequence of sparse random graphs that converges to a rooted random tree in the sense of convergence locally in probability, then $$\mu _n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>μ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> converges weakly to a limiting measure $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> that is expressible in terms of the law of the rooted random tree. We study $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> 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 $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> , identify the right tail of $$\mu $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>μ</mml:mi> </mml:math> </jats:a