Watts-Strogatz Model

Watts-Strogatz model is the canonical algorithm for generating small-world networks, introduced by Duncan Watts and Steven Strogatz in their 1998 Nature paper. The model begins with a regular ring lattice and rewires each edge with probability p, producing networks that interpolate between regular lattices (high clustering, long paths) and random graphs (low clustering, short paths). It remains the dominant synthetic construction for understanding how local order and global randomness can coexist in the same topology, though critics note that real networks rarely form by literal rewiring.

The model's influence derives not from its realism as a growth mechanism but from its demonstration that small-world properties occupy a broad region of network space, accessible through multiple generative routes.