I was browsing NPR earlier this week and saw this story:
Source: NPR
It reminded me of a fascinating result I learned in Mark Newman‘s Network Theory class at Michigan: on average your friends actually do have more friends than you — and it’s mathematically provable.
ProofLet’s start off by representing the people in some domain as a mathematical graph. Each person corresponds to a node, and two nodes have an undirected edge between them if and only if the people to whom the nodes correspond are friends. We say that if a node has an edge to 
other nodes (corresponding to friends) that it has “degree .”
The average person therefore has 
friends. Now how many friends of friends are there? If I have 
friends and they each have 
friends, then my friends have a total of 
friends. So it’s the sum of my degree times the degrees of each of my neighbors. When averaged over every node in the graph, the average person has 
friends of friends. Or we can say that on average, a person’s friends have 
friends themselves.
Now recall the definition of variance. The variance in the distribution of degrees is 
. We can work out the following chain of reasoning:
Both 
and are non-negative, and is zero only if every node has exactly the same degree. Therefore, if there is any variance at all in the number of friends a person has, then 
.
So if you think your friends have more friends than you, they probably do.
Advertisements Share this:
