Friday, 21 September 2012

The Paradox Of Friendship – Why do our friends have more friends than we do?

What may look like a psychological phenomenon, is actually basic maths.

In a colossal study of Facebook by Johan Ugander, Brian Karrer, Lars Backstrom and Cameron Marlow,  examined all of Facebook’s active users, which at the time included 721 million people — about 10 percent of the world’s population — with 69 billion friendships among them. They found that a user’s friend count was less than the average friend count of his or her friends, 93 percent of the time. Next, they measured averages across Facebook as a whole, and found that users had an average of 190 friends, while their friends averaged 635 friends of their own.

Studies of offline social networks show the same trend. It has nothing to do with personalities; it follows from basic arithmetic. For any network where some people have more friends than others, it’s a theorem that the average number of friends of friends is always greater than the average number of friends of individuals.
This phenomenon has been called thefriendship paradox. Its explanation hinges on a numerical pattern — a particular kind of “weighted average” — that comes up in many other situations. Understanding that pattern will help you feel better about some of life’s little annoyances.

In this hypothetical example, Ross, Chandler, Phoebe and Rachel are four friends. Lines signify reciprocal friendships between them; two people are connected if they’ve named each other as friends.
Ross’s only friend is Chandler, a social butterfly who is friends with everyone. Phoebe and Rachel are friends with each other and with Chandler. So Ross has 1 friend, Chandler has 3, Phoebe has 2 and Rachel has 2. That adds up to 8 friends in total, and since there are 4 girls, the average friend count is 2 friends per girl. This average, 2, represents the “average number of friends of individuals” in the statement of the friendship paradox. Remember, the paradox asserts that this number is smaller than the “average number of friends of friends” — but is it? Part of what makes this question so dizzying is its sing-song language. Repeatedly saying, writing, or thinking about “friends of friends” can easily provoke nausea. So to avoid that, I’ll define a friend’s “score” to be the number of friends she has. Then the question becomes: What’s the average score of all the friends in the network?

Imagine each person calling out the scores of his/her friends. Meanwhile an accountant waits nearby to compute the average of these scores.
Ross: “Chandler has a score of 3.”
Chandler: “Ross has a score of 1. Phoebe has 2. Rachel has 2.”
Phoebe: “Chandler has 3. Rachel has 2.”
Rachel: “Chandler has 3. Phoebe has 2.”

These scores add up to 3 + 1 + 2 + 2 + 3 + 2 + 3 + 2, which equals 18. Since 8 scores were called out, the average score is 18 divided by 8, which equals 2.25.
Notice that 2.25 is greater than 2. The friends on average do have a higher score than the girls themselves. That’s what the friendship paradox said would happen.
The key point is why this happens. It’s because popular friends like Chandler contribute disproportionately to the average, since besides having a high score, they’re also named as friends more frequently. Watch how this plays out in the sum that became 18 above: Ross was mentioned once, since she has a score of 1 (there was only 1 friend to call her name) and therefore she contributes a total of 1 x 1 to the sum; Chandler was mentioned 3 times because she has a score of 3, so she contributes 3 x 3; Phoebe and Rachel were each mentioned twice and contribute 2 each time, thus adding 2 x 2 apiece to the sum. Hence the total score of the friends is (1 x 1) + (3 x 3) + (2 x 2) + (2 x 2), and the corresponding average score is

 Each individual’s score is multiplied by itself before being summed. In other words, the scores are squared before they’re added. That squaring operation gives extra weight to the largest numbers (like Chandler’s 3 in the example above) and thereby tilts the weighted average upward.
So that’s intuitively why friends have more friends, on average, than individuals do. The friends’ average — a weighted average boosted upward by the big squared terms — always beats the individuals’ average, which isn’t weighted in this way.

Like many of math’s beautiful ideas, the friendship paradox has led to exciting practical applications unforeseen by its discoverers. It recently inspired an early-warning system for detecting outbreaks of infectious diseases. In a study conducted at Harvard during the H1N1 flu pandemic of 2009, the network scientists Nicholas Christakis and James Fowler monitored the flu status of a large cohort of random undergraduates and found that people with more connections were infected faster.

For more analogies check out the whole article at a New York Times blog.

1 comment: