Watts-Strogatz Small-World Rewiring

Interpolate between regular lattice (p=0) and random graph (p=1).
Small-world: short paths AND high clustering coexist.


Parameters

Clustering C: —
C/C₀: —
Avg path L: —
L/L₀: —
Watts-Strogatz 1998 (Nature):
At small p, L drops fast
but C stays high — the
"small-world" regime.

Six degrees of separation
→ L ≈ log(N)/log(k)