28

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?

17
  • 3
    In general, as stated below by @Larian LeQuella, it may be hard to tell. But in particular in the mathematic field, there is the Erdos number (en.wikipedia.org/wiki/Erdos_number) that shows the connections between co-authors and Erdos (a really, really, prolific mathematician, who had many, many co-authors). It is hard to find someone who has a degree higher then 5-6.
    – Zenon
    Apr 6, 2011 at 3:19
  • 3
    You can make a very broad estimate using spectral graph theory. Let us simply assume that everyone knows exactly x persons. This means the graph is x-regular. Then, the second smallest eigenvalue of its laplacian is at least x - 2sqrt(x). Since it's also at most x, we can get some approximate results by setting the value just to x. Then there's an upper bound on the diameter of the graph using x, which will tell you that the diameter is at most the natural logarithm of the number of nodes. I plugged in some numbers: If everyone knows exactly 100 other people, then...
    – Lagerbaer
    Apr 6, 2011 at 3:43
  • there can be at most 30 degrees of separation. If you increase x, then the bound drops, but doesn't become smaller than 22, so this is the "best" I can show with this very(!) crude model. It would remain basically intact if every person knew "at least" x other persons, though. Since it's just fun with mathematics, I did not post this as an answer.
    – Lagerbaer
    Apr 6, 2011 at 3:43
  • 1
    @Lagerbaer: If 99 of the people person A knows is also known by person B, he only knows 1 additional person. With that pattern there would be billions of degrees of separation. :) Apr 6, 2011 at 12:22
  • Yep, but this would be a very special regular graph. For "most" regular graphs this will not be the case.
    – Lagerbaer
    Apr 6, 2011 at 14:49

6 Answers 6

28

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.

6
  • 1
    Soo... Looks like all this simply means "There are studies and although the idea seems reasonable nothing proves or disproves it nor the number 6 in it".
    – cregox
    Apr 6, 2011 at 7:23
  • 7
    A final conclusion at the end of the answer would be beneficial. Apr 6, 2011 at 8:22
  • 3
    There is no final conclusion... As I said, "the results are contentious". Apr 6, 2011 at 10:26
  • 1
    I remember that documentary you mentioned. It can be watched on Youtube: youtube.com/watch?v=RcCpEf6_Ofg&feature=related
    – Oliver_C
    Apr 6, 2011 at 11:18
  • 2
    Monty Hall is keeping the definitive proof behind one door, and behind the other two doors, nothing but goats....... Apr 6, 2011 at 22:03
13

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.93x109. 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.93x109 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.93x109 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"! ;-)

8
  • But how many of your friends/colleagues are random people chosen uniformly from the world's entire population, and how many of your friends/colleagues are people who live near the areas you live/have lived, and are also friends/colleagues with one-another? Apr 6, 2011 at 16:40
  • 1
    Bollobás's theorem applies to all (well, to be technical, "almost every") r-regular graphs, not just ones that conform to the Erdős–Rényi model. In other words, we aren't making any assumptions on the topology of the network other than its minimum degree.
    – ESultanik
    Apr 6, 2011 at 16:50
  • 1
    Let's assume, conservatively, that there are at least 6 billion people in the population's largest connected component. Then the bound on the degrees of separation for that largest component is still 8.
    – ESultanik
    Apr 6, 2011 at 17:06
  • 4
    I don't think this really applies at all. You are making two incorrect assumptions: that the graph is random (which it isn't, people tend to cluster and thus most of the 130 connections are also reversed), and that any pair of persons has equal chances of being connected. A simple counterexample: people from a tribe on a pacific island might be isolated from the external world. The real graph may be disjointed.
    – Sklivvz
    Apr 7, 2011 at 6:49
  • 1
    As I mentioned in the second comment in this thread, Bollobás's theorem applies to all r-regular graphs. While his analysis does make the explicit assumption that the graph is random (which is a common tool in combinatorics), he only assumes that all graphs are equiprobable in the space of all r-regular graphs. That assumption is ultimately rendered moot by the strength of his result that almost all r-regular graphs—regardless of whether or not they are random—have this bounded diameter. I also addressed the counterexample you give in the fifth comment in this thread.
    – ESultanik
    Apr 11, 2011 at 14:55
11

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.

1
  • 1
    While that's true, some might argue that the six degrees of separation claim might still hold for the population's largest connected component.
    – ESultanik
    Apr 6, 2011 at 17:01
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

2
  • Note that people with IM are generally more connected than farmers in rural Africa, for example.
    – Sklivvz
    Apr 9, 2011 at 1:00
  • 1
    @Sklivvz: Yes, I understand. Still, to my knowledge, this is the only study which analyzed this amount of real human relationships.
    – liori
    Apr 9, 2011 at 21:44
1

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! :))

1
  • 1
    Wikipedia alone is not considered an authoritative reference for answers. Please add links to more authoritative resources! :-)
    – Sklivvz
    Apr 6, 2011 at 23:06
1

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.

2
  • Welcome to Skeptics! This answer is not properly referenced. Please add citations to support your claims! :-)
    – Sklivvz
    Apr 6, 2011 at 23:05
  • The air thing? I thought it was well known, but I've added a link to the example equation, for what it's worth.
    – puppybeard
    Apr 7, 2011 at 9:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .