Small-World Networks, in depth: Watts-Strogatz, clustering and path length, measuring small-worldness and Kleinberg navigability

Two measurements: clustering and path length

Two numbers describe the regime. The average shortest path length L is the mean number of hops between pairs of nodes, computed with breadth-first search from every source (see BFS and DFS). The clustering coefficient of a node with degree d is the fraction of the d(d-1)/2 possible edges among its neighbours that actually exist; the average clustering C is the mean over nodes.

Reference points make these numbers meaningful. A ring lattice of n nodes, each joined to its k nearest neighbours (k/2 on each side), has clustering C = 3(k-2)/(4(k-1)), which approaches 3/4 for large k, and path length about n/(2k), which grows linearly with n. A random graph with the same n and average degree k has clustering about k/n, which vanishes for large sparse graphs, and path length about ln n / ln k, which grows only logarithmically. A small-world network has C close to the lattice and L close to the random graph.

The Watts-Strogatz model in code

The construction has three parameters: n nodes, even degree k, and rewiring probability p. Start with the ring lattice. Then for each local edge, with probability p, keep one endpoint and move the other to a uniformly random node, avoiding self-loops and duplicate edges. At p = 0 you have the lattice; at p = 1 you have something close to a random graph with the same number of edges. The code below is the version used for the simulation in the next section; it is pure Python so you can read every step.

import random
from collections import deque

def watts_strogatz(n, k, p, rng):
    adj = [set() for _ in range(n)]
    for i in range(n):                       # ring lattice, k/2 neighbours each side
        for j in range(1, k // 2 + 1):
            adj[i].add((i + j) % n); adj[(i + j) % n].add(i)
    for j in range(1, k // 2 + 1):           # rewire in rounds, as in the original paper
        for i in range(n):
            v = (i + j) % n
            if v in adj[i] and rng.random() < p:
                w = rng.randrange(n)
                while w == i or w in adj[i]:
                    w = rng.randrange(n)
                adj[i].discard(v); adj[v].discard(i)
                adj[i].add(w); adj[w].add(i)
    return adj

def avg_clustering(adj):
    total = 0.0
    for u, nbrs in enumerate(adj):
        d = len(nbrs)
        if d < 2:
            continue
        nb = list(nbrs)
        links = sum(1 for a in range(d) for b in range(a + 1, d) if nb[b] in adj[nb[a]])
        total += 2 * links / (d * (d - 1))
    return total / len(adj)

def avg_path_length(adj, sources=None):
    n = len(adj); tot = cnt = 0
    for s in (sources or range(n)):
        dist = [-1] * n; dist[s] = 0; q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] < 0:
                    dist[v] = dist[u] + 1; q.append(v)
        if -1 in dist:
            raise ValueError("graph is disconnected; L is undefined")
        tot += sum(dist); cnt += n - 1
    return tot / cnt

Clustering costs O(n d^2) and exact L costs O(n(n + m)) for n nodes and m edges, so exact L is fine for thousands of nodes and too slow for millions. The optional sources argument lets you estimate L from a random sample of BFS sources, which is what you do on large graphs.

Worked example: a simulation you can reproduce

Here is the experiment, run with the code above: n = 1000, k = 10, three random seeds per value of p, averaged. Numbers will move slightly with other seeds but the shape is stable.

Read the rows against the reference points. The lattice matches the formulas: C = 3(8)/(4(9)) = 0.667 and L close to n/(2k) = 50. At p = 1 the clustering has collapsed to about k/n = 0.01 and L is close to ln 1000 / ln 10, about 3.0. The interesting rows are in between. With only five shortcuts L has halved while clustering is unchanged. With fifty shortcuts, one per hundred edges, L is already below 9, about one sixth of the lattice value, and clustering has lost only 3 percent. That gap, where L has fallen and C has not, is the small-world regime.

The intuition: one shortcut between distant parts of the ring shortens not just the path between its two endpoints but every path that can detour through it. A clustered neighbourhood, by contrast, depends on many local edges, and destroying it requires rewiring a large share of them. Newman and Watts showed that L scales as (n/k) f(n k p), so the controlling quantity is the number of shortcuts, not p by itself. A bigger graph needs a smaller p to enter the regime.

Why clustering survives: the Barrat-Weigt formula

Barrat and Weigt derived a simple approximation for the clustering of the rewired graph: C(p) is about C(0)(1 - p)^3. The reasoning is that a triangle among a node and two of its lattice neighbours survives only if all three of its edges are left in place, each with probability 1 - p. Check it against the table: at p = 0.1 it predicts 0.667 x 0.729 = 0.486, against 0.489 measured; at p = 0.01 it predicts 0.647 against 0.645. Path length has no equally simple closed form, which is why the simulation is the standard way to see it.

This asymmetry, cubic decay for clustering against an early collapse for path length, is the whole phenomenon in one sentence, and it is why you can design a network with both properties deliberately instead of hoping for them.

Testing whether your graph is small-world

Given your own graph, from a service dependency map to a social graph to a nearest-neighbour index, how do you tell whether it is small-world? Compare it with a random baseline that has the same degrees. Two common indices are:

• Sigma (Humphries and Gurney): sigma = (C / C_rand) / (L / L_rand). Values well above 1 suggest small-world structure. It grows with graph size, so you cannot compare sigma across graphs of different sizes.
• Omega (Telesford and colleagues): omega = L_rand / L - C / C_latt, where C_latt comes from a lattice-like version of the graph. Values near 0 indicate small-world, near -1 lattice-like, near +1 random-like.

def degree_preserving_shuffle(edges, swaps, rng):
    """Random baseline with the same degree sequence (double-edge swaps)."""
    edges = [tuple(e) for e in edges]
    present = set(frozenset(e) for e in edges)
    for _ in range(swaps):
        i, j = rng.randrange(len(edges)), rng.randrange(len(edges))
        (a, b), (c, d) = edges[i], edges[j]
        if len({a, b, c, d}) < 4:
            continue
        if frozenset((a, d)) in present or frozenset((c, b)) in present:
            continue
        present -= {frozenset((a, b)), frozenset((c, d))}
        present |= {frozenset((a, d)), frozenset((c, b))}
        edges[i], edges[j] = (a, d), (c, b)
    return edges

def sigma(adj, rng, trials=5, sample=200):
    src = rng.sample(range(len(adj)), sample)
    C, L = avg_clustering(adj), avg_path_length(adj, src)
    Cr = Lr = 0.0
    for _ in range(trials):
        r = to_adj(degree_preserving_shuffle(edge_list(adj), 10 * num_edges(adj), rng))
        Cr += avg_clustering(r) / trials
        Lr += avg_path_length(r, src) / trials   # raises if the shuffle disconnected it
    return (C / Cr) / (L / Lr)

def edge_list(adj):
    return [(u, v) for u, nb in enumerate(adj) for v in nb if u < v]

def num_edges(adj):
    return sum(len(nb) for nb in adj) // 2

def to_adj(edges, n=None):
    n = n or 1 + max(max(e) for e in edges)
    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v); adj[v].add(u)
    return adj

