Friendship paradox

The Friendship paradox on Wikipedia states that most people have fewer friends than their friends have, on average. This fills in a few of the steps of their derivation of this result.

A social network is a graph, \(G=(V,E)\). A node has degree, \(d(v)\).

The average number of friends (direct neighbors), μ, of a randomly chosen person (node) in the graph is:

\begin{equation} \mu = \frac{\sum_{v\epsilon V} d(v)}{\lvert V\rvert} = \frac{2\lvert E\rvert}{\lvert V\rvert} = E[d(v)] \end{equation}

The sum of the number of degrees over all nodes is the same as twice the number of edges, because each edge is counted twice, once for each direction.

They then state that

\begin{equation} \frac{\sum_{v\epsilon V} d(v)^2}{2\lvert E\rvert} = \mu + \frac{\sigma^2}{\mu} \label{result} \end{equation}

where σ is the variance of \(d(v)\).

Using the definition of the variance,

\begin{equation} \sigma = E[(d(v) - E(d(v)))^2] = E[(d(v) - \mu)^2] \end{equation}

\[ = E[d^2(v) - 2\mu^2 + \mu^2] = E[d^2(v)] - \mu^2 \]

Therefore,

\begin{equation} E[d^2(v)] = \mu^2 + \sigma \end{equation}

Also,

\begin{equation} E[d^2(v)] = \frac{1}{\lvert V\rvert}\sum_{v\epsilon V} d(v)^2 \end{equation}

So,

\begin{equation} (\mu^2 + \sigma)\lvert V\rvert = \sum_{v\epsilon V} d(v)^2 \end{equation}

To derive equation \eqref{result},

\[ \frac{\sum_{v\epsilon V} d(v)^2}{2\lvert E\rvert} = \frac{(\sigma^2 + \mu^2)\lvert V\rvert}{2\lvert E\rvert} \] (by 6)

\[ = \frac{1}{\mu}(\sigma^2 + \mu^2) \] (because \(2\lvert E\rvert = \mu\lvert V\rvert\))

\[ = \frac{\sigma^2}{\mu} + \mu \]