Are there any studies that prove (or disprove) the idea of “Six Degrees of Separation”?

Question

Is it true that anyone on the planet is connected to any other person on the planet through six degrees of separation? Why, or why not?

Answer 1

Well, it just so happens that there has been an experiment done on this. The original study was from Milgram back in the 1960s (same guy that did shock experiments). Orginal paper can be found here: http://www.cis.upenn.edu/~mkearns/teaching/NetworkedLife/travers_milgram.pdf However, the results are contentious. A Dr. Judith Kleinfeld has a good rundown on this. Her abstract starts out:

The idea that people are connected through just "six degrees of separation," based on Stanley Milgram's "small world study," has become part of the intellectual furniture of educated people. New evidence discovered in the Milgram papers in the Yale archives, together with a review of the literature on the "small world problem," reveals that this widely-accepted idea rests on scanty evidence. Indeed, the empirical evidence suggests that we actually live in a world deeply divided by social barriers such as race and class. An explosion of interest is occurring in the small world problem because mathematicians have developed computer models of how the small world phenomenon could logically work. But mathematical modeling is not a substitute for empirical evidence. At the core of the small world problem are fascinating psychological mysteries

She concludes with:

Nothing is so useful as a good problem. The "small world problem" remains eternally fascinating and even more so in the digital age. Milgram has not shown that we live in a world of "six degrees of separation." How we are connected to each other remains an important mystery....and a researchable one.

I also recall watching a television program a while back where Mark Vidal of the Faber Institute distributed packages all over the world with instructions on how to get the package back to him by only sending it to people you knew (basically a repeat of the Milgram study). I do recall that he did get his packages back, and often in less than six steps. Although that may have been assisted for the TV show's production values.

I also found this paper from Cornell (The Small-World Phenomenon: An Algorithmic Perspective) that starts out as:

Long a matter of folklore, the "small-world phenomenon" -- the principle that we are all linked by short chains of acquaintances -- was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960's. This work was among the first to make the phenomenon quantitative, allowing people to speak of the "six degrees of separation" between any two people in the United States. Since then, a number of network models have been proposed as frameworks in which to study the problem analytically. One of the most refined of these models was formulated in recent work of Watts and Strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the World Wide Web.

This paper makes a more mathematical look at it versus an experimental look, and thus concludes:

Algorithmic work in different settings has considered the problem of routing with local information; see for example the problem of designing compact routing tables for communication networks [15] and the problem of robot navigation in an unknown environment 3. Our results are technically quite different from these; but they share the general goal of identifying qualitative properties of networks that makes routing with local information tractable, and offering a model for reasoning about effective routing schemes in such networks. While we have deliberately focused on a very clean model, we believe that a more general conclusion can be drawn for small-world networks: that the correlation between local structure and long-range connections provides fundamental cues for finding paths through the network. When this correlation is near a critical threshold, the structure of the long-range connections forms a type of "gradient" that allows individuals to guide a message efficiently toward a target. As the correlation drops below this critical value and the social network becomes more homogeneous, these cues begin to disappear; in the limit, when long-range connections are generated uniformly at random, our model describes a world in which short chains exist but individuals, faced with a disorienting array of social contacts, are unable to find them.

I also found some further studies, however, the sites require subscriptions: http://www.eric.ed.gov/ERICWebPortal/search/detailmini.jsp?nfpb=true&&ERICExtSearch_SearchValue_0=EJ744252&ERICExtSearch_SearchType_0=no&accno=EJ744252

So as I started off with, the results are contentious. A final conclusion may need more research.

Answer 2

