Skip to main content

Small-World Networks

Module 5: Complex Networks

NoteReading
  • Compulsory: Watts and Strogatz (1998) (the two-column letter, up to Figure 2).
  • Recommended: Newman (2003), Section 6.
  • What the paper did and found: Watts and Strogatz start from a ring lattice with \(n\) vertices and \(k\) edges per vertex and rewire each edge with probability \(p\) to a vertex chosen uniformly at random, forbidding duplicate edges. They work in the regime \(n \gg k \gg \ln n \gg 1\) and find \(L \approx n/2k\) and \(C \approx 3/4\) as \(p \to 0\), against \(L \approx \ln n/\ln k\) and \(C \approx k/n\) as \(p \to 1\). Plotted on a logarithmic axis for \(p\) (Figure 2, averages over 20 realisations, normalised by the values at \(p = 0\)), \(L(p)\) drops rapidly while \(C(p)\) stays almost constant, which defines the small-world regime. Their Table 1 shows that three real networks are small-world: the film-actor graph (\(L = 3.65\) against \(2.99\) for a random graph, \(C = 0.79\) against \(0.00027\)), the western US power grid (\(L = 18.7\) against \(12.4\), \(C = 0.080\) against \(0.005\)) and the neural network of C. elegans (\(L = 2.65\) against \(2.25\), \(C = 0.28\) against \(0.05\)).

A random graph has short paths but almost no clustering. A regular lattice has high clustering but long paths. Watts and Strogatz built a one-parameter model that interpolates between the two (Watts and Strogatz 1998).

The model

  1. Place \(N\) nodes on a ring and join each node to its \(k\) nearest neighbours (\(k/2\) on each side, \(k\) even).
  2. Visit every edge \((u, v)\). With probability \(p\), replace it by \((u, w)\), where \(w\) is chosen uniformly among the nodes that are not already neighbours of \(u\).

Notation. Some texts call the rewiring probability \(\beta\) and keep \(p\) for the edge probability of the random graph. The original paper uses \(p\) for the rewiring probability, as NetworkX does (nx.watts_strogatz_graph(n, k, p)), and so does this page; read \(p\) here as \(\beta\) in those texts. Rewiring introduces shortcuts that reduce distances while the clustering stays high, and that the result is \(L \sim \log N\). This holds for any fixed \(p > 0\) only once \(N\) is large enough that the shortcuts dominate: for smaller \(N\) the path length is still of the lattice type. Scaling of Path Length and Clustering measures that crossover.

At \(p = 0\) you have the ring lattice. At \(p = 1\) you have a graph close to a random graph with the same number of edges. The degree distribution stays narrow for every \(p\): every node keeps at least \(k/2\) edges.

Key result

For the ring lattice, the clustering coefficient is \(C(0) = \frac{3(k-2)}{4(k-1)}\), which tends to \(3/4\) for large \(k\), and the average path length grows linearly with \(N\) (Newman 2003, sec. 6.1). Watts and Strogatz found a wide range of small \(p\) in which \(L(p)\) has already dropped close to its random-graph value while \(C(p)\) is still close to \(C(0)\) (Watts and Strogatz 1998). A few random shortcuts are enough to shorten distances across the ring, while they destroy only a few triangles. Networks in this regime are called small-world networks. Watts and Strogatz reported the small-world property in a film actor collaboration network, the power grid of the western United States and the neural network of C. elegans (Watts and Strogatz 1998).

Figure 1 reproduces the shape of their Figure 2 on a smaller graph.

Figure 1: Watts-Strogatz model with N = 300 and k = 6. Average clustering C(p) and average path length L(p), both divided by their values at p = 0, averaged over 3 graphs per value of p.
C(0) = 0.600, formula 3(k-2)/(4(k-1)) = 0.600

Implementation

In NetworkX, nx.watts_strogatz_graph(n, k, p) generates the model. The variant nx.connected_watts_strogatz_graph retries until the graph is connected, which you need to compute path lengths.

SEED = 7

G_sw = nx.watts_strogatz_graph(n=80, k=6, p=0.08, seed=SEED)
pos = nx.circular_layout(G_sw)
nx.draw(G_sw, pos=pos, node_size=40, node_color="lightblue", edge_color="gray")
plt.title("Watts-Strogatz graph, N = 80, k = 6, p = 0.08")
plt.show()

degrees = [d for _, d in G_sw.degree()]
print("degree range:", min(degrees), "to", max(degrees))
print(f"C = {nx.average_clustering(G_sw):.3f}")

degree range: 4 to 7
C = 0.494

The circular layout keeps the ring visible, so you can spot the rewired shortcuts.

NoteExercise

Compute \(C\) and \(L\) for nx.watts_strogatz_graph(80, 6, p) with \(p = 0\), \(p = 0.08\) and \(p = 1\). Which value of \(p\) gives a small-world network?

for p in [0, 0.08, 1]:
    G = nx.connected_watts_strogatz_graph(80, 6, p, seed=SEED)
    print(p, round(nx.average_clustering(G), 3), round(nx.average_shortest_path_length(G), 2))

At \(p = 0.08\) the clustering is still close to the lattice value (\(C(0) = 0.6\)), while \(L\) has dropped well below its lattice value. At \(p = 1\) both are close to random-graph values.

The model explains short paths together with high clustering. It does not produce hubs: for that you need preferential attachment.

See also: Scaling of Path Length and Clustering for the dependence of \(L\) and \(C\) on \(N\) in the ER, WS and BA models.

In the summary table, the Watts-Strogatz model gets ticks for short paths and for high clustering, and a cross for the degree distribution, which stays narrow. Comparing Graph Models reproduces the whole table.

References

Newman, M. E. J. 2003. “The Structure and Function of Complex Networks.” SIAM Review 45 (2): 167–256. https://doi.org/10.1137/S003614450342480.
Watts, Duncan J., and Steven H. Strogatz. 1998. “Collective Dynamics of ’Small-World’ Networks.” Nature 393 (6684): 440–42. https://doi.org/10.1038/30918.