Small-world networks

What you're seeing

Every node starts wired only to its nearest neighbors on a ring — an ordered lattice. It has two honest properties. First, it takes many hops to cross the ring — a long average path length: the mean number of links on the shortest route between every pair of nodes. Second, any two friends of a friend are usually friends themselves — high clustering: how often a node's neighbors are also neighbors of each other. Drag the dial and each edge gets, independently, a small chance of being torn out and reattached to a uniformly random node anywhere on the ring. That is a "shortcut" — drawn in amber, cutting straight across the circle instead of hugging its rim.

Watch the amber path-length line in the lower chart: it falls off a cliff in the first sliver of the dial, while the cyan clustering line barely moves. A rewiring rate of just 1% already collapses the average distance to under two-thirds of its ordered value — and local clustering is still above 90% of what it was. That gap — short paths and tight local cliques, at the same time — is the "small world". It is Watts & Strogatz's 1998 answer to why acquaintance networks, neurons and power grids can all be crossed in a handful of hops (the folk claim of "six degrees of separation") even though almost everyone knows only their immediate neighbors. Keep dragging toward 1 and the shortcuts pile up until almost nothing is left of the original ring — clustering keeps falling toward zero even as path length has nowhere further to go.

It isn't randomness alone that does this. A network wired entirely at random, with the same number of links as the ring, gets the short paths for free — but never the high clustering (verified below). The small-world effect needs both ingredients: an ordered base to keep local structure, and only a few long-range shortcuts layered on top.