Friendship Paradox

[murbard2]

This is established by making a one-step random walk in the friendship graph.

Things get more interesting when you start taking longer walks. If you take a long enough walk in a (strongly connected) graph, the probability of ending up in a particular place becomes independent of your starting point.

In fact, social graphs are said to be "fast-mixing", which means that "long enough" is typically only O(log n). In contrast, if you were walking in a two dimensional lattice, "long enough" would be O(sqrt n). This is the idea behind the "6 degrees of separation" factoid.

So what is the limiting probability distribution? That's actually the pagerank.

Which means that if friends randomly pass on a token, it's likely to end up in the hands of someone very influential with a lot of friends. It's been used for vaccine delivery.

[randomwalker]

Social graphs are not fast mixing. This used to be widely assumed but recent empirical measurements have refuted the assumption. [1] If I recall correctly, random walks tend to get stuck in cities and other highly-dense subgraphs.

Six degrees of separation refers to shortest paths, and fast mixing is decidedly _not_ the intuition behind it.

[1] http://syssec.kaist.ac.kr/~yongdaek/doc/imc2010.pdf

[gertef]

> If you take a long enough walk in a (strongly connected) graph, the probability of ending up in a particular place becomes independent of your starting point.

And this was the foundation of Google's PageRank. http://en.wikipedia.org/wiki/Google_matrix

[jiggy2011]

I wonder if this can be exploited for business networking purposes. Simply choose a person in your "network" and ask them to introduce you to one other person they know and repeat with the new person.

[andrewstuart2]

I may be oversimplifying, but thinking of it at this extreme helped me intuit a bit better.

Imagine 1,000,001 people. One of them is friends with the rest, all of whom only have this one friend. The average number of friends a person has is 2, but the aggregate average for their friends is 1,000,000.

So most social graphs probably look like a spoke-hub where a minority of people have a very large number of friends.

[visakanv]

An excellent way of thinking about it.

[jiggy2011]

This might explain why introverts tend to think that everyone else is more extrovert than them, there's probably a lot more introverts than we realise but we're just less likely to meet them.

[jokoon]

I'm not sure, but my intuition tells me there's half introverts, half extraverts. (introversion/extraversion is a spectrum).

[andrey-p]

That's actually quite depressing. "You are always surrounded by people who are more popular than you."

[codeka]

I don't think it's as bad as that. It's the mean number of friends, not the median.

The example of twitter makes this a bit more clear: your followers have more followers, on average, than you. But that's because you likely follow someone with a million followers. That one person greatly affects the mean follower count.

So if you follow 10 people, one of whom has 1000 followers, and the rest just have one, the paradox still holds.

[cjensen]

Spin it the other way and you get "people who are popular want to be your friend."

[kstenerud]

Actually, I prefer it that way. Let other people deal with the hassle of dealing with people. My greatest fear is discovering too late that something I'm doing will make me famous.

[cyorir]

Also depressing are some of the corollaries that have cropped up. "On average, you are surrounded by people who are more successful than you." "On average, your (sexual) partners have more partners than you."

[kull]

98% of the time to be more specific

[sjwright]

An even simpler explanation:

Start with the baseline assumption that people are broadly similar to the people they're friends with -- i.e. socialites are friends with socialites, loners are friends with loners.

Overlay that with the observation that you're more likely to be friends with someone who has lots of friends, and less likely to be friends with someone who has few friends.

Consider the extremes: You're certain to be friends with someone who is friends with everyone, and certain to not be friends with someone who has no friends.

[cJ0th]

I don't think it is a paradox when you look at it from a "better" perspective. Just plot a graph displaying the frequency people have x friends. Chances are, there are some outliers with enormous amounts of friends who thus push the average.

I think it is not as much a paradox but rather a good demonstration of how the average can be an inappropriate measure to describe some samples.

[sjwright]

Another simple explanation:

Imagine that there was one single person who was friends with all 7 billion people on Earth. Assuming nobody else had more than about 250,000 friends, this would cause every other person on the planet to have fewer friends than their friends have, on average. That one person skews the mean.

What happens in reality is of course much, much more subtle.

[mariusz79]

Oh, so now I know why I have no friends.. Someone must be at the very bottom of this pyramid. :)

[exo762]

I can be your friend.

The popular one.

xD

[pizza]

Good article by Strogatz, with clear explanation: http://opinionator.blogs.nytimes.com/2012/09/17/friends-you-...

[clairity]

yay for strogatz! he was one of my favorite math profs in school because he really knew how to explain counter-intuitive phenomena like this.

[goblin89]

This is a fun property of scale-free networks in general (https://en.wikipedia.org/wiki/Scale-free_network).

[gitonup]

Head Squeeze did a bit on this a while ago, as applied to Twitter: https://www.youtube.com/watch?v=Z_15zbgNpHk

[Paul_S]

Can you really have more than 1 or 2 friends? You only have two kidneys and a friend is someone you'd be willing to give a kidney to (compatibility aside).

[mehrdada]

Yes. You can oversubscribe your friends to your kidneys. You just have to be willing to give them, but that does not need to actually happen. You'll be fine as long as you pick your friends wisely.

[taliesinb]

When I was working on http://blog.stephenwolfram.com/2013/04/data-science-of-the-f..., a lot of bizarre results (such as a huge gender difference in number-of-friends for people older than 40) went away after I took into account the friendship paradox. It would be really interesting to revisit that anomaly and try to explain why.

[_RPM]

I don't have any friends, am I excluded?

[sjwright]

No, you're just a divide-by-zero error.

[eric_h]

"On-Topic: Anything that good hackers would find interesting. That includes more than hacking and startups. If you had to reduce it to a sentence, the answer might be: anything that gratifies one's intellectual curiosity."[1]

[1] https://news.ycombinator.com/newsguidelines.html

[arjie]

Read the article and you'll find that this is an interesting observation that has current relevance (the Ebola outbreak).

[tbrownaw]

If you drop the needless pejorative language, you get the observation from the second paragraph of the article...

[comrade1]

Should I have used the phrase super-fecund instead of the word 'slut'? Actually, with birth control we fool our bodies into thinking that we're mating so fecundity doesn't apply I guess.

[dangayle]

I've never heard this before. It kinda hurts my brain a little to think about.

[vacri]

If you think about it like a computer network, most nodes have fewer neighbours than their neighbour nodes. Most nodes are endpoints with only a few neighbours, but some nodes are networking midpoints with a lot of neighbours, and every endpoint knows at least one midpoint.

On a network segment with one gateway and ten endpoints, all nodes can see ten other nodes... except the gateway, which can see more nodes outside the segment. The average is therefore higher than ten, so most nodes see less than the average.

Hrm, I'm not sure if that clears it up at all. Maybe :)