The Friendship Paradox

Definition Take a social network of $n$ people with at least one friendship, in which every friendship is mutual, and write $d_i$ for the number of friends of person $i$. Compare two ways of choosing someone at random. In the first, choose one of the $n$ people, each with probability $1/n$, and record that person’s number of friends. In the second, write out every person’s list of friends, pool all the entries, choose one entry with equal probability, and record the number of friends of the person named in that entry. Each friendship puts one entry on each of two lists, so the pool has $d_1 + \cdots + d_n$ entries, and person $j$ is named in it exactly $d_j$ times. The averages of the recorded numbers are

The friendship paradox is the fact that $m_{\text{friend}} \ge m_{\text{person}}$ in every such network, with equality exactly when everyone has the same number of friends. A person with no friends counts in the person average with $0$ friends and is never named in the pool. The statement is about these two averages. It does not say that every person has fewer friends than their own friends have on average, or even that most people do. The sociologist Scott Feld described the effect in 1991.

Definition In mathematics a social network is modeled as a graph. The people are the vertices, and each friendship is an edge joining two different people. Friendship here is mutual, so the edges have no direction, and two people either are friends or are not, so no pair is joined by two edges and nobody is joined to themselves. A graph with these properties is called a simple undirected graph. The friend list of a person is the list of people joined to that person by an edge.

Definition The degree of a person in a social network is that person’s number of friends, which is the number of edges at that vertex. Each edge has two ends, one at each of the two friends, so adding all the degrees counts every edge twice,

where $f$ is the number of friendships, that is, of edges. This is the handshake lemma. The average degree is the person average $m_{\text{person}} = 2f/n$. A person with no friends has degree $0$ and counts in it. If such people are left out, the average over everyone else is larger, but it is still at most $m_{\text{friend}}$, with equality exactly when everyone left has the same degree.

Definition Suppose each member $i$ of a finite population of $n$ members has a size $x_i \ge 0$, and the sizes have a positive total. Size-biased sampling chooses member $i$ with probability $x_i / (x_1 + \cdots + x_n)$, in proportion to its size, so members of size $0$ are never chosen. The average size of the chosen member is

where $\mu$ is the ordinary average of the sizes and $\sigma^2$ is their variance, the average of the squared distances $(x_i - \mu)^2$. Since $\sigma^2 \ge 0$, the size-biased average is at least $\mu$, and it is larger exactly when the sizes are not all equal. Choosing an entry from the pooled friend lists is size-biased sampling of people with degree as the size, which is why the friendship paradox holds.