Watts and Strogatz Model

As explained in more detail in Section 1.3, our next model was inspired by the popular concept of “six degrees of separation,” which is based on the notion that every one in the world is connected to everyone else through a chain of at most six mutual acquaintances. Now an Erdös–Rényi random graph for n = 6 billion people in which each individual has an average of μ = 42.62 friends would have average pairwise distance (log n)/(log μ) = 6, but would have very few triangles, while in social networks if A and B are friends and A and C are friends, then it is fairly likely that B and C are also friends.

To construct a network with small diameter and a positive density of triangles, Watts and Strogatz (1998) started from a ring lattice with n vertices and k edges per vertex, and then rewired each edge with probability p, connecting one end to a vertex chosen at random. This construction interpolates between regularity (p = 0) and disorder (p = 1). The disordered graph is not quite an Erdös–Rényi graph, since the degree of a node is the sum of a Binomial(k, 1/2) and an independent Poisson(k/2).