The Watts-Strogatz model starts with vertices arranged on a ring, each joined to a fixed even number of nearest neighbors. It then rewires one orientation of each original ring edge independently with probability , choosing a new endpoint while avoiding loops and duplicate edges. The number of edges is preserved; individual degrees need not be.[ref]
Collective dynamics of small-world networks by Duncan J. Watts and Steven H. Strogatz. model construction and characteristic path length/clustering plots
At the graph is a regular ring lattice. A small positive rewiring probability introduces shortcuts that can sharply reduce typical path lengths while retaining substantial local clustering. This offers a mechanism for small-world networks with both properties. It is a model of a structural effect, not a claim that every observed network was generated by literal rewiring.
Articles by others on the same topic
The Watts–Strogatz model is a mathematical model used to generate small-world networks, which are characterized by high clustering and short average path lengths. Introduced by Duncan J. Watts and Steven H. Strogatz in their 1998 paper, "Collective dynamics of ‘small-world’ networks," this model captures the balance between local interconnectedness (like regular lattices) and global interconnectedness (like random networks).