Appendix: One Number Decides Whether a Network Holds Together
In the main text we used several results without proving them:
- A giant component exists when \kappa = \dfrac{\langle k^2 \rangle}{\langle k \rangle} > 2.
- Under random failures the network falls apart once a fraction f_c = 1 - \dfrac{1}{\kappa - 1} of nodes is removed.
- A network with enough degree heterogeneity has f_c \rightarrow 1: essentially every node must fail before it breaks.
- That same network breaks under a targeted attack at a few percent.
This appendix derives all four. The only tool we need is a careful answer to one question: if I follow a random edge, what do I find at the other end?
Setup: what kind of network are we talking about?
The criterion applies to a network that is randomly wired subject to a given degree sequence — the configuration model. Picture giving node i exactly k_i half-edges (“hands”), throwing all the hands into a bag, and pairing them up at random.
This is the same null model we meet again in Module 5, where it supplies the k_ik_j/2m term in modularity. There it answers “how many edges would I expect by chance?”; here it answers “does the network hold together?”
The important consequence of random wiring is that the network is locally tree-like: starting from a node and walking outward, you almost never return to where you have already been, because short cycles are vanishingly rare in a large sparse random network. This is what lets us treat the exploration as a branching process.
Step 1: following an edge is biased toward high degree
Let p(k) be the fraction of nodes with degree k. If we pick a node uniformly at random, we get degree k with probability p(k), and the average degree is
\langle k \rangle = \sum_{k} k \, p(k).
But that is not how the exploration works. We arrive at nodes by following edges, and a node with many hands is many times more likely to be at the end of the hand we happened to grab.
Nodes of degree k contribute k \, p(k) hands to the bag, out of \sum_{k} k\,p(k) = \langle k \rangle hands in total. So the probability that a randomly chosen hand belongs to a node of degree k is
q(k) = \frac{k \, p(k)}{\sum_{k'} k'\, p(k')} = \frac{k}{\langle k \rangle} p(k).
q(k) is exactly the mechanism behind the friendship paradox in Module 4: the person at the other end of a friendship tie is not an average person. Here it decides whether the network survives; there it decides whom to vaccinate. Same bias, two uses.
The average degree of the node we land on is therefore
\langle k \rangle_{q} = \sum_{k} k \, q(k) = \sum_{k} k \cdot \frac{k}{\langle k \rangle} p(k) = \frac{\langle k^2 \rangle}{\langle k \rangle} = \kappa.
So \kappa is not an abstract ratio: it is the average degree of the node you reach by following a random edge. Because it involves \langle k^2 \rangle, it is large whenever the degree distribution has a heavy tail — which is exactly the “degree heterogeneity” reading used in the main text.
Step 2: the branching argument
Now explore the network outward from a randomly chosen starting node.
Arrive at some node by following an edge. On average it has \kappa edges — but one of them is the edge we came in on, and that one leads backward. The number of new edges leading onward is on average
\kappa - 1 = \frac{\langle k^2 \rangle}{\langle k \rangle} - 1.
This quantity — the average number of onward edges from a node reached by an edge — is the branching factor of the exploration, and its value is the whole story:
- If \kappa - 1 < 1, each layer of the exploration is smaller than the last. The frontier shrinks geometrically and dies out after a few steps. Every component is small.
- If \kappa - 1 > 1, each layer is larger than the last. The frontier grows geometrically and reaches a finite fraction of the network. A giant component exists.
The transition sits exactly at \kappa - 1 = 1:
\boxed{\;\kappa = \frac{\langle k^2 \rangle}{\langle k \rangle} > 2 \iff \text{a giant component exists.}\;}
This is the Molloy-Reed criterion.
Molloy and Reed originally stated it as \mathbb{E}[k(k-2)] > 0. The two forms say the same thing: \langle k^2 \rangle - 2\langle k \rangle > 0, then divide through by \langle k \rangle > 0.
- A ring, where every node has degree exactly 2: \langle k^2\rangle = 4, \langle k \rangle = 2, so \kappa = 2. Exactly at the threshold — and indeed a ring is a single cycle, connected but with nothing to spare. Cut one edge and it is a path; the structure is marginal.
- Isolated pairs, every node of degree 1: \kappa = 1 < 2. No giant component, as expected.
- A Poisson network with \langle k \rangle = 1: we show below that \kappa = \langle k \rangle + 1 = 2. This reproduces the classic Erdős-Rényi result that the giant component appears exactly at average degree 1.
Step 3: what random failure does to \kappa
Now remove nodes at random, keeping each with probability p (so a fraction f = 1-p is removed). The result is still a randomly wired network, so the criterion still applies — we only need its new \kappa.
Take a node that survives and originally had degree k_0. Each of its neighbors independently survives with probability p, so its new degree k follows \text{Binomial}(k_0, p). Using \mathbb{E}[k \mid k_0] = p k_0 and \text{Var}(k \mid k_0) = k_0\, p (1-p):
\begin{aligned} \langle k \rangle_p &= p \, \langle k \rangle_0 \\[4pt] \langle k^2 \rangle_p &= \mathbb{E}\left[\text{Var}(k \mid k_0) + \mathbb{E}[k \mid k_0]^2\right] = p(1-p)\langle k \rangle_0 + p^2 \langle k^2 \rangle_0 \end{aligned}
Dividing gives a pleasantly simple result:
\kappa_p = \frac{\langle k^2 \rangle_p}{\langle k \rangle_p} = \frac{p^2 \langle k^2 \rangle_0 + p(1-p)\langle k \rangle_0}{p \langle k \rangle_0} = p \, \kappa_0 + (1 - p).
Random removal therefore drags \kappa linearly from its original value \kappa_0 (at p=1) down toward 1 (as p \rightarrow 0).
Step 4: the critical fraction
The network disintegrates when \kappa_p falls to the threshold value 2:
p_c \kappa_0 + (1 - p_c) = 2 \quad \Longrightarrow \quad p_c (\kappa_0 - 1) = 1 \quad \Longrightarrow \quad p_c = \frac{1}{\kappa_0 - 1}.
Here p_c is the fraction that must remain. Converting to the fraction removed, f_c = 1 - p_c:
\boxed{\;f_c = 1 - \frac{1}{\kappa_0 - 1}\;}
which is the formula used in the main text. Note that it depends on the original network only through \kappa_0 — a single number summarizing the entire degree distribution.
The heuristic in the main text gets here in one line. After removing a fraction f, a node you reach still has (1-f)(\kappa - 1) onward edges on average, and the exploration dies out when that branching factor falls to 1:
(1-f_c)(\kappa - 1) = 1 \;\Longrightarrow\; f_c = 1 - \frac{1}{\kappa - 1}.
The derivation above is the same argument done carefully, and it confirms that treating the diluted network as a fresh configuration model is legitimate.
Step 5: reading off the two regimes
Degree-homogeneous (Poisson) networks. For a Poisson distribution with mean \lambda = \langle k \rangle, the second moment is \langle k^2 \rangle = \lambda^2 + \lambda. Hence
\kappa_0 = \frac{\lambda^2 + \lambda}{\lambda} = \lambda + 1 = \langle k \rangle + 1, \qquad f_c = 1 - \frac{1}{(\langle k \rangle + 1) - 1} = 1 - \frac{1}{\langle k \rangle}.
A denser random network is harder to break, but f_c stays strictly below 1: remove enough nodes and it always fragments.
It is tempting to write \langle k^2 \rangle = \langle k \rangle^2 here. That would say the degree variance is zero, which describes a regular graph, not a Poisson one — a Poisson distribution has variance equal to its mean, which is precisely the extra +\lambda term. Dropping it gives \kappa_0 = \langle k \rangle and the wrong threshold 1 - 1/(\langle k \rangle - 1).
Degree-heterogeneous (scale-free) networks. For P(k) \sim k^{-\gamma} with 2 < \gamma < 3, the second moment \langle k^2 \rangle diverges as the network grows. Then \kappa_0 \rightarrow \infty and
f_c = 1 - \frac{1}{\kappa_0 - 1} \rightarrow 1.
Essentially every node must be removed before the giant component dies. This is the mathematical content of the claim that scale-free networks are extraordinarily robust to random failure — and, as the main text shows, it says nothing at all about targeted attack, where those same hubs become the network’s weakness.
Note the scope: the divergence is what makes f_c \rightarrow 1, and it happens only for 2 < \gamma < 3. For \gamma > 3 the second moment is finite, \kappa_0 is an ordinary number, and f_c is strictly below 1. The next step makes both regimes explicit.
Step 6: putting numbers on the heterogeneous case
A real network is finite, so \langle k^2 \rangle is never literally infinite — it is capped by the largest hub. Treat the degree distribution as a continuous power law p(k) = C k^{-\gamma} running from k_{\min} to k_{\max}, with C = (\gamma - 1) k_{\min}^{\gamma-1} fixing the normalisation, and integrate:
\langle k \rangle = C\!\!\int_{k_{\min}}^{k_{\max}}\!\! k^{1-\gamma}\,dk = \frac{\gamma-1}{\gamma-2}\,k_{\min}, \qquad \langle k^2 \rangle = C\!\!\int_{k_{\min}}^{k_{\max}}\!\! k^{2-\gamma}\,dk = C\,\frac{k_{\max}^{3-\gamma} - k_{\min}^{3-\gamma}}{3-\gamma}.
(For \gamma > 2 the upper limit contributes negligibly to \langle k \rangle, so \langle k \rangle is set by k_{\min} alone; for \gamma \le 2 even the average degree diverges, which is why the whole discussion is restricted to \gamma > 2.) Which term of \langle k^2 \rangle dominates depends on the sign of 3 - \gamma, and that is where the two regimes come from:
\kappa = \begin{cases} \dfrac{\gamma-2}{3-\gamma}\, k_{\min}^{\gamma-2}\, k_{\max}^{3-\gamma} & \text{if } 2 < \gamma < 3 \quad (k_{\max}\text{ dominates}) \\[10pt] \dfrac{\gamma-2}{\gamma-3}\, k_{\min} & \text{if } \gamma > 3 \quad (k_{\min}\text{ dominates}). \end{cases}
Feeding each branch into f_c = 1 - 1/(\kappa - 1) gives the critical fraction quoted for heterogeneous networks:
f_c = \begin{cases} 1 - \dfrac{1}{\frac{\gamma-2}{3-\gamma} k_{\min}^{\gamma-2} k_{\max}^{3-\gamma} - 1} & \text{if } 2 < \gamma < 3 \\[10pt] 1 - \dfrac{1}{\frac{\gamma-2}{\gamma-3} k_{\min} - 1} & \text{if } \gamma > 3 . \end{cases}
Reading the two cases:
- For 2 < \gamma < 3, f_c is set by the largest hub. In a growing network k_{\max} grows with N, so \kappa grows without bound and f_c \rightarrow 1. The bigger the network, the harder it is to break by chance.
- For \gamma > 3, f_c is set by the smallest degree k_{\min}, which does not grow with N. So \kappa stays finite, f_c stays below 1, and a fixed fraction of random failures is enough to shatter the network at any size.
Step 7: targeted attack, mapped back onto random failure
An attack is not a random removal, so the results above do not apply directly. Cohen, Erez, ben-Avraham and Havlin (2001) get around this by noticing that removing the top f fraction of nodes does exactly two things to the network, and both can be expressed as changes a random-failure calculation can absorb.
- It truncates the tail. After deleting the highest-degree f fraction, the largest surviving degree is k'_{\max} = k_{\min} f^{\,1/(1-\gamma)} . (Set the fraction of nodes above k'_{\max} equal to f and solve; the exponent is negative for \gamma > 1, so a smaller f leaves a larger surviving hub, as it must.)
- It removes the edges those hubs carried. Those edges had one end on a deleted hub and one end on a surviving node, so from the survivors’ point of view a further fraction of their edges has simply vanished. That is an unbiased thinning of the surviving degrees — the same kind of dilution Step 3 already knows how to handle.
Combining the two and setting \kappa = 2 gives an equation for the attack threshold:
f_c^{\frac{2-\gamma}{1-\gamma}} = 2 + \frac{2-\gamma}{3-\gamma}\, k_{\min} \left(f_c^{\frac{3-\gamma}{1-\gamma}} - 1\right).
This is implicit in f_c — there is no closed form — but for particular \gamma it collapses to something you can solve by hand.
Take \gamma = 2.5 and k_{\min} = 1. The exponents are \frac{2-\gamma}{1-\gamma} = \frac{-0.5}{-1.5} = \tfrac13, \qquad \frac{3-\gamma}{1-\gamma} = \frac{0.5}{-1.5} = -\tfrac13, and the prefactor is (2-\gamma)/(3-\gamma) = -1. Writing x = f_c^{1/3}, the equation becomes
x = 2 - \left(\frac1x - 1\right) = 3 - \frac1x \quad\Longrightarrow\quad x^2 - 3x + 1 = 0 .
The root in (0,1) is x = (3-\sqrt5)/2 \approx 0.382, so f_c = x^3 \approx 0.056. Removing the best-connected 5.6% of nodes destroys the giant component, in a network that random failure could barely dent.
Raising the minimum degree helps a lot: with k_{\min} = 2 the same substitution gives x^2 - 4x + 2 = 0, root x = 2 - \sqrt2 \approx 0.586, hence f_c \approx 0.20. Giving every node a second connection is the cheapest defence there is.
One warning about reading the exponents. It is tempting to say “both exponents are negative for \gamma < 3”, but that is false: at \gamma = 2.5 the exponent (2-\gamma)/(1-\gamma) = +1/3 is positive and only (3-\gamma)/(1-\gamma) = -1/3 is negative. The two sides of the equation therefore move in opposite directions as f_c grows, which is exactly why they cross once, and cross early.
What the proof assumes
Two assumptions are doing real work, and both can fail:
- Local tree-likeness. Real networks contain many triangles (Module 2), and clustering makes the exploration revisit nodes, which slows growth. The criterion is a good approximation for sparse, weakly clustered networks and degrades as clustering rises.
- Randomness beyond the degree sequence. If high-degree nodes preferentially attach to other high-degree nodes (assortativity, Module 4), the branching factor along an edge is no longer \kappa - 1 and the threshold shifts.
References
- Molloy, M., & Reed, B. (1995). A critical point for random graphs with a given degree sequence. Random Structures & Algorithms, 6(2-3), 161-180.
- Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2000). Resilience of the Internet to random breakdowns. Physical Review Letters, 85(21), 4626-4629. [Steps 3-6]
- Cohen, R., Erez, K., ben-Avraham, D., & Havlin, S. (2001). Breakdown of the Internet under intentional attack. Physical Review Letters, 86(16), 3682-3685. [Step 7]
- Newman, M. E. J. (2018). Networks (2nd ed.), Chapter 11. Oxford University Press.