What is the small-world effect behind six degrees of separation?

The small-world effect is the observation that in many large networks, the average number of hops between any two nodes is small, even though the nodes also form tight local clusters. The popular phrase "six degrees of separation" is the best-known version of this idea for human acquaintance networks. According to plus.maths.org, these two features, short average distance and many local clusters, define what mathematicians call a small world network. [1]

The first significant empirical study was by the social psychologist Stanley Milgram. He asked randomly chosen starter individuals to forward a letter to a target person in Sharon, Massachusetts, a suburb of Boston, passing it only to an acquaintance they knew on a first-name basis. Roughly a third of the letters arrived, in a median of six steps. Similar experiments have since been repeated by other groups, according to the networks textbook by Easley and Kleinberg hosted at Cornell. [2]

That text says the experiment showed two things: short paths exist in abundance, and people with no global map of the network are effective at collectively finding them. [2]

In the late 1990s, Duncan Watts and Steven Strogatz built a simple model. They began with a ring in which each person is linked only to nearby neighbours. That network is highly clustered, but for large networks the average path between random pairs is very long. They then randomly rewired some links, keeping one end fixed and moving the other to a random node. Because most of the network is far from any given node, a rewired link is likely to join two otherwise distant clusters. A little rewiring shortened average paths without destroying the clusters. [1]

Kleinberg and Easley describe the same idea in social terms. Homophily, the tendency to link to similar people, creates many triangles of mutual friends. Weak ties, links to acquaintances in otherwise far-off parts of the network, supply the widely branching structure that reaches many people in few steps. Even if only a small fraction of people have a single long-range link, short paths still exist between all pairs. [2]

For a completely random network where each node links to k others, the average distance is proportional to ln(N)/ln(k), with N the number of nodes. Distances grow only logarithmically with size, which is why even very large networks stay small. [1]

The small-world property itself is well documented: a physics paper in Physical Review X notes that real-world networks show distances scaling logarithmically with size. The same paper says why social networks have an ultrasmall-world organization, with diameter independent of network size over several orders of magnitude, is still unknown. Its authors propose an answer: the property emerges at equilibrium when individuals weigh their aspiration for centrality against the costs of forming and maintaining connections. This is one proposed explanation from the results, not an established consensus. [3]

The number six should also be read loosely. It comes from the median in Milgram's experiment, in which only about a third of letters arrived, and it has become a popular shorthand rather than a fixed law. [2]