Chapter 7

Percolation

This chapter is devoted to percolation theory, which is the study of connectivity in

large networks. In Section 7.1 we look at ordinary percolation on an infinite lattice,
which is a model for connectedness of a large regular network in which edges are
randomly removed. In Section 7.2 we look at invasion percolation on an infinite
lattice, which is a model for the spread of a virus through a large regular network
in which edges have random transmission capacities. In Section 7.3 we look at the
configuration model and investigate how vulnerable its connectedness is when ver-
tices are being removed, either deterministically or randomly. This is a model for a
“malicious attack” on a network by a “hacker”.
A standard reference for percolation theory is Grimmett [2].

7.1 Ordinary percolation

Consider the d -dimensional integer lattice Zd , d ≥ 2. Draw edges between neigh-
bouring vertices. Associate with each edge e a random variable w(e), drawn in-
dependently from the uniform distribution on (0, 1). This gives a random field of
weights
w = (w(e))e∈(Zd )∗ , (7.1)

where (Zd )∗ is the set of edges (see Fig. 7.1).

Figure 7.1: Z2 (vertices) and (Z2 )∗ (edges) with random weights.

Pick p ∈ [0, 1], and partition Zd into p-clusters by connecting all vertices that are

137
138 CHAPTER 7. PERCOLATION

connected by edges whose weight is ≤ p, i.e.,

p
x ←→y (7.2)

if and only if there is a path π connecting x and y such that w(e) ≤ p for all e ∈ π.
(A path is a collection of neighbouring vertices connected by edges. Note that the
p-clusters are the same as for the model where we retain an edge with probability p
and remove it with probability 1 − p, as we did for the Erdős-Rényi random graph in
Section 2.2.)
Let C p (0) denote the p-cluster containing the origin, and define

θ(p) = P(|C p (0)| = ∞) (7.3)

with P denoting the probability distribution of w, i.e., θ(p) is the probability that the
origin is connected to infinity via edges with weight ≤ p. This is called the percola-
tion function. Given a realisation of the random edge weights we have

C 0 (0) = {0}, C 1 (0) = Zd , p 7→ |C p (0)| is non-decreasing, (7.4)

so that (see Fig. 7.2)

θ(0) = 0, θ(1) = 1, p 7→ θ(p) is non-decreasing. (7.5)

Exercise 7.1 Prove (7.4).

Figure 7.2: Qualitative plot of the percolation function.

Ordinary percolation may serve as a model for the connectedness of a network in

which edges are randomly removed.
Define
p c = sup{p ∈ [0, 1] : θ(p) = 0}. (7.6)

It is known that p c ∈ (0, 1), and that p 7→ θ(p) is continuous for all p ̸= p c and strictly
increasing on (p c , 1). Continuity is expected to hold also at p = p c , but this has only
been proved for d = 2 and d ≥ 11. It is further known that p c = 21 for d = 2 (see
Fig. 7.3), while no explicit expression for p c is known for d ≥ 3. However, good nu-
1
merical approximations are available for p c , as well as expansions in powers of 2d
for d large.
7.2. INVASION PERCOLATION 139

Homework 7.1 Show that p c = 1 for d = 1: no percolation occurs on Z as soon as

edges are removed with a strictly positive probability. What does the analogue of
Fig. 7.2 look like?

At p = p c , called the critical percolation threshold, a phase transition occurs:

p < pc : all clusters are finite,

(7.7)
p > pc : there are infinite clusters.

It is known that in the supercritical phase there is a unique infinite cluster with P-
probability 1.

Exercise 7.2 Why is this uniqueness not obvious?

Figure 7.3: Simulation of ordinary percolation on a 25 × 25 block in Z2 for p = 0.45 and

p = 0.55. The largest cluster is colored red, the second largest cluster blue, the third largest
cluster green. Note that the red cluster spans across the block for p = 0.55 but not for p = 0.45.

