Watts-Strogatz model

The Watts-Strogatz model is a generative mechanism for small-world networks, introduced by Duncan Watts and Steven Strogatz in their 1998 paper 'Collective Dynamics of Small-World Networks.' The model begins with a regular ring lattice in which each node is connected to its k nearest neighbors. With probability p, each edge is randomly rewired to a new target node. For small p, the network retains high local clustering while acquiring short global path lengths — the defining small-world property.

The model's significance is not merely that it produces small-world networks but that it reveals phase transitions in network topology. As p increases from 0 to 1, the network undergoes a rapid transition from a regular lattice to a random graph, with a narrow intermediate regime where both clustering and short paths coexist. This suggests that small-world structure is not rare but robust — a generic property of networks with a small fraction of random long-range connections.