Small-World Networks: From Ordered Lattice to Random Shortcut

Two extremes, and the surprise in between

Take n points arranged on a ring and connect each one to its k nearest neighbours. This regular lattice is highly clustered — your neighbours are also neighbours of each other — but it is slow to cross: reaching a point halfway around the ring takes roughly n/2k steps. Now rewire every edge to a uniformly random endpoint instead. This random graph (Erdős–Rényi) is the opposite: barely any clustering, but the average shortest path between any two nodes collapses to about log(n)/log(k), because random long-range shortcuts appear almost immediately.

In 1998 Duncan Watts and Steven Strogatz asked what happens in between, and the answer explained something that had puzzled sociologists since Stanley Milgram's 1967 "six degrees" letter-passing experiment: real social networks are both highly clustered and have short paths, which the two textbook extremes could not explain together.

The rewiring procedure

The Watts-Strogatz construction starts from the ring lattice and then, for each edge, rewires it to a random new endpoint with probability p, keeping the graph connected:

for each node i in the ring:
  for each of its k/2 clockwise edges (i, j):
    with probability p:
      pick a random node j' not already adjacent to i
      replace edge (i, j) with edge (i, j')

At p = 0 nothing is rewired: pure lattice, high clustering coefficient C, long path length L. At p = 1 every edge is randomised: pure random graph, low C, short L. The interesting regime is a narrow window of small p — often just a few percent of edges — where L collapses almost to its random-graph value while C barely drops from its lattice value. A handful of rewired long-range edges is enough to punch shortcuts across the whole ring, while most of the local clustering that those few edges didn't touch survives untouched.

Measuring it: C and L

The clustering coefficient of a node is the fraction of its neighbour pairs that are themselves connected — how many of your friends know each other. The average path length L is the mean number of hops on the shortest path between all node pairs. Watts and Strogatz showed that as p increases from 0, L drops steeply almost immediately (a few long-range shortcuts affect enormous numbers of shortest paths), while C decreases only gradually, roughly linearly with p, since most triangles are untouched by the sparse rewiring.

C(p) / C(0)  and  L(p) / L(0)   plotted against p (log scale)
p=0.0001 : C/C(0) ≈ 1.00   L/L(0) ≈ 1.00   (still a lattice)
p=0.01   : C/C(0) ≈ 0.95   L/L(0) ≈ 0.20   (small-world regime)
p=1.0    : C/C(0) ≈ 0.02   L/L(0) ≈ 0.04   (random graph)

Why it matters beyond social graphs

The small-world property turns up in neural wiring (the C. elegans connectome, cortical networks), the power grid, food webs, citation networks and the World Wide Web's hyperlink graph. It matters practically because it explains fast spreading with local structure intact: an epidemic, a rumour or a cascading power failure can traverse a small-world network in very few hops even though most of the graph still looks locally clustered and orderly. Designing networks (or interventions) that deliberately add or remove a few long-range links has an outsized effect on global reachability precisely because of this p-sensitivity.

Frequently asked questions

Try it live

Everything above runs in your browser — open Small-World Networks and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.