In
statistical physics and
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, percolation theory describes the behavior of a network when nodes or links are added. This is a geometric type of phase transition, since at a critical fraction of addition the network of small, disconnected clusters merge into significantly larger
connected, so-called spanning clusters. The applications of percolation theory to
materials science and in many other disciplines are discussed here and in the articles
network theory
Network theory is the study of graphs as a representation of either symmetric relations or asymmetric relations between discrete objects. In computer science and network science, network theory is a part of graph theory: a network can be de ...
and
percolation.
Introduction
A representative question (and the
source of the name) is as follows. Assume that some liquid is poured on top of some
porous material. Will the liquid be able to make its way from hole to hole and reach the bottom? This physical question is
modelled mathematically as a
three-dimensional network of
vertices, usually called "sites", in which the
edge or "bonds" between each two neighbors may be open (allowing the liquid through) with probability , or closed with probability , and they are assumed to be independent. Therefore, for a given , what is the probability that an open path (meaning a path, each of whose links is an "open" bond) exists from the top to the bottom? The behavior for large is of primary interest. This problem, called now bond percolation, was introduced in the mathematics literature by ,
and has been studied intensively by mathematicians and physicists since then.
In a slightly different mathematical model for obtaining a random graph, a site is "occupied" with probability or "empty" (in which case its edges are removed) with probability ; the corresponding problem is called site percolation. The question is the same: for a given ''p'', what is the probability that a path exists between top and bottom? Similarly, one can ask, given a connected graph at what fraction of failures the graph will become disconnected (no large component).
The same questions can be asked for any lattice dimension. As is quite typical, it is actually easier to examine
infinite networks than just large ones. In this case the corresponding question is: does an infinite open cluster exist? That is, is there a path of connected points of infinite length "through" the network? By
Kolmogorov's zero–one law
In probability theory, Kolmogorov's zero–one law, named in honor of Andrey Nikolaevich Kolmogorov, specifies that a certain type of event, namely a ''tail event of independent σ-algebras'', will either almost surely happen or almost sure ...
, for any given , the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of (proof via
coupling argument), there must be a critical (denoted by ) below which the probability is always 0 and above which the probability is always 1. In practice, this criticality is very easy to observe. Even for as small as 100, the probability of an open path from the top to the bottom increases sharply from very close to zero to very close to one in a short span of values of .
History
The
Flory–Stockmayer theory
Flory–Stockmayer theory is a theory governing the cross-linking and gelation of step-growth polymers.Flory, P.J. (1941). "Molecular Size Distribution in Three Dimensional Polymers I. Gelation". ''J. Am. Chem. Soc.'' 63, 3083 The Flory-Stockmayer ...
was the first theory investigating percolation processes.
The history of the percolation model as we know it has its root in the coal industry. Since the industrial revolution, the economical importance of this source of energy fostered many scientific studies to understand its composition and optimize its use. During the 30' and 40', the qualitative analysis by organic chemistry left more and more room to more quantitative studies.
In this context, the
British Coal Utilisation Research Association
British Coal Utilisation Research Association (BCURA) was a non-profit association of industrial companies, incorporated 23 April 1938 and dissolved 24 February 2015.
History
It was founded in 1938, with an assured income of £25000 per year for ...
(BCURA) was created in 1938. It is a research association funded by the coal mines owners. In 1942,
Rosalind Franklin
Rosalind Elsie Franklin (25 July 192016 April 1958) was a British chemist and X-ray crystallographer whose work was central to the understanding of the molecular structures of DNA (deoxyribonucleic acid), RNA (ribonucleic acid), viruses, ...
, who then recently graduated in chemistry from the university of Cambridge, joined the BCURA. She started research on the density and porosity of coal. During the Second World War, coal was an important strategic resource. It was used as a source of energy, but also was the main constituent of gas masks.
Coal is a porous medium. To measure its 'real' density, one was to sink it in a liquid or a gas whose molecule are small enough to fill its microscopic pores. While trying to measure the density of coal using several gases (helium, methanol, hexane, benzene) and as she found different values depending on the used gas, Rosalind Franklin showed that the pores of coal are made of microstructures of various lengths that act as a microscopic sieve to discriminate the gases. She also discovered that the size of these structures depends on the temperature of carbonation during the coal production. With these research, she obtained a PhD degree and she left the BCURA in 1946.
In the mid fifties, Simon Broadbent worked in the BCURA as a statistician. Among other interests, he studied the use of coal in gas masks. One question is to understand how a fluid can diffuse in the coal pores, modeled as a random maze of open or closed tunnels. In 1954, during a symposium on
Monte Carlo methods, he asks questions to
John Hammersley
John Michael Hammersley, (21 March 1920 – 2 May 2004) was a British mathematician best known for his foundational work in the theory of self-avoiding walks and percolation theory.
Early life and education
Hammersley was born in Helensbur ...
on the use of numerical methods to analyze this model.
Broadbent and Hammersley introduced in their article of 1957 a mathematical model to model this phenomenon, that is percolation.
Computation of the critical parameter
For most infinite lattice graphs, cannot be calculated exactly, though in some cases there is an exact value. For example:
*for the
square lattice
In mathematics, the square lattice is a type of lattice in a two-dimensional Euclidean space. It is the two-dimensional version of the integer lattice, denoted as . It is one of the five types of two-dimensional lattices as classified by thei ...
in two dimensions, for bond percolation, a fact which was an open question for more than 20 years and was finally resolved by
Harry Kesten
Harry Kesten (November 19, 1931 – March 29, 2019) was an American mathematician best known for his work in probability, most notably on random walks on groups and graphs, random matrices, branching processes, and percolation theory.
Biog ...
in the early 1980s,
see . For site percolation, the value of is not known from analytic derivation but only via simulations of large lattices.
*A limit case for lattices in high dimensions is given by the
Bethe lattice
In statistical mechanics and mathematics, the Bethe lattice (also called a regular tree) is an infinite connected cycle-free graph where all vertices have the same number of neighbors. The Bethe lattice was introduced into the physics literature ...
, whose threshold is at for a
coordination number . In other words: for the regular
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
of degree
,
is equal to
.
* For a random
tree-like network without degree-degree correlation, it can be shown that such network can have a
giant component, and the
percolation threshold (transmission probability) is given by
, where
is the
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
corresponding to the
excess degree distribution. So, for random
Erdős–Rényi networks of average degree
, .
* In networks with low
clustering,
, the critical point gets scaled by
such that:
This indicates that for a given degree distribution, the clustering leads to a larger percolation threshold, mainly because for a fixed number of links, the clustering structure reinforces the core of the network with the price of diluting the global connections. For networks with high clustering, strong clustering could induce the core–periphery structure, in which the core and periphery might percolate at different critical points, and the above approximate treatment is not applicable.
Universality
The
universality principle states that the numerical value of is determined by the local structure of the graph, whereas the behavior near the critical threshold, , is characterized by universal
critical exponents. For example the distribution of the size of clusters at criticality decays as a power law with the same exponent for all 2d lattices. This universality means that for a given dimension, the various critical exponents, the
fractal dimension of the clusters at is independent of the lattice type and percolation type (e.g., bond or site). However, recently percolation has been performed on a
weighted planar stochastic lattice (WPSL) and found that although the dimension of the WPSL coincides with the dimension of the space where it is embedded, its universality class is different from that of all the known planar lattices.
Phases
Subcritical and supercritical
The main fact in the subcritical phase is "exponential decay". That is, when , the probability that a specific point (for example, the origin) is contained in an open cluster (meaning a maximal connected set of "open" edges of the graph) of size decays to zero
exponentially in . This was proved for percolation in three and more dimensions by and independently by . In two dimensions, it formed part of Kesten's proof that .
The
dual graph of the square lattice is also the square lattice. It follows that, in two dimensions, the supercritical phase is dual to a subcritical percolation process. This provides essentially full information about the supercritical model with . The main result for the supercritical phase in three and more dimensions is that, for sufficiently large , there is an infinite open cluster in the two-dimensional slab . This was proved by .
In two dimensions with , there is with probability one a unique infinite closed cluster (a closed cluster is a maximal connected set of "closed" edges of the graph). Thus the subcritical phase may be described as finite open islands in an infinite closed ocean. When just the opposite occurs, with finite closed islands in an infinite open ocean. The picture is more complicated when since , and there is coexistence of infinite open and closed clusters for between and .
Criticality
Percolation has a
singularity at the critical point and many properties behave as of a power-law with
, near
.
Scaling theory predicts the existence of
critical exponents, depending on the number ''d'' of dimensions, that determine the class of the singularity. When these predictions are backed up by arguments from
conformal field theory and
Schramm–Loewner evolution
In probability theory, the Schramm–Loewner evolution with parameter ''κ'', also known as stochastic Loewner evolution (SLE''κ''), is a family of random planar curves that have been proven to be the scaling limit of a variety of two-dimensional ...
, and include predicted numerical values for the exponents. Most of these predictions are conjectural except when the number of dimensions satisfies either or . They include:
* There are no infinite clusters (open or closed)
* The probability that there is an open path from some fixed point (say the origin) to a distance of decreases ''polynomially'', i.e. is
on the order of
An order of magnitude is an approximation of the logarithm of a value relative to some contextually understood reference value, usually 10, interpreted as the base of the logarithm and the representative of values of magnitude one. Logarithmic d ...
for some
** does not depend on the particular lattice chosen, or on other local parameters. It depends only on the dimension (this is an instance of the
universality principle).
** decreases from until and then stays fixed.
**
** .
* The shape of a large cluster in two dimensions is
conformally invariant.
See .
In 11 or more dimensions, these facts are largely proved using a technique known as the
lace expansion. It is believed that a version of the lace expansion should be valid for 7 or more dimensions, perhaps with implications also for the threshold case of 6 dimensions. The connection of percolation to the lace expansion is found in .
In two dimensions, the first fact ("no percolation in the critical phase") is proved for many lattices, using duality. Substantial progress has been made on two-dimensional percolation through the conjecture of
Oded Schramm
Oded Schramm ( he, עודד שרם; December 10, 1961 – September 1, 2008) was an Israeli-American mathematician known for the invention of the Schramm–Loewner evolution (SLE) and for working at the intersection of conformal field theory ...
that the
scaling limit
In mathematical physics and mathematics, the continuum limit or scaling limit of a lattice model refers to its behaviour in the limit as the lattice spacing goes to zero. It is often useful to use lattice models to approximate real-world process ...
of a large cluster may be described in terms of a
Schramm–Loewner evolution. This conjecture was proved by
in the special case of site percolation on the triangular lattice.
Different models
*
Directed percolation that models the effect of
gravitational forces acting on the liquid was also introduced in ,
and has connections with the
contact process
The contact process is the current method of producing sulfuric acid in the high concentrations needed for industrial processes. Platinum was originally used as the catalyst for this reaction; however, as it is susceptible to reacting with arsenic ...
.
*The first model studied was Bernoulli percolation. In this model all bonds are independent. This model is called bond percolation by physicists.
*A generalization was next introduced as the
Fortuin–Kasteleyn random cluster model, which has many connections with the
Ising model
The Ising model () (or Lenz-Ising model or Ising-Lenz model), named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent ...
and other
Potts models.
*Bernoulli (bond) percolation on
complete graphs is an example of a
random graph. The critical probability is , where is the number of vertices (sites) of the graph.
*
Bootstrap percolation removes active cells from clusters when they have too few active neighbors, and looks at the connectivity of the remaining cells.
*
First passage percolation First passage percolation is a mathematical method used to describe the paths reachable in a random medium within a given amount of time.
Introduction
First passage percolation is one of the most classical areas of probability theory. It was first ...
.
*
Invasion percolation Invasion percolation is a mathematical model of realistic fluid distributions for slow immiscible fluid invasion in porous media, in percolation theory
In statistical physics and mathematics, percolation theory describes the behavior of a netwo ...
.
Applications
In biology, biochemistry, and physical virology
Percolation theory has been used to successfully predict the fragmentation of biological virus shells (capsids),
with the fragmentation threshold of
Hepatitis B virus
capsid predicted and detected experimentally. When a critical number of subunits has been randomly removed from the nanoscopic shell, it fragments and this fragmentation may be detected using Charge Detection Mass Spectroscopy (CDMS) among other single-particle techniques. This is a molecular analog to the common board game
Jenga, and has relevance to the broader study of virus disassembly. Interestingly, more stable viral particles (tilings with greater fragmentation thresholds) are found in greater abundance in nature.
In ecology
Percolation theory has been applied to studies of how environment fragmentation impacts animal habitats and models of how the plague bacterium ''
Yersinia pestis'' spreads.
See also
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
References
*
*
Further reading
*
*
*
External links
PercoVIS: a program to visualize percolation on networks in real timeNanohub online course on ''Percolation Theory''
{{Stochastic processes