Statistical mechanics, structure of matter Percolation and random geometry Example

Invasion percolation

Builds on Percolation theory Percolation threshold Prim's algorithm Minimum spanning tree Self-organized criticality

Example

Let $G = (V, E)$ be an infinite connected graph with finite degrees, and let $o \in V$ . Give each edge $e$ an independent weight $U(e)$ , uniform on $[0, 1]$ ; almost surely all weights are distinct. Invasion percolation from $o$ builds clusters $I_0 \subset I_1 \subset \cdots$ . Start with $I_0 = \set{o}$ . Given $I_n$ , choose the edge of smallest weight among the edges with exactly one endpoint in $I_n$ . Let $I_{n+1}$ be $I_n$ together with the other endpoint of that edge. The invasion cluster is $I_\infty = \bigcup_n I_n$ .

Check on $G = \Z$ with $o = 0$ and weights $U(\set{-2, -1}) = 0.2$ , $U(\set{-1, 0}) = 0.7$ , $U(\set{0, 1}) = 0.4$ , $U(\set{1, 2}) = 0.9$ . Step 1 compares $0.7$ and $0.4$ and adds the vertex $1$ . Step 2 compares $0.7$ and $0.9$ and adds $-1$ . Step 3 compares $0.2$ and $0.9$ and adds $-2$ . After crossing the high weight $0.7$ , the invasion at once uses the low weight $0.2$ behind it.

Remarks

The rule is the same as Prim's algorithm for a minimum spanning tree, run on an infinite graph from $o$ ; see Prim's algorithm. For $p \in [0, 1]$ , the edges with $U(e) \le p$ form bond percolation with parameter $p$ , so the model couples all values of $p$ at once. Let $d \ge 2$ , and let $p$ be above the percolation threshold $p_c$ of $\Z^d$ . On $\Z^d$ the invasion eventually reaches the infinite cluster of edges with weight at most $p$ . From then on it never accepts an edge of weight larger than $p$ . So the invasion finds the critical value by itself, without any parameter being tuned, and its cluster looks like a large critical percolation cluster. This makes it a standard example of self-organized criticality.

Reading path

To understand this page from the ground up, read these 6 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`2KKXVKFN16`
URI	`m2://2KKXVKFN16`
Kind	example
Writing	W0 stub
MSC	82B43, 60K35
Illustrates	Percolation theory
Uses	Percolation theory, Percolation threshold, Prim's algorithm, Minimum spanning tree, Self-organized criticality
Same as	Wikidata Q24902133 Wikipedia Invasion percolation
Changed	3 November 2026

Invasion percolation

Example

Remarks

Reading path

Further reading

What this page needs for W1

What links here