Percolation Theory
==================
Introduction
------------
Percolation theory characterizes how global connectivity emerges in a system of
a large number of objects.
These objects connect according to some local rule constrained by an underlying
topology.
Thus, given the topology and the local rule, percolation theory yields the
global, emergent behavior :cite:`Hunt2014Percolation`.
Early occurrences of percolation theory in the literature include the classic
works by Flory and Stockmayer on polymerization and the sol-gel transition
:cite:`Flory1941Molecular,Stockmayer1943Theory`.
However, it is only later that a theory of percolation starts to condense
:cite:`Broadbent1957Percolation`.
**Definition** (:cite:`Hunt2014Percolation`, p. 2):
We say a system *is at percolation*, or *percolates*, if sufficiently many
objects are connected locally such that a global connection emerges.
This global connection is a continuous "chain" or "cluster" of locally
connected objects, which is unbounded in size (in infinite systems), or of the
order of the system size (in finite systems).
Typically, percolation also refers to a stochastic process of increasing
connectivity and eventual emergence of the giant cluster.
In an infinite system, this emergence in an ensemble of system configurations
constitutes a phase transition.
In fact, percolation is a phase transition paradigm
:cite:`Stauffer1994Introduction`.
The central quantity in percolation settings is the cluster size distribution
:math:`n_s`, which we will introduce shortly.
The setting of percolation is a graph.
A typical setting is a regular lattice of sites connected to their nearest
neighbors.
In *site percolation*, all sites are subsequently *occupied*.
In *bond percolation*, it is the bonds that are subsequently added to form a
giant cluster of connected sites.
In the following, we introduce the concepts and notation mainly according to
Stauffer's and Aharony's classical textbook :cite:`Stauffer1994Introduction`.
The cluster size distribution
-----------------------------
In the regular lattice setting, a *cluster* is a maximum set of occupied sites
which are pairwise joined by paths on the lattice only traversing occupied
sites.
In general, a *cluster* is component of the graph.
The *size* :math:`s` of a cluster is the number of nodes in the component.
Note that infinite graphs allow for infinite cluster sizes.
The occupation of sites, or the cluster sizes, typically depend on a (global)
system parameter.
For example, the paradigmatic percolation model is that of each site
independently being occupied with some probability :math:`p` (Bernoulli percolation).
All the following statistics only require the general percolation setting of a
graph.
Let :math:`\varrho` denote the system parameter.
**Definition**:
For any given cluster size :math:`s`, let the *cluster number*
:math:`n_s(\varrho, L)` be the *density* of clusters of size :math:`s` with
respect to the system size :math:`L`.
In other words, in a system of :math:`L` sites, the cluster number
:math:`n_s(\varrho, L)` is the number :math:`N_s(\varrho, L)` of clusters of
size :math:`s` divided by the total number :math:`L` of sites,
.. math::
n_s(\varrho, L) = \frac{N_s(\varrho,L)}{L}.
This definition also applies to systems of infinite size as
.. math::
n_s(\varrho) = \lim_{L \to \infty} \frac{N_s(\varrho,L)}{L}.
*The cluster size distribution* :math:`n_s` *is the fundamental quantity in
percolation theory*.
Percolation threshold and characteristic cluster size
-----------------------------------------------------
Typically, in an infinite system the largest cluster grows with increasing
parameter :math:`\varrho`, and at some critical value :math:`\varrho_c`, an
infinite cluster appears.
This number :math:`\varrho_c` is the *percolation threshold*.
At and above :math:`\varrho_c`, there is an infinite cluster, and the system is
said to *percolate*.
The probability that a system of size :math:`L` percolates at parameter
:math:`\varrho`, i.e. has a cluster of order of the system size, is
:math:`\Pi(\varrho,L)`.
In the infinite system, we have
.. math::
\Pi(\varrho) = \lim_{L \to \infty} \Pi(\varrho, L) = \begin{cases}
0 & \varrho < \varrho_c, \\
1 & \varrho \geq \varrho_c.
\end{cases}
The *percolation strength* :math:`P(\varrho, L)` is the fraction of sites
belonging to the infinite cluster.
In the infinite system, the limit strength :math:`P(\varrho) = \lim_{L \to
\infty} P(\varrho, L)` is the typical *order parameter* of the percolation
transition.
The cluster size distribution typically is of the form
.. math::
n_s(\varrho) \sim s^{-\tau} e^{- s/s_\xi}, \qquad (s \to \infty)
for large :math:`s` and with some characteristic cluster size :math:`s_\xi`.
At the percolation transition, the characteristic cluster size :math:`s_\xi`
diverges as a power law,
.. math::
s_\xi \sim |\varrho_c - \varrho|^{-1/\sigma}, \qquad (\varrho \to \varrho_c)
with the *critical exponent* :math:`\sigma`.
In general, clusters of size :math:`s < s_\xi \sim |\varrho - \varrho_c|^{-1 /
\sigma}` dominate the moments of the cluster size distribution.
These clusters effectively follow a power-law distribution :math:`n_s(\varrho)
\sim s^{-\tau}`, as all clusters at the critical point :math:`n_s(\varrho_c)
\sim s^{-\tau}`.
For :math:`s \gg s_\xi`, the distribution is cut off exponentially.
Thus, clusters in this regime do not exhibit "critical" behavior.
Average cluster size
--------------------
For any given site, the probability that it is part of a cluster of size
:math:`s` is :math:`s n_s`. The *occupation probability*
:math:`p(\varrho, L)` is the probability that any given site is part of
a finite cluster, in a system of size :math:`L` (may be infinite) at
parameter :math:`\varrho`,
.. math::
p(\varrho, L) = \sum_{s=1}^\infty s n_s(\varrho, L) = M_1(\varrho, L),
which is the first moment of the cluster size distribution.
Hence, for any given site of any given finite cluster, the probability
:math:`w_s(\varrho, L)` that the cluster is of size :math:`s`, is
.. math::
w_s(\varrho, L) = \frac{1}{p(\varrho,L)} s n_s(\varrho, L),
with :math:`\sum_{s=1}^\infty w_s(\varrho, L) = 1`.
For any given site of any given finite cluster, the average size
:math:`S(\varrho, L)` of the cluster is
.. math::
S(\varrho, L) = \sum_{s=1}^\infty s w_s(\varrho, L) = \frac{1}{p(\varrho,
L)} \sum_{s=1}^\infty s^2 n_s(\varrho, L) = \frac{M_2(\varrho,
L)}{M_1(\varrho, L)},
which is the second moment divided by the first moment of the cluster size
distribution.
Note that this average is different from the average of the (finite) cluster
sizes in the system.
The *average cluster size* :math:`S(\varrho, L)` is defined with respect to a
site, and thus, it is an intensive quantity :cite:`Stauffer1994Introduction`.
Note that for infinite systems (:math:`L\to\infty`), these statistics exclude
the infinite cluster.
At the critical point, the average cluster size :math:`S(\varrho_c)`
nevertheless diverges as
.. math::
S(\varrho) \sim |\varrho - \varrho_c|^{- \gamma}, \qquad (\varrho \to
\varrho_c)
with the *critical exponent* :math:`\gamma`.
As :math:`S` is the second moment of the cluster size distribution (up to a
factor), it is a measure of fluctuations in the system.
*Thus, divergence of* :math:`S` *actually defines the percolation phase
transition.*
Correlation length
------------------
The *correlation function* :math:`g(\mathbf{r})` is the probability that a site
at position :math:`\mathbf{r}` from an occupied site in a *finite* cluster
belongs to the same cluster.
Typically, for large :math:`r \equiv |\mathbf{r}|`, there is an exponential
cutoff, i.e. :math:`g(\mathbf{r}) \sim e^{-r/\xi}`, at the *correlation length*
:math:`\xi`.
**Definition**:
The *correlation length* :math:`\xi` is defined as
.. math::
\xi^2 = \frac{\sum_{\mathbf{r}} r^2 g(\mathbf{r})}{\sum_{\mathbf{r}}
g(\mathbf{r})}.
For a cluster of size :math:`s`, its *radius of gyration* :math:`R_s` is
defined as the average square distance to the cluster center of mass
:cite:`Stauffer1994Introduction`.
It turns out that :math:`2 R_s^2` is the average square distance between two
sites of the same (finite) cluster.
Averaging over :math:`2R_s^2` yields the squared correlation length
:cite:`Stauffer1994Introduction`,
.. math::
\xi^2 = \frac{\sum_s 2 R_s^2 s^2 n_s}{\sum_s s^2 n_s},
since :math:`s^2 n_s` is the weight of clusters of size :math:`s`.
Hence, the correlation length is the radius of the clusters that dominate the
second moment of the cluster size distribution, or, the fluctuations.
The divergence of quantities at the critical point involves sums over all
cluster sizes :math:`s`.
The cutoff of the cluster number :math:`n_s` at :math:`s_\xi \sim |\varrho -
\varrho_c|^{-1/\sigma}` marks the *cluster sizes* :math:`s \approx s_\xi` that
contribute the most to the sums and hence, to the divergence.
This also holds for the correlation length :math:`\xi`, which is the radius of
those clusters of sizes :math:`s \approx s_\xi`.
As such, this is the one and only length scale which characterizes the behavior
of an infinite system in the critical region :cite:`Stauffer1994Introduction`.
The correlation length :math:`\xi` defines the relevant length scale.
As :math:`\xi` diverges at :math:`\varrho \to \varrho_c`, a length scale
is absent at the percolation transition :math:`\varrho = \varrho_c`.
This lack of a relevant length scale is a typical example of *scale
invariance*.
This implies that the system appears to be self-similar on length scales
smaller than :math:`\xi`.
As :math:`\xi` becomes infinite at :math:`\varrho_c`, the whole system becomes
self-similar.
The lack of a relevant length scale also implies that functions of powers
(*power laws*) describe the relevant quantities in the critical region.
In particular, the correlation length itself diverges as a power law,
.. math::
\xi \sim (\varrho - \varrho_c)^{-\nu}. \qquad (\varrho \to \varrho_c)
The form of this divergence is the same in all systems, which is called
*universal* behavior.
The *critical exponent* :math:`\nu` depends only on general features of the
topology and the local rule, giving rise to *universality classes* of systems
with the same critical exponents.
Scaling relations
-----------------
The scaling theory of percolation clusters relates the critical exponents of
the percolation transition to the cluster size distribution
:cite:`Stauffer1979Scaling`.
As the critical point lacks any length scale, the cluster sizes also need to
follow a power law,
.. math::
n_s(\varrho_c) \sim s^{-\tau}, \qquad (\varrho \to \varrho_c, s \gg 1)
with the *Fisher exponent* :math:`\tau` :cite:`Fisher1967Theory`.
The scaling assumption is that the ratio :math:`n_s(\varrho) / n_s(\varrho_c)`
is a function of the ratio :math:`s / s_\xi(\varrho)` only
:cite:`Stauffer1979Scaling`,
.. math::
\frac{n_s(\varrho)}{n_s(\varrho_c)} = f\left( \frac{s}{s_\xi(\varrho)}
\right), \qquad (\varrho \to \varrho_c, s \gg 1).
As in the critical region, the characteristic cluster size diverges as
:math:`s_\xi \sim |\varrho - \varrho_c|^{-1/\sigma}`, we have :math:`s /
s_\xi(\varrho) \sim |(\varrho - \varrho_c) s^\sigma |^{1/\sigma}`, and hence
.. math::
n_s(\varrho) \sim s^{-\tau} f((\varrho - \varrho_c) s^\sigma), \qquad
(\varrho \to \varrho_c, s \gg 1),
with some scaling function :math:`f` which rapidly decays to zero, :math:`f(x)
\to 0` for :math:`|x| > 1` (:math:`s > s_\xi`)
:cite:`Stauffer1994Introduction`.
It remains to determine the scaling relationship of cluster radius :math:`R_s`
and cluster size :math:`s` in the critical region.
For :math:`s \sim R_s^D` for some possibly fractal cluster dimension :math:`D`,
we have :cite:`Stauffer1994Introduction`
.. math::
\frac{1}{D} = \sigma \nu.
The cutoff cluster size :math:`s_\xi` was the *crossover size* separating
critical behavior (:math:`n_s \sim s^{-\tau}`) from non-critical behavior
(:math:`n_s \to 0` exponentially fast).
Now, the correlation length :math:`\xi \sim s_\xi^{1/D} = s_\xi^{\sigma \nu}`
is the *crossover length* separating the critical and non-critical regimes.
The following scaling law relates the system dimensionality :math:`d` and the
fractal dimensionality :math:`D = \frac{1}{\sigma \nu}` of the infinite cluster
to the exponents of the cluster size distribution :cite:`Hunt2014Percolation`:
.. math::
\frac{\tau - 1}{\sigma \nu} = d, \qquad \tau = 1 + \frac{d}{D}
Consider the :math:`k`-th raw moment of the cluster size distribution
.. math::
M_k(\varrho) = \sum_s s^k n_s(\varrho)
which scales as
.. math::
M_k(\varrho) \sim \sum_s s^{k-\tau} e^{-s/s_\xi(\varrho)} \sim |\varrho -
\varrho_c|^{(\tau -1 - k)/\sigma} \qquad (\varrho \to \varrho_c)
in the critical region.
In this region, above the percolation threshold (:math:`\varrho > \varrho_c`),
the percolation strength behaves as :cite:`Stauffer1994Introduction`
.. math::
P(\varrho) \sim \sum_s s (n_s(\varrho_c) - n_s(\varrho)) \sim \sum_s
s^{1-\tau} \left(1 - e^{-s/s_\xi(\varrho)} \right) \sim (\varrho -
\varrho_c)^{(\tau -2)\sigma} \equiv (\varrho - \varrho_c)^\beta
defining the *critical exponent* :math:`\beta` as
.. math::
\beta = \frac{\tau - 2}{\sigma}.
As the second raw moment :math:`M_2(\varrho) \sim |\varrho - \varrho_c|^{(\tau
- 3)/\sigma}`, we have
.. math::
\gamma = \frac{3 - \tau}{\sigma},
or
.. math::
\sigma = \frac{1}{\beta + \gamma}, \tau = 2 + \frac{\beta}{\beta + \gamma}.
These are the *scaling relations* between the critical exponents, which all
derive from the exponents :math:`\tau` and :math:`\sigma` of the cluster size
distribution.