Watts and Strogatz’s
Collective dynamics of
’small-world’ networks
:
an annotatable review

Abstract

This is a summary of Watts and Strogatz’s classic 1998 paper on network models and the inherent “small world” properties found in many “organic” networks (Watts 1998).

Bret Victor’s brilliant comic-formatted example

the classic paper

Motivation

Many networks of dynamical systems are either regular or random. Here, the authors investigate so-called ’small-world’ networks which allow to probe the region between these two extremes by a rewiring strategy of a regular network. The name of these graphs is chosen in analogy to the small-world phenomenon (also known as six degrees of separation).

Model and Observables

The following random rewiring process is executed to generate a graph which allows for the interpolation between regular (\(p=0\)) and random (\(p=1\)) networks:

  1. Generate a ring network with \(n\) nodes and an (average) degree \(k\) for each node

  2. Rewire each edge with probability \(p\), where a new endpoint of the edge is chosen uniformly at random from all vertices. This edge is only added, if it doesn’t exist so far.

Two observables are considered to investigate small-world networks. The characteristic path length \(L(p)\) is defined by the number of edges in the shortest path between two nodes, averaged over all pairs of nodes and it is a global property. The clustering coefficient \(C(p)\) is a local property and it basically measures the fraction of connected neighbors of a node in the graph compared to all possible connections of the neighbors averaged over all nodes.

Results

In the case \(n \gg k \gg \ln(n) \gg 1\), one can derive the following the limiting cases. For a regular graph (\(p=0\)) one gets a highly clustered (\(C \sim 3/4\)) graph where \(L \sim n/2k\). For a random graph (\(p=1\)) the resulting network is poorly clustered (\(C_{\text{random}} \sim k/n\)) and small-world-like (\(L_{\text{random}} \sim \ln(n)/\ln(k)\)).

For intermediate values of \(0 < p < 1\), i.e. small-world networks one obtains a broad interval of \(p\)-values where the characteristic path length \(L(p) \approx L_{\text{random}}\), but \(C(p) \gg C_{\text{random}}\). This is a result of adding few long-range short cuts in the graph which connect distant nodes with each other.

Next, the authors investigate three empirical examples of small-world networks: The collaboration network of film actors, the electrical power grid of the western United States and the neural network of the worm C. elegans. The results are shown in table \ref{tab1}. All three investigated real networks show the small-world phenomenon \(L \gtrsim L_{\text{random}}\) but \(C \gg C_{\text{random}}\).

Values for the characteristic path length \(L\) and the clustering coefficient \(C\) for different real networks compared with random networks. For the random networks the same number of nodes \(n\) and the same number of average neighbors \(k\) as in the real graph are chosen. \label{tab1}
\(n\) \(k\) \(L\) \(L_{\text{random}}\) \(C\) \(C_{\text{random}}\)
Film actors 225,226 61 3.65 2.99 0.79 0.00027
Power grid 4,941 2.67 18.7 12.4 0.080 0.005
C. elegans 282 14 2.65 2.25 0.28 0.05

The behavior of dynamical systems on small-world networks is investigated next. A simple model for disease spreading (SIR model) is used as an example for such a dynamical system. It is found that the critical infectiousness \(r_{\text{half}}\) at which the disease has infected half of the population decreases rapidly for small \(p\). The time \(T(p)\) required for a maximally infectious disease to infect the whole population follows essentially the same functional form as the characteristic path length. Hence, infectious dieases spread much more easily and quickly in a small world.