Posts Tagged ‘erdos number’

Six Degrees of Separation?

August 8, 2008
Photo of Kevin Bacon by SAGIindie (Creative Commons license)

Photo of Kevin Bacon by SAGIindie (Creative Commons license)

The notion of “degrees of separation” is once again in the news, thanks to Microsoft. The basic idea is that you start with someone, look at everyone they know (where “know” would have to be defined in some way), then look at everyone that those people know, and see what happens. Chain letters and pyramid schemes thrive on this sort of thing. The origin of “six degrees of separation” seems to date back to the 1929 short story “Chains” by Frigyes Karinthyin:

One of us suggested performing the following experiment to prove that the population of the Earth is closer together now than they have ever been before. We should select any person from the 1.5 billion inhabitants of the Earth—anyone, anywhere at all. He bet us that, using no more than five individuals, one of whom is a personal acquaintance, he could contact the selected individual using nothing except the network of personal acquaintances.

Musing #1: The 5th root of 1.5 billion is about 68.5. This suggests that each person would need at least 68 personal acquaintances if there was no overlap. But since many people share personal acquaintances, the actual number would have to be a lot higher.

Musing #2: The notion of six degrees of separation was introduced in a work of fiction.

Then there was this paper by Jeffrey Travers and Stanley Milgram in 1969 about an experiment by Milgram in which people in the USA got letters to someone they didn’t know by sending the letters to people they did know, who would send it to people they knew, etc. The average number of people it passed through was 5.2 [so each letter was sent 6.2 times on average to get to the final person] leading to more emphasis on that whole SIX thing.

Problem #1: Here the 6.2 was an average, not a maximum like in the short story above. This distinction is always sometimes pretty much always blurred when degrees of separation are talked about informally.

Problem #2: The 6.2 was the average only of the letters that made it to their destination, and that was only 64 out of 296. In other words, this experiment suggests that two people in the US would be 6.2 steps on average away from each other if they’re connected at all, but they probably aren’t.

Problem #3: The title “Infinite Degrees of Separation” isn’t so catchy, and is a little depressing.

Problem #4: This is the same Stanley Milgram who conducted the infamous Milgram Experiment in which volunteers gave supposed electric shocks to supposed volunteers in response to mistakes. Not that this has anything to do with the Small World theory, but it was a surprise to me that it was the same guy.

Moving along, the degrees of separation results were repeated in the Small World Project through Columbia University and published here in 2003. As explained in the abstract:

We report on a global social-search experiment in which more than 60,000 e-mail users attempted to reach one of 18 target persons in 13 countries by forwarding messages to acquaintances.

This was worldwide, not just the USA, and with much bigger numbers, and yours truly actually participated in it. It led to some interesting results:

Result #1: Of the completed chains, the median number of steps was 4.05, though the authors conjectured that overall the median number of steps is probably five to seven. This lead to headlines like “Email experiment confirms six degrees of separation“.

Result #2: The participants were not a random sample. From the article above: “More than half of all participants resided in North America and were middle class, professional, college educated, and Christian” In theory, I think only the starting and ending points would have to be random, but here the starting and ending people did need to have internet access and I’d question whether or not internet access is truly independent of social connectedness internationally.

Result #3: The average is, once again, based only on completed chains. And out of the 24,163 chains, only 384 were finished. In other words, most people don’t seem to be connected. Either that or we’re just lazy — there’s some evidence for that in the paper: if people couldn’t think of a good person to pass the email along to, they didn’t pass it along to anyone.

Then in June 2006 Microsoft got in on the action. They looked at all the Instant Messenges that month and counted folk as connected if they exchanged at least one IM. The average degrees of separation was 6.6, which lead to recent headlines like, “Everyone really is just six degrees of separation from Kevin Bacon” with the subheader, “A study of Microsoft’s instant messaging network supports the popular idea that everyone on the planet can be connected through fewer than seven links in a chain of contacts.”

Misconception #1: Once again, the six degrees, which was really more like seven, is an average and not a maximum. Microsoft did find that 78% of users could be connected in seven stages or less, but they also said that some pairs were separated by 29 degrees. Actually, what might be the most interesting bit to me is that the news articles I looked at (on Yahoo! News and The Washington Post) imply that everyone was connected in some way, which is very different from the results of the previous study.

Misconception #2: I think it’s a stretch to claim that Microsoft IM users are representative of everyone on the planet, and I’d be wary of claims like the headline above that extrapolate it to every single person.

But despite the limitations of studies like this, if you limit yourself to certain subsets of people, you still can have some fun. For example:

Related Website #1: The Oracle of Bacon. This site allows you to choose an actor and see that actor’s “Bacon Number” (their degrees of separation from Kevin Bacon). For example, if you pick Christina Mastin, you find:

Christina Mastin has a Bacon number of 2.

Christina Mastin was in Dogfight (1991) with Brendan Fraser
Brendan Fraser was in Air I Breathe, The (2007) with Kevin Bacon

You can also choose the Advanced Setup to search for a path linking any two actors. Incidentally, the notion that all actors are connected to Kevin Bacon appeared around 1994, and last year Kevin Bacon started a charitable giving organization called, which is a nice thing even though Kevin himself claims on the site that the six degrees of separation is a maximum and not an average. (You might want to correct that, Kev. But still, kudos for the charity work.)

Related Website #2: The Erdös Number Project. This site studies collaboration among mathematicians, many of whom have co-authored a paper with someone who co-authored a paper with someone who co-authored a paper with Paul Erdös. For example, Natalie Portman has an Erdös number of 5: she published a psychology paper (as Natalie Hershlag) with Abigail A. Baird, who published a paper on Functional Connectivity with M.S. Gazzaniga, who published a paper on Acquired central dyschromatopsia with J.D. Victor, who published a combinatorics paper with J. Gillis, who published a paper on transfinite diameter with Paul Erdös. Incidentally, Natalie currently has a Bacon number of 2 but this coming February she and Kevin are both appearing in the movie New York, I Love You, giving Natalie an Erdös-Bacon Number of 6 (5+1).

Related Website #3: The six degrees of celeb dating. This site is a game, so it gives you two people and you have to fill in the dating chain yourself. The site will, however, tell you if you’re right and it gives you a limited number of celebrities to choose from: I was able to tell that Drew Barrymore dated Edward Norton who dated Salma Hayek in only about ten guesses. If that’s too much work or if closed cycles interest you more than chains, you can see a twelve-step dating cycle starting and ending with Brad Pitt on cbs2chicago.