How Small is the World, Really?
Social network analysis is back in the news again, with a recent Facebook project which determined that there are an average of 3.5 intermediaries between any 2 Facebook users. But this is different than "6 degrees of separation." Read on to find out why, and how.
By Duncan Watts, Microsoft Research.
Last week’s finding by a team of data scientists at Facebook that everyone in the social network is connected by an average of 3.5 “intermediaries” has renewed interest in the longstanding “Six Degrees of Separation” hypothesis: that everyone in the world is connected by some short chain of acquaintances. Not surprisingly, the attention has focused on the plausible assertion that online social networks like Facebook have made the world smaller: that what used to be six degrees is now almost half that. But really what it has revealed is how little we understand this intriguing phenomenon and what it might mean for our world.
This “small world” hypothesis, as it is known in sociology, has been percolating in popular culture for a long time. Almost a century ago the Hungarian poet Frigyes Karinthy wrote a short story called “Chain Links” in which he claimed he could reach anyone in the world, whether a Nobel Prize winner or a worker in a Ford auto factory, through a series of no more than five intermediaries. Subsequently, writers like Jane Jacobs, John Guare, and Malcolm Gladwell have periodically reinvigorated the idea with their own colorful characters and fantastical speculations about who really runs the world.
But arguably no one has had more impact on the question of how small the world is than Stanley Milgram, a Harvard psychologist who in the 1960s conducted an ingenious experiment to test it (Milgram is even more famous for another experiment of his, on obedience to authority, but that’s for another day). In brief, Milgram chose a single person, an acquaintance of his who was a stockbroker living in Sharon Mass, just outside of Boston, to be the “target” of the experiment. In addition he chose roughly 300 others — 100 from Boston itself and the other 200 from Omaha Nebraska, which Milgram figured was about as far away from Boston, socially and geographically, as one could get within the US.
Milgram then sent these 300 subjects special packets containing a good deal of information about the target — his name, address, occupation, etc. — and also instructions that they were to try to get the packet to him. But there was a catch: they could only send the packet to him if they knew him personally, meaning on a first-name basis. In the overwhelmingly likely event that that they did not, they were instead to send to someone they did know on a first name basis and who was closer to the target than they were themselves. These new participants would then get the same packet with the same instructions, and the process would repeat until — hopefully — some of the packets reached the target.
Milgram’s question then was: for successfully delivered packets, how long would the chains be? Curiously, before he ran the experiment Milgram asked lots of people to guess the answer. Many assumed it wasn’t possible while others figured it would take hundreds of steps. So when Milgram found that not only did 64 packets, roughly one fifth of the initial sample, reached the target, but that the average length of the successful chains was just 6, he knew it would surprise many people.
In many ways, it still does. Although the phrase “Six Degrees of Separation” has become a cliché, when pressed many people still find it difficult to imagine how they could really reach anyone — not just someone like them or someone near to them, but anyone at all in the whole world — in something like six steps. Understandably then, the Facebook result also attracted some resistance: “Facebook is an unrepresentative sample of the population;” “Facebook friends aren’t real friends” and so on. But although these critiques may have merit, they miss the point. In reality, the 3.5 number is simply incomparable to Milgram’s 6 for three reasons.
First, the number 3.5 counts intermediaries not degrees of separation. If I am “one degree” from someone I know them directly; there are zero intermediaries between me and them. Likewise, there is one intermediary between me and my “two degree” neighbors, and so on. In general, therefore, an average of 3.5 intermediaries corresponds to 4.5 degrees of separation, which is almost exactly what Facebook itself found when it performed a similar exercise a few years ago. Conversely, Milgram’s six degrees result corresponds to five intermediaries, which is actually the number he reported in his original paper with Jeffery Travers. So already the difference is one less than it appears.
Second, though, Milgram’s experiment was a subtly but importantly different test than the one run by Facebook. Whereas the latter measured the length of the shortest possible path between two people — by exhaustively searching every link in the underlying Facebook graph — the former is simply the shortest path that ordinary people could find given very limited information about the underlying social network. There are, in other words, two versions of the small-world hypothesis — the “topological” version, which refers only to underlying network structure, and the “algorithmic” version, which refers to the ability of people to search this underlying structure. From these definitions, it follows that algorithmic (search) paths cannot be shorter than topological paths and are almost certainly longer. Saying that the world has gotten smaller because the shortest topological path length is 4.5 not 6 therefore makes no sense — because the equivalent number would have been smaller in Milgram’s day as well.
Finally, the number 6 is also in some respects too small. As has been pointed out many times since Milgram’s experiment, only about 20% of the letters made it to their target. More importantly, these letters were almost certainly on shorter paths than the ones that didn’t make it, meaning that estimates of path length that don’t take into account the missing data are almost certainly biased downwards. Fortunately it is possible to correct for this bias using standard statistical methods. In a 2009 paper my colleagues and I performed exactly this analysis both on Milgram’s original data and also on our data from a similar — but much larger — experiment that we had conducted ourselves in 2003.
Remarkably we found that after the correction, both experiments yielded similar results: the median shortest path was 7, meaning that 50% of chains should complete in 7 or fewer steps while the other 50% would be longer. Many people find this result surprising because it seems so clear that the world has gotten smaller in the last 50 years. Yet this apparent stability is exactly what one would predict from my early theoretical work with Steven Strogatz back in the late 1990’s. In a nutshell what we showed is that it is easy to turn a “large” world into a “small” one, just by adding a small fraction of random, long-range links, reminiscent of Mark Granovetter’s famous “weak ties.” The flip side of our result, however, is that once the world has already gotten small — as it was already by the 1960's — it is extremely hard to make it smaller. Obviously Facebook did not exist in 2003 so possibly since then something has indeed changed. But I suspect that the difference will be small.
Why does any of this matter? There are three reasons. First, the two versions of the small-world hypothesis — topological and algorithmic — are relevant to different social processes. The spread of a sexually transmitted disease along networks of sexual relations, for example, does not require that participants have any awareness of the disease, or intention to spread it; thus for an individual to be at risk of acquiring an infection, he or she need only be connected in the topological sense to existing infectives. On the contrary, individuals attempting to “network” — in order to locate some resources like a new job or a service provider — must actively traverse chains of referrals, and thus must be connected in the algorithmic sense. Depending on the application of interest, therefore, either the topological or algorithmic distance between individuals may be more relevant — or possibly both together. Second, whereas the topological hypothesis has been shown to apply essentially universally, to networks of all kinds, the algorithmic hypothesis is largely (although not exclusively) concerned with social networks in which human agents make decisions about how to direct messages. And third, whereas the topological version is supported by an overwhelming volume of empirical evidence — hundreds of studies, if not thousands — have found that nodes in even the very largest known networks are connected by short paths, the practical difficulty of running “small-world” experiments of the sort that Milgram conducted in the 1960s has meant that much less is known about the algorithmic version.
On this last point, for example, our 2009 analysis also found evidence that some of the longer paths could be much longer than the median, adding weight to the skeptics’ claims that in spite of the small-world phenomenon, some people remain socially isolated. Given the importance of social networks in determining life outcomes, it would be extremely interesting and useful to understand better who these people are and why they are isolated. Is it something to do with their underlying networks or is it that their search strategies are somehow less effective? Could it be, as my coauthors and I speculated many years ago, some kind of self-fulfilling prophecy, in which the perception of social isolation discourages one from searching one’s network, and that the resulting lack of success reinforces the original perception of isolation? Answering these questions would require new experiments that are only now just becoming possible. But the answers would not only be of academic interest — they could also potentially help many people access currently inaccessible reserves of “social capital” thereby improving their lives. Far from being settled, the small-world problem still has much to teach us about the world, and ourselves.
Original. Reposted with permission.
- KDnuggets Interview with Jon Kleinberg, revisited
- The Star Wars social networks – who is the central character?
- How to Visualize your Facebook Network