Small World Graphs

Small World Graphs are a classification of graphs that have a property of “clustering” in combination with “short path lengths”. This means that nodes in the graph tend to form tightly-knit groups (high clustering coefficient), while still being connected to other groups through a few long-range connections (short average path length).

The key importance of small world graphs is that they tend to show up in biological, social, and technological networks. For example, social networks often exhibit small world properties, where individuals are part of close-knit communities but can also connect to distant acquaintances through a few intermediaries.

Another great example is this obsidian vault, as the property of clustering emerged without explicit design, while still maintaining short paths between any two notes.

This leads to something called “information highways”, where information can quickly spread across the network due to the presence of these long-range connections, while still benefiting from the local clustering for efficient communication within groups.

---

Formal Definition

A small-world graph is characterized by two key properties: a high clustering coefficient $\sigma$ and a short average path length $L$. This is supposedly a rare combination in random graphs, as most graphs tend to have either high clustering or short path lengths, but not both.

Computing the Clustering Coefficient

We can find the local clustering coefficient $C_i$ for each node $i$ and then average over all nodes to get the global clustering coefficient $C$:

$$C_i=\frac{\text{number of edges between neighbors of }i}{\text{maximum possible edges between neighbors}}=\frac{2e_i}{k_i(k_i-1)}$$

where:

• $k_i$ is the degree of node $i$ (number of neighbors)
• $e_i$ is the number of edges between the neighbors of $i$
• For nodes with degree 0 or 1, we define $C_i=0$

We can then compute the global clustering coefficient as:

$$C=\frac{1}{n}\sum _{i=1}^n{C}_i$$

Intuition

If a node $i$ has 10 neighbors, those neighbors could potentially form $\left(\genfrac{}{}{0ex}{}{10}{2}\right)=45$ connections between themselves. If they actually form 20 connections, then $C_i=20/45\approx 0.44$.

Average Path Length

The characteristic path length $L$ is the average shortest path between all pairs of nodes:

$$L=\frac{1}{n(n-1)}\sum _{i\ne j}d(i,j)$$

where $d(i,j)$ is the shortest path distance between nodes $i$ and $j$.

For disconnected graphs, only connected pairs are considered, or we use the harmonic mean distance:

$$L_{\text{harm}}=\frac{n(n-1)}{{\sum }_{i\ne j}\frac{1}{d(i,j)}}$$

Small-World Criterion

A network exhibits small-world properties if:

$$C\gg C_{\text{random}}\text{and}L\approx L_{\text{random}}$$

More formally, the small-worldness coefficient is:

$$S=\frac{C/C_{\text{random}}}{L/L_{\text{random}}}$$

A network is considered small-world if $S>1$, typically $S\gg 1$ in practice.

For comparison:

• Regular lattice: High $C$, high $L$
• Random graph (Erdős–Rényi): Low $C$, low $L$
• Small-world: High $C$, low $L$

Watts-Strogatz Model

The canonical small-world graph is generated by the Watts-Strogatz model:

1. Start with a regular ring lattice of $n$ nodes, each connected to its $k$ nearest neighbors
2. For each edge, rewire it with probability $p$ to a randomly chosen node
3. The rewiring probability $p\in [0,1]$ controls the transition:
   • $p=0$: Regular lattice
   • $p=1$: Random graph
   • $0.01\lesssim p\lesssim 0.1$: Small-world regime

The small-world property emerges because even a few random rewirings ($p\ll 1$) dramatically reduce $L$ while barely affecting $C$.

---

^