Seven Degrees of Separation

In the year 2651 we will have to create the "Seven Degrees of Separation Game"!

Tagged: Math Theories

Is it true that everyone on earth is separated by at most six degrees? There's plenty of empirical evidence to support this claim already, so I am going to take a different, more theoretical approach.

Béla Bollobás, who is famous for having studied the properties of random graphs/networks with Paul Erdős (who is himself famous, among other things, for his degrees of separation from other mathematicians), discovered loose bounds on the diameter of random regular graphs. He proved the following:

Theorem 1 (of this paper) Let $r \geq 3$ and $\epsilon > 0$ be fixed and define $d = d(n)$ as the least integer satisfying $(r-1)^{d-1} \geq (2+\epsilon)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 \geq 1 + 0.2057692596 \log(0.4082721260\mbox{e}14 + 0.2041360630\mbox{e}14 \epsilon).$

This bound strictly increases as $\epsilon \rightarrow \infty$, so taking the limit as $\epsilon \rightarrow 0$ gives us the least $d$ that satisfies Theorem 1:

$\left\lceil\lim_{\epsilon\rightarrow 0} 1 + 0.2057692596 \log(0.4082721260\mbox{e}14 + 0.2041360630\mbox{e}14 \epsilon) \right\rceil = 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.

In 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.

Now, at this point you might be saying to yourself: The real world social network is not a random graph! While Bollobás’s 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. The beauty is that 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. But there are certainly some tribal cultures that still exist that have little or no contact with the rest of the world, right? Well, 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.


Now, on to the punchline.

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"!

← Older Post Blog Archive Newer Post →