Six degrees of separation

One mathematical idea that has made it into mainstream popular culture is that of six degrees of separation or six degrees of Kevin Bacon.  The idea is that any two people on Earth are likely to be linked by six steps in terms of acquaintance. That includes you and the King of England, you and the actor Kevin Bacon and you and the mathematician Paul Erdős.  

The idea originated in an experiment conducted in the 1960s by the sociologist Stanley Milgram, who is perhaps better known for another, more sinister, run of experiments designed to understand the horrific actions committed by thousands of "ordinary" German citizens during the holocaust.  Milgram found that a shocking number of volunteers were prepared to administer what they thought were deadly electric shocks to pretend test subjects, purely on the grounds that an authority figure had asked them to. 

Milgram's small world experiment was of a far less depressing nature. He wanted to investigate something many of us have experienced: you meet someone far from home and to your surprise it turns out you share a mutual friend or acquaintance.  This common experience inspired the small-world problem: can you link any two people by a short chain of mutual acquaintances? And how long is such a chain?  

To investigate this Milgram randomly selected people from the suitably far away state of Nebraska and asked them to pass on a letter to a target person in Boston (Milgram was at Harvard, just up the road) via a chain of friends and acquaintances.  If they didn't know the target person personally, they were asked to send the letter to someone they knew on a first name basis who they thought would be closer to the target. Although only a small proportion of the letters made it all the way, the average number of links in the chains that did was 6: and the idea of 6 degrees of separation was born. The idea  was so surprising that it inspired a broadway play (which coined the phrase "six degrees of separation"), a movie, a TV show and even a charitable social network.  

Small worldness

Today we are more aware than ever that our lives are played on and through networks: as well as social networks there are infrastructure networks such as the power grid, water and transportation networks, the physical network of computers and the virtual network of web pages that makes up the internet, even biological networks of neurons in the brain and metabolic processes within our cells.  All of these networks are a collection of nodes – people, power stations, computers or neurons – connected by links – friendships, power lines, wifi and internet cables, and neural connections.  And all of these networks appear to exhibit a similar structure. The average distance between nodes, measured as the number of hops it takes to get from one node to another, tends to be small.  They also all tend to have lots of local clusters: if two nodes are connected to each other, their other connections tend to be connected too. These two features define what mathematicians call a small world network.

Why are these small world networks so ubiquitous? Within social networks you would expect lots of local clusters – friends of friends tend to make friends. At the same time,  acquaintances can form in airports and illicit flings on holiday, loosely linking distant groups. This intuition is reflected in a model developed in the late 1990s by the mathematicians Steven Strogatz and Duncan J. Watts. Watts was inspired by his own experience, having moved to Cornell University in the US from his home in Australia to take a PhD with Strogatz.  His decision to move across the world suddenly linked together two otherwise distant groups of people, his friends in Australia and in Cornell.

To try to model small-world networks Watts and Strogatz did what mathematicians often do. They started with simplest setup they could find: a ring of friendships where people were only friends with a specified number of nearest neighbours.  Such a network is highly clustered but the average path length between random pairs of nodes is very long, at least for large networks.

Watt and Strogatz then started rewiring their neighbourly network, randomly reconnecting some of the links, keeping one end of the link fixed and connecting the other end to a randomly chosen node. Because most of the network isn't in the near neighbourhood of any one node, it's very likely that the rewiring will connect two otherwise disconnected clusters, drastically shortening the path between them.  It turned out that only a little bit of random reconnecting sufficed to make the average path between nodes shorter without destroying the local clusters: a few "shortcuts" between previously distant nodes were enough to make their networks small-world.

The number of hops it takes, on average, to get from one node to another in such a model for a small world network depends on the total size of the network and the number of nodes a given node is connected to. In a completely random network, in which each node is connected at random to $k$ others, the average distance between two nodes is proportional to $ln(N)/ln(k)$, where $N$ is the total number of nodes. Such a network is what you'd get if you took the random  rewiring to the extreme. But what Strogatz and Watts found is that you don't have to rewire too many nodes in the initial "large-world" network before the average path length drops quite rapidly towards this limiting value. 

Degrees of separation in context

To put this into context, the current world population is roughly 8 billion. If you discount 15% for people whose social patterns are atypical, because they are babies, too old or unusual in other ways, you are left with 6,800,000,000 people. Assuming that each person has 35 acquaintances on average (this is a wild guess not based on evidence) we can estimate the average distance between two people in acquaintance terms as $ln(6800000000)/ln(35) \approx 22.5/3.55 = 6.37.$

Several years after the discovery of this surprisingly simple mathematical explanation for the small-world phenomenon Watts took his mathematical know-how to the sociology department of Columbia University where he became a professor. In 2001 Watts and his Columbia colleagues conducted a modern version of Milgram's experiment, this time using the internet rather than snail mail.  They recruited over 60,000 people from 166 different countries to reach 18 different target recipients including a professor in the US, a tech consultant in India, and a policeman in Australia.  

As before they were asked to reach their target by passing on an email (in place of the paper letter) to a friend or acquaintance who they thought was closer to the target.  And accounting for the rate of dropouts, this experiment again found that the average number of steps in the email chain was around 6. Studies of online social networks have come up with slightly different number, presumably due to the ease with which people connect here, for example around  3.4 for X and 4.5 for Facebook — it seems the Internet really does make the world smaller.

About this article

 

Rachel Thomas and Marianne Freiberger are the editors of Plus. This article is an edited extract from their book Numericon: A journey through the hidden lives of numbers.