In statistical physics and mathematics, percolation theory describes the behavior of a network when nodes or links are removed. This is a type of phase transition, since at a critical fraction of removal the network breaks into significantly smaller connected clusters. The applications of percolation theory to materials science and in many other disciplines are discussed here and in the articles network theory and percolation.
Introduction
The Flory–Stockmayer theory was the first theory investigating percolation processes. A representative question 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 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 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" 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. 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, for any given, the probability that an infinite cluster exists is either zero or one. Since this probability is an increasing function of , there must be a critical 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 . 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 two dimensions, for bond percolation, a fact which was an open question for more than 20 years and was finally resolved by Harry Kesten in the early 1980s, see. For site percolation, the value of is not known analyticity but only via simulations of large lattices.
A limit case for lattices in many dimensions is given by the Bethe lattice, whose threshold is at for a coordination number . In other words: for the regular tree of degree, is equal to.
For random Erdős–Rényi networks of average degree,.
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 exponents 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. However, recently percolation has been performed on a weighted planar stochastic lattice 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 is contained in an open cluster 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. 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 . For the phase transition nature of percolation see Stauffer and Aharony and Bunde and Havlin . For percolation of networks see Cohen and Havlin.
Critical
Percolation has a singularity at the critical point and many properties behave as a of 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, and include predicted numerical values for the exponents. The values of the exponent are given in. Most of these predictions are conjectural except when the number of dimensions satisfies either or. They include:
There are no infinite clusters
The probability that there is an open path from some fixed point to a distance of decreases polynomially, i.e. is on the order of for some
* does not depend on the particular lattice chosen, or on other local parameters. It depends only on the dimension .
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 is proved for many lattices, using duality. Substantial progress has been made on two-dimensional percolation through the conjecture of Oded Schramm that the scaling limit 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.
Bernoulli percolation on complete graphs is an example of a random graph. The critical probability is , where is the number of vertices 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.
Invasion percolation.
Percolation with dependency links was introduced by Parshani et al.
Percolation and opinion spreading model.
Percolation under localized attack was introduced by Berezin et al. See also Shao et al.
Percolation of traffic in cities was introduced by Daqing Li et al.
Introducing recovery of nodes and links in percolation.
Percolation in 2d with a characteristic link length. This percolation show a novel phenomena of critical stretching phenomena near critical percolation.
A generalized percolation model that introduces a fraction of reinforced nodes in a network that can function and support their neighborhood was introduced by Yanqing Hu et al.
Applications
In biology, biochemistry (physical virology), and nanomedicine
Percolation theory has been used to successfully predict the fragmentation of biological virus shells , with the percolation threshold of Hepatitis B viruscapsid 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 among other single-particle techniques. This is a molecular analog to the common board gameJenga, and has relevance to virus disassembly.
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.
