The friendship paradox

What just happened?

The friendship paradox is a surprising result from social-network theory, described by the sociologist Scott Feld in 1991 (“Why your friends have more friends than you do”). It says that on average your friends have more friends than you do — and this holds for most people at the same time. It is not psychology or bad luck: it is pure mathematics of graph statistics.

The model: two different averages

We turn people into vertices of a graph and friendships into edges. The degree $\deg(v)$ is the number of friends of person $v$. The average number of friends per person is computed in the ordinary way:

But when we ask “how many friends do my friends have”, we average over friendship relations (over edges), not over people. A person of degree $d$ is a friend of $d$ people, so they appear on $d$ lists and are counted $d$ times:

The invariant: friends always win

For any friendship network the following inequality holds (it follows from the Cauchy–Schwarz inequality for the degrees):

Equality holds only when everyone has exactly the same number of friends (a regular graph — our “Ring”). In every other network $\bar d_{\mathrm{fr}} > \bar d$: the average number of friends your friends have is greater than the average number of friends per person.

Why it works — sampling bias

This is an example of sampling bias. Looking at “friends”, you are more likely to hit a popular person than a loner — because a popular person is someone’s friend dozens of times, while a loner barely once. Hubs are overrepresented in the set of friends and inflate the average. On the stage you can see it directly: the probe hopping along friendships keeps landing on the golden hubs.

What does it mean in practice?

The paradox has real applications. In epidemiology, vaccinating “friends of randomly chosen people” stops an epidemic more effectively than vaccinating random people — because it hits the hubs of the contact network. It also governs social-media analysis and viral marketing, and teaches caution in interpreting averages in networks: “the average friend” is something different from “the average person”.

Why this matters for your exams:

It is an extension of the topic of the mean and of graph theory. It shows that the way of averaging (over people vs over relations) changes the result — a classic trap in interpreting data. The same inequality $\sum d^2 / \sum d \ge \bar d$ is a disguised Cauchy–Schwarz inequality (the quadratic mean ≥ the arithmetic mean), which appears in advanced-level problems.

Remember: vertices of high degree — sociable people — are overrepresented among “friends”, so the average number of friends-of-friends $\bar d_{\mathrm{fr}}$ is always $\ge$ the average number of friends $\bar d$. Your friends really do have more friends than you on average — and it is not bad luck, just graph statistics.