The Watts–Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their article published in 1998 in the Nature scientific journal. The model also became known as the (Watts) beta model after Watts used β {\displaystyle \beta } to formulate it in his popular science book Six Degrees.
Rationale for the model The formal study of random graphs dates back to the work of Paul Erdős and Alfréd Rényi. The graphs they considered, now known as the classical or Erdős–Rényi (ER) graphs, offer a simple and powerful model with many applications. However the ER graphs do not have two important properties observed in many real-world networks:
They do not generate local clustering and triadic closures. Instead, because they have a constant, random, and independent probability of two nodes being connected, ER graphs have a low clustering coefficient. They do not account for the formation of hubs. Formally, the degree distribution of ER graphs converges to a Poisson distribution, rather than a power law observed in many real-world, scale-free networks. The Watts and Strogatz model was designed as the simplest possible model that addresses the first of the two limitations. It accounts for clustering while retaining the short average path lengths of the ER model. It does so by interpolating between a randomized structure close to ER graphs and a regular ring lattice. Consequently, the model is able to at least partially explain the "small-world" phenomena in a variety of networks, such as the power grid, neural network of C. elegans, networks of movie actors, or fat-metabolism communication in budding yeast.
Algorithm
Given the desired number of nodes N {\displaystyle N} , the mean degree K {\displaystyle K} (assumed to be an even integer), and a parameter β {\displaystyle \beta } , all satisfying 0 ≤ β ≤ 1 {\displaystyle 0\leq \beta \leq 1} and N ≫ K ≫ ln N ≫ 1 {\displaystyle N\gg K\gg \ln N\gg 1} , the model constructs an undirected graph with N {\displaystyle N} nodes and N K 2 {\displaystyle {\frac {NK}{2}}} edges in the following way:
Construct a regular ring lattice, a graph with N {\displaystyle N} nodes each connected to K {\displaystyle K} neighbors, K / 2 {\displaystyle K/2} on each side. That is, if the nodes are labeled 0 … N − 1 , {\displaystyle 0\ldots {N-1},} there is an edge ( i , j ) {\displaystyle (i,j)} if and only if 0 < | i − j | m o d ( N − 1 − K 2 ) ≤ K 2 . {\displaystyle 0<|i-j|\ \mathrm {mod} \ \left(N-1-{\frac {K}{2}}\right)\leq {\frac {K}{2}}.}
For every node i = 0 , … , N − 1 {\displaystyle i=0,\dots ,{N-1}} take every edge connecting i {\displaystyle i} to its K / 2 {\displaystyle K/2} rightmost neighbors, that is every edge ( i , j ) {\displaystyle (i,j)} such that 0 < ( j − i ) m o d N ≤ K / 2 {\displaystyle 0<(j-i)\ \mathrm {mod} \ N\leq K/2} , and rewire it with probability β {\displaystyle \beta } . Rewiring is done by replacing ( i , j ) {\displaystyle (i,j)} with ( i , k ) {\displaystyle (i,k)} where k {\displaystyle k} is chosen uniformly at random from all possible nodes while avoiding self-loops ( k ≠ i {\displaystyle k\neq i} ) and link duplication (there is no edge ( i , k ′ ) {\displaystyle (i,{k'})} with k ′ = k {\displaystyle k'=k} at this point in the algorithm).
… excerpt ends here. Continue reading the full article.
