Small-World Networks

In 1998, Watts and Strogatz proposed a network model that captures a striking property observed in real-world networks: high clustering combined with short average path lengths — the "small-world" phenomenon.

The Ring Lattice

Start with a ring lattice: $N$ nodes arranged in a circle, each connected to its $K$ nearest neighbours on each side (total degree $2K$).

N=6, K=2: node 0 connects to {1, 2, 4, 5}

Properties of the regular ring lattice:

• High clustering: nearby nodes share many common neighbours
• Long path lengths: to get across the ring takes $O(N/K)$ steps

Average Path Length

The average path length $L$ is the mean shortest-path distance over all pairs of nodes:

$L = \frac{1}{N(N-1)} \sum_{i \neq j} d(i, j)$

Shortest paths are computed using breadth-first search (BFS).

Global Clustering Coefficient

The global clustering coefficient $C$ is the mean local clustering coefficient across all nodes:

$C = \frac{1}{N} \sum_i C_i$

Small-World Signature

A network is "small-world" when, compared to a random graph with the same $N$ and $\langle k \rangle$:

• $C \gg C_{\text{random}}$ (much higher clustering)
• $L \approx L_{\text{random}}$ (similar short paths)

Real examples: social networks (six degrees of separation), the brain's connectome, the power grid.

Your Task

Implement:

• ring_lattice_adj(N, K) — build the ring lattice adjacency dict; node $i$ connects to $(i \pm 1) \% N, (i \pm 2) \% N, \ldots, (i \pm K) \% N$
• bfs_distances(adj, source) — BFS from source, returns {node: distance} dict
• average_path_length(adj) — mean shortest path over all ordered pairs
• global_clustering(adj) — mean local clustering coefficient

Use from collections import deque for BFS.