Watts–Strogatz model
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.
to formulate it in his popular science book Six Degrees.
The formal study of random graphs dates back to the work of Paul Erdős and Alfréd Rényi.
[2] 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: 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.
, the model constructs an undirected graph with
edges in the following way: The underlying lattice structure of the model produces a locally clustered network, while the randomly rewired links dramatically reduce the average path lengths.
makes it possible to interpolate between a regular lattice (
) and a structure close to an Erdős–Rényi random graph
It does not approach the actual ER model since every node will be connected to at least
The three properties of interest are the average path length, the clustering coefficient, and the degree distribution.
For a ring lattice, the average path length[1] is
and scales linearly with the system size.
, the average path length falls very rapidly with increasing
grows, independently of the system size.
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
This results in a region where the average path length falls rapidly, but the clustering coefficient does not, explaining the "small-world" phenomenon.
The degree distribution in the case of the ring lattice is just a Dirac delta function centered at
The degree distribution for a large number of nodes and
The shape of the degree distribution is similar to that of a random graph and has a pronounced peak at
The topology of the network is relatively homogeneous, meaning that all nodes are of similar degree.
The major limitation of the model is that it produces an unrealistic degree distribution.
In contrast, real networks are often scale-free networks inhomogeneous in degree, having hubs and a scale-free degree distribution.
(On the other hand, the Barabási–Albert model fails to produce the high levels of clustering seen in real networks, a shortcoming not shared by the Watts and Strogatz model.
The Watts and Strogatz model also implies a fixed number of nodes and thus cannot be used to model network growth.
