Six handshakes to anyone on Earth. A regular ring where each node knows only its near neighbours is heavily clustered but has to travel far; a purely random graph gets everywhere fast but has no clusters. Rewire just a handful of a ring's edges and the average distance collapses toward the random value while clustering barely moves — that thin overlap is the small world. Down the center, data flows: parameters go in, the engine rewires and measures, the two curves come out. The blue team builds and defends it; the red team tries to break it.
source Watts, D. J. & Strogatz, S. H., Collective Dynamics of ‘Small-World’ Networks (1998), Nature 393, 440–442 — doi:10.1038/30918 — nature.com/articles/30918. Rendered, not quoted.
Start from a ring lattice: N nodes on a circle, each joined to its k nearest neighbours (k/2 each side). Then walk every edge and, with probability β, snip it and reconnect one end to a node chosen uniformly at random (no self-loops, no duplicates). Edge count is preserved; only where they land changes.
Two measurements, both computed live from the graph, not looked up:
C — clustering: for each node, the fraction of its neighbour-pairs that are themselves joined (a closed triple / triangle). L — the mean shortest-path length over all reachable pairs (breadth-first).
| N | k | β | C | L |
|---|
Milgram's letters found strangers linked by about six hops; Watts & Strogatz (1998) gave the mechanism. A pure lattice is too rigid — clustered but distances grow like N/2k. A purely random graph, the-erdos-renyi, is too loose — short paths but essentially no clustering.
The small world lives between them: a few random shortcuts across an otherwise local ring buy near-random distance at almost no cost to local structure. Erdős–Rényi is the β=1 endpoint of this very knob; each sphere is the next one's premise.
The blue team's live check: re-measure the ensemble and confirm the small-world gap — L collapses at small β while C stays high — against the known lattice and random values. If red tampers, this badge is where it shows.
Three numbers define the experiment: N = 60 nodes, neighbour degree k = 6 (so C of the untouched ring is exactly 0.6), and the rewiring probability β you sweep from 0 to 1. Every point averages a fixed-seed ensemble of 12 graphs, so the curve is deterministic — re-run and it is identical.
β = 0 is the ring lattice (clustered, far). β = 1 is a near-random graph (close, unclustered). The interesting physics is everything in between — feed β into the panel below.
Normalised curves C(β)/C(0) and L(β)/L(0). Where the cyan L-curve has already fallen but the purple C-curve is still high — the shaded band — is the small world.
Move β — both numbers are re-measured from freshly rewired graphs on the spot, never looked up.
What the machine proves: the ring (β=0) has C=0.6 and a long mean path (≈5.4 hops). A few rewires (β≈0.05–0.1) drop that path to roughly 60% while C stays near 0.9× its lattice value — short paths and high clustering at once. By β=1 both have fallen to random-graph levels (C≈0.09, L≈2.4≈ln N/ln k). The small world is that gap.
The blue team's witness (left) re-checks this gap live; the red team (right) tries to make it disappear.
And the model is a toy: nodes are interchangeable, geography and cost are ignored, and at very small β the few rewires make L high-variance — one lucky shortcut swings the mean. The small-world effect is robust; any single small graph is not.
“Small-world means everyone is six steps apart.” Cut. Six is folklore from Milgram's incomplete-return letters. The claim is structural: L grows like log N, not that it equals six.
“Small-world = scale-free.” Cut. Different properties. WS gives short paths + clustering with a homogeneous degree distribution; scale-free is about hub heterogeneity. A graph can be one, both, or neither.
“More rewiring is always better.” Kept, corrected. Past β≈0.1 you gain little path length but keep shedding clustering — you are just walking toward Erdős–Rényi.
The red team's move: after rewiring, don't recompute the paths — just report the lattice's long path length. The clustering still looks right, so the fraud is subtle: the small-world collapse simply never shows on the L-curve.
Skip re-measuring L on the rewired graph and the cyan curve stays pinned near 1 — no dip. The witness (window 7) recomputes the gap, finds L never fell, and turns red. Nothing is faked; the attack is real and it is caught.