**Why your friends, on average, have more friends than you do**The

**friendship paradox** is the observation that your friends, on average, have more friends than you do. This phenomenon, which was first observed by the sociologist

**Scott L. Feld** in 1991, is mathematically provable, even though it contradicts most people's intuition that they have more friends than their friends do.

Wikipedia gives a nice intuitive explanation for this phenomenon:

*People with more friends are more likely to be your friend in the first place; that is, they have a higher propensity to make friends in the first place.* However, it is also possible to explain the phenomenon using graph theory and mathematical statistics. I give an outline of the mathematical proof at the end of this post for those who are interested, but the upshot is that if we look at everybody's numbers of friends, and these numbers have a mean of μ and a variance of σ^2, then the average number of friends that an average friend has is μ + (σ^2/μ), which will be greater than μ assuming that someone has at least one friend and that not everyone has the same number of friends.

The recent paper

*The Majority Illusion in Social Networks* (

http://arxiv.org/abs/1506.03022) by

**Kristina Lerman**,

**Xiaoran Yan**, and

**Xin-Zeng Wu** explores some phenomena that are related to the friendship paradox. The authors explain how, under certain conditions, the structure of a social network can make it appear to an individual that certain types of behaviour are far more common than they actually are.

The diagram here, which comes from the paper, illustrates this point. It shows two social networks, (a) and (b), each containing 14 individuals. In each case, three vertices are marked in red; let's suppose that these correspond to the heavy drinkers in the group. In social network (a), the heavy drinkers are three of the most popular people, and the configuration of the network means that each of the other eleven individuals observes that at least half of their friends are heavy drinkers. This will lead these eleven people to think that heavy drinking is common in their society, when in fact it is not: only 3/14 of the group are heavy drinkers. In social network (b), there are the same number of heavy drinkers, but they are not particularly popular, and nobody in the group will have heavy drinkers as most of their friends.

Network (a) is experiencing what the authors call the

**majority illusion**, whereas network (b) is not. The illusion will tend to occur when the behaviour in question is correlated with having many friends. The paper shows that the illusion is likely to be more prevalent in

**disassortative** networks, which means networks in which people have less tendency to be friends with people like themselves. Observe that in network (b), many of the non-heavy drinkers are friends with each other, whereas in network (a), they are not. This suggests that network (a) is more disassortative, and thus more susceptible to the majority illusion.

The authors also study the phenomenon using three real-world data sets: (a) the coauthorship network of high energy physicists (HepTh), (b) the social network Digg, studying only the mutual-following links, and (c) the network representing the links between political blogs. It turns out that networks (a) and (b) are assortative, and (c) is disassortative. They also look at the the case of Erdős–Rényi-type networks, which can be thought of as random.

As the paper points out, the friendship paradox has real life applications. For example, if one is monitoring a contagious outbreak, it is more efficient to monitor random

*friends* of random people than it is to monitor random people. This is because the friends are more likely to be better connected, are more likely to get sick earlier, and are more likely to infect more people once sick. The reason for this has to do with the fact that these attributes are positively correlated with having many friends.

If you're wondering why your coauthors are on average cited more often than you are, or why your sexual partners on average have had more sexual partners than you have, now you know. I found out about this paper via my Facebook friend

+Paul Mitchener, who has more Facebook friends than I do.

**Relevant links**Wikipedia's page on the Friendship Paradox contains much of the information in this post, including a sketch of the proof given below:

https://en.wikipedia.org/wiki/Friendship_paradoxWikipedia on assortativity:

https://en.wikipedia.org/wiki/AssortativityHere's another post by me about the mathematics of social networks, in which I explain why it is impossible for everyone on Google+ to have more than 5000 followers. It provoked a surprisingly hostile reaction:

https://plus.google.com/101584889282878921052/posts/YV7j9LRqKsXA post by me about Erdős and Rényi's construction of the random graph:

https://plus.google.com/101584889282878921052/posts/34guwy4ftWX**Appendix: Mathematical proof of the friendship paradox**Assume for simplicity that friendship is a symmetric relation: in other words, that whenever A is a friend of B, then B is also a friend of A. We can then model a friendship network with an undirected graph G, with a set of vertices V and a set of edges E. Each vertex v in V represents an individual, and each edge e in E connects a pair of individuals who are friends. For each vertex v in V, the number d(v) (the

*degree* of v) is the number of edges connected to v; in other words, the number of friends v has.

The average number of friends of everyone in the network is then given by summing d(v) over all vertices v of V, and then dividing by |V|, the total number of people. Using basic graph theory, this number, μ, can be shown to be equal to 2 times |E| divided by |V|, where |E| is the number of edges.

In order to find the number of friends that a typical friend has, one first chooses a random edge of E (which represents a pair of friends) and one of the two endpoints of E (representing one of the pair of friends); the degree of this latter vertex is the number of friends that a friend has. Summing these degrees over all possible choices amounts to summing d(v)^2 over all possible vertices, and since the number of choices is 2 times |E|, it follows that the average number of friends a friend has is the sum of d(v)^2 divided by 2 times |E|. Using the formula for μ above, it follows that μ times the average number of friends that a friend has is equal to the average value of d(v)^2. However, the average value of d(v)^2 is also equal, by basic mathematical statistics, to the sum of the

*square of the mean* of the d(v) plus the

*variance* of the d(v). The result follows from this.

#mathematics #scienceeveryday #spnetwork arXiv:1506.03022