Percolation threshold

The percolation threshold is a mathematical concept in percolation theory that describes the formation of long-range connectivity in random systems. Below the threshold a giant connected component does not exist; while above it, there exists a giant component of the order of system size. In engineering and coffee making, percolation represents the flow of fluids through porous media, but in the mathematics and physics worlds it generally refers to simplified lattice models of random systems or networks (graphs), and the nature of the connectivity in them. The percolation threshold is the critical value of the occupation probability p, or more generally a critical surface for a group of parameters p1, p2, ..., such that infinite connectivity (percolation) first occurs.

Percolation models The most common percolation model is to take a regular lattice, like a square lattice, and make it into a random network by randomly "occupying" sites (vertices) or bonds (edges) with a statistically independent probability p. At a critical threshold pc, large clusters and long-range connectivity first appear, and this is called the percolation threshold. Depending on the method for obtaining the random network, one distinguishes between the site percolation threshold and the bond percolation threshold. More general systems have several probabilities p1, p2, etc., and the transition is characterized by a critical surface or manifold. One can also consider continuum systems, such as overlapping disks and spheres placed randomly, or the negative space (Swiss-cheese models). To understand the threshold, you can consider a quantity such as the probability that there is a continuous path from one boundary to another along occupied sites or bonds—that is, within a single cluster. For example, one can consider a square system, and ask for the probability P that there is a path from the top boundary to the bottom boundary. As a function of the occupation probability p, one finds a sigmoidal plot that goes from P=0 at p=0 to P=1 at p=1. The larger the square is compared to the lattice spacing, the sharper the transition will be. When the system size goes to infinity, P(p) will be a step function at the threshold value pc. For finite large systems, P(pc) is a constant whose value depends upon the shape of the system; for the square system discussed above, P(pc)=1⁄2 exactly for any lattice by a simple symmetry argument. There are other signatures of the critical threshold. For example, the size distribution (number of clusters of size s) drops off as a power-law for large s at the threshold, ns(pc) ~ s−τ, where τ is a dimension-dependent percolation critical exponents. For an infinite system, the critical threshold corresponds to the first point (as p increases) where the size of the clusters become infinite. In the systems described so far, it has been assumed that the occupation of a site or bond is completely random—this is the so-called Bernoulli percolation. For a continuum system, random occupancy corresponds to the points being placed by a Poisson process. Further variations involve correlated percolation, such as percolation clusters related to Ising and Potts models of ferromagnets, in which the bonds are put down by the Fortuin–Kasteleyn method. In bootstrap or k-sat percolation, sites and/or bonds are first occupied and then successively culled from a system if a site does not have at least k neighbors. Another important model of percolation, in a different universality class altogether, is directed percolation, where connectivity along a bond depends upon the direction of the flow. Another variation of recent interest is Explosive Percolation, whose thresholds are listed on that page. Over the last several decades, a tremendous amount of work has gone into finding exact and approximate values of the percolation thresholds for a variety of these systems. Exact thresholds are only known for certain two-dimensional lattices that can be broken up into a self-dual array, such that under a triangle-triangle transformation, the system remains the same. Studies using numerical methods have led to numerous improvements in algorithms and several theoretical discoveries. Simple duality in two dimensions implies that all fully triangulated lattices (e.g., the triangular, union jack, cross dual, martini dual and asanoha or 3-12 dual, and the Delaunay triangulation) all have site thresholds of 1⁄2, and self-dual lattices (square, martini-B) have bond thresholds of 1⁄2. The notation such as (4,82) comes from Grünbaum and Shephard, and indicates that around a given vertex, going in the clockwise direction, one encounters first a square and then two octagons. Besides the eleven Archimedean lattices composed of regular polygons with every site equivalent, many other more complicated lattices with sites of different classes have been studied. Error bars in the last digit or digits are shown by numbers in parentheses. Thus, 0.729724(3) signifies 0.729724 ± 0.000003, and 0.74042195(80) signifies 0.74042195 ± 0.00000080. The error bars variously represent one or two standard deviations in net error (including statistical and expected systematic error), or an empirical confidence interval, depending upon the source.

Percolation on networks For a random tree-like network (i.e., a connected network with no cycle) 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

… excerpt ends here. Continue reading the full article.