In 1929 Frigyes Karinthy set out the idea that all living things, and everything else in the world, is six or fewer steps away from each other. This meaning in a string of “friend-of-a-friend”, any two people is connected with the maximum of six steps [1].
From “shrinking world” to “small world”.
After World War 1, theories on optimal design of cities, city traffic flows, neighborhoods and demographics were in the wind. Karinthy published a series of short novels, where one piece titled “Chain-links” investigated – in abstract, conceptual, and fictional terms – many of the problems that would later engage generations of mathematicians, sociologists and physicists within the field of network theory. Friendship networks could grow larger and span greater distances due to technological advances in communications and travel. Karinthy argued that the modern world was “shrinking” due to this increasing connectedness of human beings, and despite of great physical distances between the globe’s individuals, the growing density of human networks made the actual social distance far smaller. In his story, the characters believed that any two individuals could be connected through at most five acquaintances, and they created a game out of this notion [1]:
A fascinating game grew out of this discussion. 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 [2].
Several studies have been conducted to measure this connectedness empirically since then. One of them was Milgram’s small world experiment from 1961. He sent a package to randomly selected individuals in the US, with information on how to forward it. He then sent it to one of his acquaintances, along with the information to pass it forward to the addressee. If the receiver did not know the target himself, he was to forward it to an acquaintance who were likely to know the target. Among these chains of tries, the average path length fell among five and six [3]. His experiment was attempted recreated on the internet in 2001 by Duncan Watts. He used an e-mail as the “package”, with 48.000 senders and 19 targets in 157 countries. Watts found that the average number of intermediaries was around six [4].
From “small world” Facebook and social media.
In 2016, “the Guardian” published an article on how Facebook brings to world three-and-a-bit degrees of separation closer. The social media platform used its friend graph to calculate the degrees separating its 1.6 billon users and found it to be as few as 3.57 people [5]. This means that every person in the world is connected to every other person by three and a half other people. At least among those of us with Facebook-accounts, but findings from the Pew Research Centre in 2015 indicate that upwards of 72% adults are active online [6]. The distance is getting smaller as we speak too, as more people are signing up to the platform. As of the third quarter of 2017, Facebook had 2.07 billion monthly active users [7].
Three-and-a-half-degree separation calculation.
Calculating degrees of separation in a network with hundreds of billions of edges is a monumental task, because the number of people reached, grows very quickly with the degree of separation. For every person with 100 friends, each of his friends has 100 friends, then friends-of-friends will be 10.000. Add Friends-of-friends-of-friends and we are up to 1.000.000. And most people on Facebook have more than 100 friends. As friends will overlap, the calculation needs to be filtered down to unique connections. The computation needs to be run 1.6 billion times, for every person on Facebook [8]. This was done by statistical algorithms developed by Kang et al [9], to estimate distances with great accuracy, finding the approximate number of people within 1, 2, 3 and so on, hops away from the source. More precisely, for each number of hops we estimate the number of distinct people you can reach from every source. This estimation can be done efficiently using the Flajolet-Martin algorithm [10]. It can be repeated recursively to estimate the number of unique friends-of-friends, and then friends-of-friends-of-friends. Together with the Apache Giraph [11], Edunov et al [8] could run this computation on the entire Facebook friendship graph. In summary, they found that the world is more connected than we might think.
References:
[1] https://en.wikipedia.org/wiki/Six_degrees_of_separation#cite_note-karinthy-3
[3] https://en.wikipedia.org/wiki/Small-world_experiment
[4] http://worrydream.com/refs/Watts-CollectiveDynamicsOfSmallWorldNetworks.pdf
[6] http://www.pewinternet.org/2015/08/19/the-demographics-of-social-media-users/
[7] https://www.statista.com/statistics/264810/number-of-monthly-active-facebook-users-worldwide/
[8] https://research.fb.com/three-and-a-half-degrees-of-separation/
[9] http://www.cs.cmu.edu/~ukang/papers/CentralitySDM2011.pdf
[10] https://en.wikipedia.org/wiki/Flajolet–Martin_algorithm