Watts-Strogatz Algorithm

Described in D.J. Watts and S.H. Strogatz, 1998, Nature (London) 393, 440.

This algorithm arranges a lattice of n vertices and connects each vertex to its k-nearest neighbors. With probability p, each edge is re-wired. Because this model is meant to simulate the dynamics of small interpersonal networks, it has come to be referred to as the small-world model.