7.2 Invasion percolation

Again consider Zd and (Zd )∗ with the random field of weights w. Grow a cluster
from 0 as follows (∥ · ∥ denotes the Euclidean distance on Zd ):

1. Invade the origin: I (0) = {0}.

2. Look at all the edges touching I (0), choose the edge with the smallest weight,
and invade both that edge and the vertex at the other end: I (1) = {0, x}, with
x = argmin y∈Zd : ∥y∥=1 w({0, y}).

3. Repeat 2 with I (1) replacing I (0), etc. (see Fig. 7.4).

In this way we obtain a sequence of growing sets I = (I (n))n∈N0 with I (n) ⊂ Zd the set
of invaded vertices at time n and |I (n)| ≤ n + 1. (The reason for the inequality is that
the vertex at the other end may have been invaded before. The set of invaded edges
140 CHAPTER 7. PERCOLATION

Figure 7.4: The first three steps of the invasion: I (n) for n = 0, 1, 2.

at time n has cardinality n. An invaded edge no longer counts for the probing of the
weights in Step 2 of the growth algorithm, because it cannot be invaded a second
time.) The invasion percolation cluster is defined as

C IPC = lim I (n). (7.8)

n→∞

This is an infinite subset of Zd , which is random because w is random. Note that

the sequence I is uniquely determined by w (because no two edges have the same
weight).
Invasion percolation may serve as a model for the spread of a virus through a
computer network: the virus is “greedy” and invades the network along the weakest
links.
The first question we may ask is whether C IPC = Zd with probability 1. The an-
swer is no:
C IPC ⊊ Zd a.s. (7.9)
(a.s. is an abbreviation for almost surely, which means that the statement is true with
P-probability 1). In fact, C IPC turns out to be an asymptotically thin set, in the sense
that
1
lim |B N ∩C IPC | = 0 a.s. with B N = [−N , N ]d ∩ Zd . (7.10)
N →∞ |B N |

Thus, the virus affects only a small part of the network.

Homework 7.2 Show that C IPC = Z for invasion percolation on Z: all sites of Z get
invaded eventually. Compare with Exercise 7.1.

An interesting fact about invasion percolation is the following. Let Wn denote

the weight of the edge that is traversed in the n-th step of the growth of C IPC , i.e., in
going from I (n − 1) to I (n). Then

lim sup Wn = p c a.s. (7.11)

n→∞

The intuition behind this fact is the following.

First we argue why the limsup is ≤ p c . Pick p ∈ (p c , 1). Then the union of all
the p-clusters contains a unique infinite component (recall Exercise 7.2), which we
denote by C p . Note that the asymptotic density of C p is θ(p) ∈ (0, 1) (see Fig. 7.2) and
that C p does not necessarily contain the origin (see Fig. 7.5). All edges incident to
C p have weight > p. Let τp denote the first time a vertex in C p is invaded:

τp = inf{n ∈ N0 : I (n) ∩C p ̸= ;}. (7.12)

We claim that P (τp < ∞) = 1. Indeed, each time I “breaks out” of the box around
0 it is currently contained in, it sees a “never-before-explored” region containing a
7.2. INVASION PERCOLATION 141

half-space. There is an independent probability θ(p) ∈ (0, 1) that it hits C p at such a

break out time. Therefore it will eventually hit C p with probability 1. (Here we tacitly
use that the critical percolation threshold of the full space is the same as that of the
half-space. This fact is not obvious, but is true nonetheless. It is also the reason why
we look at the times the invasion breaks out of boxes rather than out of the set of
vertices so far invaded.)

Figure 7.5: Picture of invasion percolation becoming trapped inside C p (shaded region). All
edge weights in C p are ≤ p, all edge weights incident to the boundary of C p are > p. The lower
black circle is the origin (the starting location of the invasion). The upper black circle is the
vertex where the invasion enters C p , which occurs at time τp .