Double-edge swaps preserve every degree but can occasionally split the graph; if avg_path_length raises on a baseline, discard that sample and draw another.

Use the degree-preserving baseline rather than an Erdos-Renyi graph with the same density: a graph with a few huge hubs has short paths because of its hubs, not because of rewiring, and the wrong baseline will report small-world structure that is really degree heterogeneity. If you also care about which nodes create those short paths, eigenvector centrality and Louvain community detection show the hubs and the dense clusters they connect.

Short paths versus findable paths: Kleinberg navigability

Milgram's letters were routed by people who only knew their own contacts, so short paths were not enough: people had to find them. Jon Kleinberg showed in 2000 that this is a separate and harder property. In his model, nodes sit on a two-dimensional grid with local edges, and each node gets one long-range link to a node at grid distance d with probability proportional to d^(-r). Each message is forwarded greedily to the contact closest to the target in grid distance.

The result: greedy routing reaches the target in an expected O(log^2 n) steps when r = 2, the grid dimension, and needs a number of steps growing polynomially in n for every other value of r. With r = 0 the long links are uniform, so paths are short but the links are useless for steering; with large r the links are too local to help. At r equal to the dimension, long links are spread evenly across distance scales, so from any position there is a reasonable chance of a link that halves the remaining distance.

def greedy_route(pos, nbrs, src, dst, dist):
    """Forward to the neighbour closest to dst; stop if no neighbour improves."""
    path, cur = [src], src
    while cur != dst:
        nxt = min(nbrs[cur], key=lambda v: dist(pos[v], pos[dst]))
        if dist(pos[nxt], pos[dst]) >= dist(pos[cur], pos[dst]):
            return path, False       # local minimum: greedy is stuck
        path.append(nxt); cur = nxt
    return path, True

This is the design principle behind navigable small-world graphs in vector search. HNSW keeps a hierarchy of layers whose links span decreasing distance scales and searches greedily from the top, which is Kleinberg's idea made practical; see HNSW in depth. Peer-to-peer overlays such as Symphony also choose long links with a harmonic distance distribution for the same reason.

Failure modes and pitfalls

• Disconnected graphs. Rewiring at high p can isolate a node, making L infinite. Either reject disconnected samples or report L on the largest component and say so.
• Wrong baseline. Comparing a hub-dominated graph to an Erdos-Renyi graph overstates small-worldness; use degree-preserving shuffles.
• Sampled L without error bars. Estimate from several source samples and report the spread.
• Assuming the model matches reality. Watts-Strogatz degrees are nearly uniform; real social and web graphs have heavy-tailed degrees, which PageRank and similar measures are designed around.
• Confusing short with navigable. A graph can have short paths that no local routing rule finds; test greedy routing success directly if routing is the goal.

Trade-offs

What to do next

1. Run the Watts-Strogatz code above for your own n and k and plot C(p)/C(0) and L(p)/L(0) on a log scale of p.
2. Check the measured clustering against C(0)(1 - p)^3.
3. Pick a real graph you own, compute C and sampled L, and compute sigma against a degree-preserving baseline.
4. If the graph is used for routing or search, measure greedy routing success and hop count, not only L.
5. Read Watts and Strogatz (1998) and Kleinberg (2000); both are short and still the clearest statements of the ideas.