The friendship paradox for sparse random graphs

Probability Theory and Related Fields, vol. 195, pp. 109–131

Abstract

Abstract Let $$G_n$$ G n be an undirected finite graph on $$n\in {\mathbb {N}}$$ n ∈ N vertices labelled by $$[n] = \{1,\ldots ,n\}$$ [ n ] = { 1 , … , n } . For $$i \in [n]$$ i ∈ [ n ] , let $$\Delta _{i,n}$$ Δ 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 $$\mu _n$$ μ n denote the friendship-bias empirical distribution , i.e., the measure that puts mass $$\frac{1}{n}$$ 1 n at each $$\Delta _{i,n}$$ Δ i , n , $$i \in [n]$$ i ∈ [ n ] . The friendship paradox says that $$\int _{\mathbb {R}}x\mu _n(\textrm{d}x) \ge 0$$ ∫ R x μ n ( d x ) ≥ 0 , with equality if and only if in each connected component of $$G_n$$ G n all the degrees are the same. We show that if $$(G_n)_{n\in {\mathbb {N}}}$$ ( G n ) n ∈ N is a sequence of spars

Authors 3

1. Rajat Subhra Hazra Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Mathematical Institute, Leiden University, Einsteinweg 55, 2333 CC, Leiden, The Netherlands

2. Frank den Hollander corresponding Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Mathematical Institute, Leiden University, Einsteinweg 55, 2333 CC, Leiden, The Netherlands

3. Azadeh Parvaneh Aachen Mathematical Institute

   Leiden University

   Affiliation as printed

   Mathematical Institute, Leiden University, Einsteinweg 55, 2333 CC, Leiden, The Netherlands