The friendship paradox

People tend to be less popular than their friends. This paradox, first observed by Feld (1991), is due to popular people appearing on many friend lists.

For example, consider the social network among members of a karate club studied by Zachary (1977):

The network contains $n = 34$ nodes with mean degree $E [d_{i}] \equiv \frac{1}{n} \sum_{i = 1}^{n} d_{i} = 4.59,$ where $E$ takes expected values across nodes and $d_{i}$ is the degree of node $i$ . If $N_{i}$ denotes the set of $i$ 's neighbors, then the mean degree among those neighbors equals $f_{i} \equiv \frac{1}{d_{i}} \sum_{j \in N_{i}} d_{j} .$ The friendship paradox states that $E [d_{i}] \leq E [f_{i}]$ in any network. In Zachary’s network we have $E [f_{i}] = 9.61$ , about twice the mean degree.

We can approximate $E [f_{i}]$ using the following procedure:

Choose a stub (i.e., the endpoint of an edge) uniformly at random.
Record the degree of the chosen stub.

Repeating these steps many times yields a degree distribution that over-samples from high-degree nodes. The mean of this distribution answers the following question: “How many friends does a typical friend have?” The probability of choosing node $i$ in the first step equals $p_{i} \equiv \frac{d_{i}}{\sum_{j = 1}^{n} d_{j}},$ the proportion of stubs that $i$ adds to the network. Using the probabilities $p_{i}$ to compute the expected value of the degrees $d_{i}$ yields an approximation $\begin{aligned} \hat{E [f_{i}]} & = \sum_{i = 1}^{n} p_{i} d_{i} \\ = \sum_{i = 1}^{n} (\frac{d_{i}}{\sum_{j = 1}^{n} d_{j}}) d_{i} \\ = \frac{\sum_{i = 1}^{n} d_{i}^{2}}{\sum_{j = 1}^{n} d_{j}} \\ = \frac{E [d_{i}^{2}]}{E [d_{i}]} \\ = E [d_{i}] + \frac{Var (d_{i})}{E [d_{i}]} \end{aligned}$ of $E [f_{i}]$ . Notice that if $Var (d_{i}) = 0$ then $\hat{E [f_{i}]} = E [d_{i}]$ ; in that case, everyone has the same degree as their friends, and so there is no friendship paradox. The difference between the mean degree $E [d_{i}]$ and the typical friend’s degree $\hat{E [f_{i}]}$ grows as the variance in degrees grows.

The approximation $\hat{E [f_{i}]}$ is closest to $E [f_{i}]$ when there is no assortative mixing with respect to degree. Then the $d_{i}$ are uncorrelated with the $f_{i}$ . But this isn’t true in Zachary’s network:

Indeed, in Zachary’s network we have $\hat{E [f_{i}]} = 7.77$ , which is smaller than the true value $E [f_{i}] = 9.61$ . To see why, notice that $\begin{aligned} E [d_{i} f_{i}] & = \frac{1}{n} \sum_{i = 1}^{n} d_{i} f_{i} \\ = \frac{1}{n} \sum_{i = 1}^{n} \sum_{j \in N_{i}} d_{j} \\ \overset{⋆}{=} \frac{1}{n} \sum_{j = 1}^{n} d_{j}^{2} \\ = E [d_{j}^{2}], \end{aligned}$ where $⋆$ holds because $j$ appears in $d_{j}$ neighborhoods $N_{i}$ . But $E [d_{i} f_{i}] = E [d_{i} f_{i}] + Cov (d_{i}, f_{i})$ by the definition of covariance, from which it follows that $\hat{E [f_{i}]} = E [f_{i}] + \frac{Cov (d_{i}, f_{i})}{E [d_{i}]} .$ Thus $\hat{E [f_{i}]}$ under-estimates $E [f_{i}]$ in Zachary’s network because $Cov (d_{i}, f_{i}) = - 8.45$ is negative.

The value of $\hat{E [f_{i}]}$ depends only on the mean and variance of degrees, and not the correlation of degrees across adjacent nodes. Thus $\hat{E [f_{i}]}$ is invariant to degree-preserving randomizations (DPRs). But $E [f_{i}]$ can vary under DPRs because they can change the correlation of adjacent nodes’ degrees. For example, consider the three networks shown below:

The networks $G_{1}$ , $G_{2}$ , and $G_{3}$ have the same degree distributions. As a result, they have the same mean degrees $E [d_{i}]$ and approximations $\hat{E [f_{i}]}$ of $E [f_{i}]$ . But the true values of $E [f_{i}]$ differ because the correlations $Corr (d_{i}, f_{i})$ differ:

Network	$E [d_{i}]$	$\hat{E [f_{i}]}$	$E [f_{i}]$	$Corr (d_{i}, f_{i})$
$G_{1}$	1.43	1.6	1.43	1.00
$G_{2}$	1.43	1.6	1.57	0.20
$G_{3}$	1.43	1.6	1.71	-0.91

The network $G_{1}$ is perfectly assortative with respect to degree, so $\hat{E [f_{i}]}$ over-estimates $E [f_{i}]$ . Whereas $G_{3}$ is dis-assortative with respect to degree, so $\hat{E [f_{i}]}$ under-estimates $E [f_{i}]$ . The network $G_{2}$ is relatively unsorted, so $\hat{E [f_{i}]}$ is close to $E [f_{i}]$ .