Béla Bollobás, who is famous for having studied the properties of random graphs/networks with Paul Erdős (note Zenon's comment above), discovered loose bounds on the diameter of random regular graphs. He proved the following:

Theorem 1 (of this paper) Let r ≧ 3 and ε > 0 be fixed and define d = d(n) as the least integer satisfying (r-1)^d-1 ≧ (2+ε)rn log n. Then a.e. r-regular graph of order n has diameter at most d.

In our case, n would be the world population, which we can estimate at 6.93x10⁹. The parameter r would be the minimum number of connections per person, which I think we can estimate at 130 (based on statistics from Facebook). Plugging in those values and solving for d we get

d ≧ 1 + 0.2057692596 log(0.4082721260e14 + 0.2041360630e14 ε).

This bound strictly increases as ε → ∞, so taking the limit as ε → 0 gives us the least d that satisfies Theorem 1:

⌈ lim_ε→0 1 + 0.2057692596 log(0.4082721260e14 + 0.2041360630e14 ε) ⌉ = 8.

Therefore, by Theorem 1, the diameter of a graph on 6.93x10⁹ vertices with degrees at least 130 almost surely has a diameter of at most 8.

According to Bollobás, this bound could even be sharpened (meaning that it is likely the actual value is lower than 8). The bound will of course also be tighter if people actually have more than 130 connections. Also note that this is a bound on the maximum degree of separation between people; the average degree would likely be much lower.

Summary: In a population of 6.93x10⁹ in which each person is connected to at least 130 others, it can be said with extremely high confidence that the largest degree of separation between any two people is at most 8.

---

If we assume that the number of connections per person, r, remains constant at 130, then we can set d to 9 and solve for n to get an estimate on the size of the population when the maximum degree of separation will increase. This will happen when the population is just under 10 Trillion. Assuming our current rate of population growth remains constant at about 1.14% per year, our population should reach 10 Trillion in about 640 years. Therefore, I conjecture that in the year 2651 we will have to create the "Seven Degrees of Separation Game"! ;-)

Answer 3

Well since the graph is disconnected (that is, there are tribes of people who still have had no contact with the outside world), this statement can't be true, since there is no way to reach them from any of us.

Answer 4

Microsoft has performed an analysis of their IM network. They wrote:

We investigate on a planetary-scale the oft-cited report that people are separated by “six degrees of separation” and find that the average path length among Messenger users is 6.6.

Paper is available online: Planetary-Scale Views on an Instant-Messaging Network

Answer 5

Those are further readings in the matter.

http://en.wikipedia.org/wiki/Erd%C5%91s_number

http://en.wikipedia.org/wiki/Bacon_number

http://en.wikipedia.org/wiki/Morphy_Number

Unfortunately, ibeatgarry.com is unavailable now, one was able to search the shortest chain he beat Garry Kasparov by (if I remember correctly) the Mega Database delivered by chessgames.com. My Kasparov-number was infinite when I checked it years ago (no beating way existed), I'm sure it is less now. The strongest player (~2100-2200 ELO-points) in my then-club had 5 or 6, I can't remember. But my non-beating, only playing number is 3, it seems to be extremely few. Kasparov -> Korchnoi -> Kádas -> me. I can't find the Korchnoi-Kádas match, but Gábor Kádas told me they played once. And I played with Gábor in 2007, if I remember correctly, but it is impossible to find, it happened in an unofficial rapidchess event. (Trivia: I lost that match! :))

Answer 6

It depends on what you mean by connected.

If you believe (and the numbers make sense) that we have all had air in our lungs which was also in those of Genghis Khan, for example, and you call that a connection, 6 is much greater than the real number, and everyone alive is probably connected by molecules directly or via one other person.

Example equation, referring to Caesar: http://www.j-bradford-delong.net/movable_type/archives/001392.html

If a connection means "having had a conversation with, in person" it's harder.

Another thing which needs to be addressed is the variety of social networks involved. One person has the internet, another person lives as a hunter-gatherer in the jungle. Boundaries also need to be taken into account. A North Korean citizen and a French citizen do not have the same chance of having a connection in India. French citizens have free access to internet, can leave their country at will, unlike citizens of North Korea.

Taking Milgrams case of the café in Tunisia, well it's a poor example. Both of the parties in conversation are privileged enough to travel to Tunisia from their respective homelands, which puts them in a minority, or a given class, if you're so inclined. Remember the case is in the 60's before the advent of high-volume, lower-cost flights. On top of that, their mutual connection, owning a chain of supermarkets, will have far greater influence than the average person, and is a far from typical case. However it does give an interesting lead in what may be the quickest way to find a connection.

If you have an algorithm where you take a person, then look for the most influential person they know, and repeat that for the next two connections, you should have a huge range of options available to you. You might want the remaining steps to focus on the individual at the other end.

So if you think having had the same molecules in your lungs is a connection, yes it is true. If not, it's probably a lot more complicated than has been suggested.