Exercise 7.3 Write out the details of the above heuristic proof of P (τp < ∞) = 1. Ex-
plain where we tacitly use that the critical percolation threshold of the full space is
the same as that of the half-space. This fact is not at all obvious. Nonetheless it is true
and therefore was used correctly.

Now, the edge invaded at time τp , being incident to C p , has weight > p. Since the
invasion took place along this edge, all edges incident to I (τp − 1) (which includes
this edge) have weight > p too. Thus, all edges incident to I (τp ) ∪ C p have weight
> p. However, all edges connecting the vertices of C p have weight ≤ p, and so after
time τp the invasion will be “stuck inside C p forever”. Not only does this show that
C IPC = I (τp ) ∪ C p ⊊ Zd , it also shows that Wn ≤ p for all n large enough a.s. Since
p > p c is arbitrary, it follows that

lim sup Wn ≤ p c a.s. (7.13)

n→∞

Next we argue why the reverse inequality holds as well. The proof is by contra-
diction. Indeed, suppose that Wn ≤ p̃ for all n large enough for some p̃ ∈ (0, p c ).
Then
C IPC ⊆ I (σp̃ ) ∪C p̃ (7.14)
with
σp̃ = inf m ∈ N0 : Wn ≤ p̃ ∀ n ≥ m
© ª
(7.15)
the first time from which onwards Wn stays below p̃. Indeed, from time σp̃ onwards
the invasion must stay inside C p̃ . But |C p̃ | < ∞ and |I (σp̃ )| < ∞ a.s., and this contra-
dicts |C IPC | = ∞. Thus, we have proved (7.11).
Note that
1
lim sup |B N ∩C IPC | ≤ θ(p) a.s. ∀ p > pc , (7.16)
N →∞ |B N |
142 CHAPTER 7. PERCOLATION

which proves (7.10) because limp↓p c θ(p) = 0 by the (supposed) continuity of p 7→

θ(p).
The above argument shows that invasion percolation exhibits self-organized crit-
icality: C IPC is in some sense close to C p c for ordinary percolation (see Fig. 7.6). In-
formally this can be expressed by writing

C IPC = lim C p . (7.17)

p↓p c

Thus, even though invasion percolation has no parameter, it behaves as if it were

critical. Very little is known about the probability distribution of C IPC . For further
background, see Angel, Goodman, den Hollander and Slade [1]. It appears that C IPC
5
has fractal dimension 2 − 48 when d = 2.
In Chapter 12 we will encounter two further examples of models that exhibit self-
organized criticality: the sandpile model and the Bak-Sneppen model.

Figure 7.6: Simulation of C IPC on Z2 .

7.3 Vulnerability of the configuration model

Let us leave the world of infinite lattices and return to the world of finite random
graphs. In Chapters 2 and 4 we saw that percolation may occur in the Erdős-Renýi
model and in the configuration model. We found that the critical percolation thresh-
olds in these models are λ = 1 and ν = 1, respectively. Namely, for λ > 1 and ν > 1,
respectively, the largest cluster has size Θ(n) as n → ∞, with n the number of ver-
tices, while for λ < 1 and ν < 1, respectively, it has size Θ(log n).
We focus on the configuration model with n vertices and with vertex degrees
D 1 , . . . , D n that are i.i.d. random variables drawn from a prescribed probability dis-
tribution f . We will be particularly interested in choices of f having a polynomial
tail f (k) ∼ C k −τ , k → ∞, with exponent τ ∈ (3, ∞).
The key quantity determining the occurrence of percolation is (recall (4.6))
P
k∈N k(k − 1) f (k)
ν= P ∈ (0, ∞). (7.18)
k∈N k f (k)

Suppose that ν > 1. We ask ourselves the following question:

7.3. VULNERABILITY OF THE CONFIGURATION MODEL 143

• Given is a sequence π = (π(k))k∈N0 of probabilities, each taking values in [0, 1].

