Rewire a ring lattice with probability p — average path length drops fast, clustering stays high
Network (ring layout)
C(p)/C(0) and L(p)/L(0) vs log p
—Clustering C(p)/C(0)
—Path length L(p)/L(0)
—Rewiring p
Watts-Strogatz (1998): start with N nodes in a ring, each connected to k nearest neighbors. Rewire each edge with probability p.
For small p: high clustering (like a lattice) and long path length. For large p: low clustering and short path length (like random).
The small-world regime (p ≈ 0.01–0.1): path length L drops dramatically while clustering C remains high.
Six degrees of separation, neural connectivity, power grids, and social networks all show small-world structure.