Small-World Networks

Small-world networks are graphs that simultaneously exhibit high clustering (neighbors of a node tend to be connected to each other) and short average path lengths (most pairs of nodes are reachable in a small number of steps). The combination was formalized by Watts and Strogatz (1998), who showed that a simple interpolation between regular ring lattices and random graphs passes through a region with both properties: the small-world regime.

The small-world property had been anticipated by Milgram's 1967 chain-letter experiments, which suggested that any two Americans could be connected through a chain of roughly six acquaintances — the origin of the phrase "six degrees of separation." Watts and Strogatz gave this intuition a graph-theoretic foundation and demonstrated that small-world structure appears in empirical networks ranging from power grids to the neural wiring of C. elegans.

What the small-world result does not establish is why short paths matter dynamically. Short paths are a topological property; whether information, disease, or influence actually travels along shortest paths depends on the dynamics, not the topology. The field's enthusiasm for the small-world finding often outruns this distinction.