Appendix: Why a Random Network Is Already Small

The main text uses three results without proving them: that the local clustering coefficient can be written with the adjacency matrix, that a random graph’s clustering is exactly p, and that its distances grow like \log n. Here are the derivations. Nothing on this page is needed to use the small-world index — it is here for readers who want to see where the baseline numbers come from.

The Erdős-Rényi Random Graph

The Erdős-Rényi random graph is the structureless baseline against which everything else in the module is measured. It comes in two variants: G(n,m) creates n nodes and places exactly m edges at random, while G(n,p) creates n nodes and joins each of the \binom{n}{2} possible pairs independently with probability p. We work with G(n,p), because independence is what makes the algebra below go through.

Its average degree is \langle k \rangle = p(n-1): node i has n-1 possible partners and takes each with probability p.

Writing Local Clustering with the Adjacency Matrix

The main text defines the local clustering coefficient by counting:

C_i = \frac{e_i}{k_i(k_i-1)/2}

where e_i is the number of edges among the neighbors of node i. The same quantity is often written with the adjacency matrix A:

C_i = \frac{\sum_{j}\sum_{\ell} A_{ij}A_{j\ell} A_{\ell i} }{k_i(k_i-1)}

The two agree. The product A_{ij}A_{j\ell}A_{\ell i} equals 1 exactly when i, j and \ell form a triangle, and 0 otherwise. Summing it over all j and all \ell counts each triangle at i twice, once as i \rightarrow j \rightarrow \ell \rightarrow i and once as i \rightarrow \ell \rightarrow j \rightarrow i, so the numerator equals 2e_i. The denominator k_i(k_i-1) is likewise twice the number of neighbor pairs \binom{k_i}{2} = k_i(k_i-1)/2. The factors of 2 cancel and the two expressions are the same number.

Why a Random Graph’s Clustering Is Exactly p

Consider a node i with degree k_i = k in G(n,p). Between its k neighbors there are \binom{k}{2} = \frac{k(k-1)}{2} possible edges. Here is the point of using G(n,p): whether any one of those edges exists is independent of the edges that made these nodes neighbors of i in the first place. Each one is present with probability p, so

E[e_i \mid k_i = k] = \frac{k(k-1)}{2} \cdot p .

Dividing by the number of pairs gives the expected local clustering coefficient:

E[C_i \mid k_i = k] = \frac{\frac{k(k-1)}{2} \cdot p}{\frac{k(k-1)}{2}} = p .

The degree cancels out entirely, so the answer is p for every node no matter how many friends it has. Averaging over nodes therefore also gives p, and substituting \langle k \rangle = p(n-1) produces the reference value quoted in the main text:

\overline{C}_{\text{random}} = p = \frac{\langle k \rangle}{n-1} .

With n = 1{,}000 and \langle k \rangle = 10 this is 0.010 — a hundredth. Any real network with clustering in the tenths is doing something a random graph does not.

Why Distances in a Random Graph Grow Only Logarithmically

Now the other baseline. Write \langle k \rangle = k for the average degree and imagine exploring the network outward from one node, one layer at a time.

• Step 1 reaches roughly k new nodes — the starting node’s neighbors.
• Step 2: each of those k nodes has about k neighbors of its own, giving about k^2 new nodes.
• After h steps you have reached about 1 + k + k^2 + \ldots + k^h \approx k^h nodes.

The counting assumes that each step lands on nodes you have not already seen — that the exploration branches like a tree rather than looping back on itself. That is a good approximation in a sparse random graph precisely because we just showed its clustering is p = \langle k \rangle / (n-1), which is tiny: a neighbor of a neighbor is almost never someone you have already met.

The expansion stops when it has covered the network, that is when k^h \approx n. Solving for h:

h \approx \log_{k}(n) = \frac{\log n}{\log k} .

So the number of steps needed to reach the whole network — and hence the typical distance between two nodes — grows only like \log n:

\overline{L}_{\text{random}} \approx \frac{\log n}{\log \langle k \rangle} .

Strictly, the quantity this argument bounds is the depth of the exploration, which is closer to the network’s diameter (the largest distance) than to the average. But in a random graph the two are within a constant factor of each other, because almost every node is reached on the very last layer, and the \log n / \log \langle k \rangle formula is the standard estimate for both.

The consequence is the one that reframes the whole module. Multiplying the number of nodes by a thousand adds only \log 1000 / \log \langle k \rangle steps — for \langle k \rangle = 10, three of them. A random graph of 1,000 nodes with average degree 10 has typical distance 6.91/2.30 = 3.0; grow it to a million and you get 6; grow it to a billion and you get 9. Short paths are free. Every network that is merely well-mixed already has them, which is why the surprising part of the small-world phenomenon is not the six degrees — it is that we get six degrees while still living in dense little clusters of friends.