Suppose that a “hacker attacks the network" by randomly removing vertices:
vertex i is retained with probability π(D i ) and is removed with probability
1−π(D i ) (together with all its incident edges), independently for different ver-
tices. After the attack, does the the largest cluster still have size Θ(n) or not?

This question was answered by Janson [3]: The answer is yes if and only if
P
k∈N k(k − 1)π(k) f (k)
ν̄ = P > 1. (7.19)
k∈N k f (k)

Thus, if ν̄ ≤ 1, then the answer is no and we say that the attack was successful.
P
Homework 7.3 Explain heuristically why the denominator in (7.19) is not k∈N0 kπ(k) f (k).
Hint: Recall the argument in Section 4.1.4.

Two choices are of interest:

(1) π(k) = π ∈ (0, 1) for all k ∈ N. This corresponds to a random attack, where the
terrorist removes a fraction 1−π of the vertices without looking at the degrees.

(2) π(k) = 0 for k > k ∗ and π(k) = 1 for k ≤ k ∗ , with k ∗ ∈ N some threshold value.
This corresponds to a deterministic attack, where the terrorist removes all ver-
tices with degree larger than k ∗ .

In case (1) we have ν̄ = πν, and so the attack is successful if and only if π ≤ 1/ν, i.e.,
a fraction 1 − (1/ν) of the vertices is removed. In case (2) we have
P
1≤k≤k ∗ k(k − 1) f (k)
ν̄ = P , (7.20)
k∈N k f (k)

and so the attack is successful if and only if

P
1≤k≤k ∗ k(k − 1) f (k) 1
≤ . (7.21)
ν
P
k∈N k(k − 1) f (k)

k(τ)

2
τ
3

Figure 7.7: Plot of τ 7→ k(τ).

For the special case where f (k) = k −τ /ζ(τ), k ∈ N, with ζ the Riemann zeta-
function given by ζ(τ) = k∈N k −τ , the denominator in the left-hand side of (7.21)
P

equals
1
[ζ(τ − 2) − ζ(τ − 1)], (7.22)
ζ(τ)
144 CHAPTER 7. PERCOLATION

while the denominator minus the numerator scales like

1
[1 + o(1)] k −(τ−3) , k ∗ → ∞. (7.23)
(τ − 3)ζ(τ) ∗

This gives us the approximate criterion that the attack is successful if and only if
k ∗ ⪅ k(τ) with

1 −1/(τ−3)
· µ ¶¸
k(τ) = (τ − 3) ζ(τ − 2) − ζ(τ − 1) 1 −
© ª
. (7.24)
ν

We have from (7.24) that (see Fig. 7.7)

lim k(τ) = ∞, lim k(τ) = 2. (7.25)

τ↓3 τ→∞

Thus, for τ ↓ 3 the network becomes extremely vulnerable because only few vertices
with a high degree need to be removed in order to take down the network, while for
τ → ∞ the network becomes extremely robust because all vertices with degree > 2
need to be removed in order to take down the network.

Exercise 7.4 Prove (7.25). Hint: Show that limu↓1 (u−1)ζ(u) = 1 and limu→∞ 2u [ζ(u−
1) − ζ(u)] = 1.

Take home message: Ordinary percolation serves as a model for the

connectedness of a random network, invasion percolation as a model
for the spread of a virus through a random network. The percolation
transition shows up in both. Greedy invasion manages to affect only a
thin part of the network. For the configuration model under attack by
a hacker, vulnerability increases as the network is given more hubs.
Bibliography

[1] O. Angel, J. Goodman, F. den Hollander and G. Slade, Invasion percolation on

regular trees, Ann. Probab. 36 (2008) 420–466.

[2] G.R. Grimmett, Percolation, Springer, Berlin, 1989.

[3] S. Janson, On percolation in random graphs with given vertex degrees, Elec-
tronic J. Probab. 14 (2009) 86–118.

145