Watts-Strogatz model
Start with regular ring lattice. Rewire each edge with probability p. Interpolates between lattice + random.
Advertisement
Properties
p = 0: high clustering, high diameter. p = 1: low clustering, low diameter. Small p: high clustering + low diameter — small-world regime.
Advertisement
Milgram's experiment
1967 mail-passing study estimated 6-hop average distance between random Americans.
Kleinberg's algorithmic small world
Grid + long-range edges with distribution ~1/d² → decentralized greedy routing finds targets in O(log² N) hops.