Watts–Strogatz model

The Watts and 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 joint 1998 Nature paper. The model also became known as the (Watts) beta model after Watts used $\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. In particular, it explains how increasing the probability of any two nodes being connected beyond a critical threshold produces a connected network that is small-world in the sense that the average path length between any two nodes is short.

Despite their simplicity and power, the ER graphs fail to explain two important properties observed in real-world networks:

1. By assuming a constant and independent probability of two nodes being connected, they do not account for local clustering and triadic closures. This fact is formally expressed by the ER graphs having a low clustering coefficient.
2. 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 most 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 an ER graph and a regular ring lattice.

Algorithm

Given the desired number of nodes $N$, the mean degree $K$ (assumed to be an even integer), and a special parameter $\beta$, satisfying $0\leq \beta \leq 1$ and $N\gg K\gg ln(N)\gg 1$, the model constructs an undirected graph with $N$ nodes and ${\frac {NK}{2}}$ edges in the following way:

1. Construct a regular ring lattice, a graph with $N$ nodes each connected to $K$ neighbors, $K/2$ on each side. That is, if the nodes are labeled labeled $n_{0}...n_{N-1}$, there is an edge $(n_{i},n_{j})$ if and only if $\quad |i-j|\equiv k{\pmod {N}}$ for some $|k|\in \left(1,{\frac {K}{2}}\right)$
2. For every node $n_{i}=n_{0}...n_{N-1}$ take every edge $(n_{i},n_{j})$ with $i<j$, and rewire it with probability $\beta$. Rewiring is done by replacing $(n_{i},n_{j})$ with $(n_{i},n_{k})$ where $k$ is chosen with uniform probability from all possible values that avoid loops ($k\neq i$) and link duplication (there is no edge $(n_{i},n_{k'})$ with $k'=k$ at this point in the algorithm).

Properties

The underlying lattice structure of the model produces a locally clustered network, and the random links dramatically reduce the average path lengths. The algorithm introduces about $\beta {\frac {NK}{2}}$ non-lattice edges. Varying $\beta$ allows to interpolate between a regular lattice ($\beta =0$) and a random graph ($\beta =1$) approaching the Erdős–Rényi random graph $G(n,p)$ with $n=N$ and $p={\frac {NK}{2{N \choose 2}}}$.

The three properties of interest are the average path length, the clustering coefficient, and the degree distribution.

Average path length

For a ring lattice the average path length is $l(0)=N/2K\gg 1$ and scales linearly with the system size. In the limiting case of $\beta \rightarrow 1$ the graph converges to a classical random graph with $l(1)={\frac {\ln {N}}{\ln {K}}}$. However, in the intermediate region $0<\beta <1$ the average path length falls very rapidly with increasing $\beta$, quickly approaching its limiting value.

Clustering coefficient

For the ring lattice the clustering coefficient is $C(0)=3/4$ which is independent of the system size. In the limiting case of $\beta \rightarrow 1$ the clustering coefficient attains the value for classical random grpahs, $C(1)=K/N$ and is thus inversely proportional to the system size. In the intermediate region the clustering coefficient remains quite close to its value for the regular lattice, and only falls at relatively high $\beta$.

If we use the Barrat and Weigt measure for clustering $C'(\beta )$ defined as the fraction between the average number of edges between the neighbors of a node and the average number of possible edges between these neighbors, or, alternatively,

$C^{'}(\beta )\equiv {\frac {3\times {\mbox{number of triangles}}}{\mbox{number of connected triples}}}$

then we get $C'(\beta )\sim C(0)\left(1-\beta \right)^{3}$

Degree distribution

The degree distribution in the case of the ring lattice is just a Dirac delta function centered at $K$. In the limiting case of $\beta \rightarrow 1$ it is Poisson distribution, as with classical graphs. The degree distribution for $0<\beta <1$ can be written as,

$P(k)=\sum _{n=0}^{f\left(k,K\right)}C_{K/2}^{n}\left(1-\beta \right)^{n}\beta ^{K/2-n}{\frac {(\beta K/2)^{k-K/2-n}}{\left(k-K/2-n\right)!}}e^{-\beta K/2}$

where $k_{i}$ is the number of edges that the $i^{th}$ node has or its degree. Here $k\geq K/2$, and $f(k,K)=min(k-K/2,K/2)$. The shape of the degree distribution is similar to that of a random graph and has a pronounced peak at $k=K$ and decays exponentially for large $|k-K|$. The topology of the network is relatively homogeneous, and all nodes have more or less the same degree.

Limitations

The major limitation of the model is that it produces graphs that are homogeneous in degree. In contrast, real networks are often scale-free networks inhomogeneous in degree, having hubs and a scale-free degree distribution. Such networks are better described by the preferential attachment family of models, such as the Barabási–Albert (BA) model.

The model also implies a fixed number of nodes and thus cannot be used to model network growth.

See also

• Small-world networks
• Social networks