The percolation threshold is a mathematical concept in
percolation theory
In statistical physics and 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 ...
that describes the formation of long-range connectivity in
random
In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...
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
A porous medium or a porous material is a material containing pores (voids). The skeletal portion of the material is often called the "matrix" or "frame". The pores are typically filled with a fluid (liquid or gas). The skeletal material is usua ...
, but in the mathematics and physics worlds it generally refers to simplified
lattice models
In mathematical physics, a lattice model is a mathematical model of a physical system that is defined on a lattice, as opposed to a continuum, such as the continuum of space or spacetime. Lattice models originally occurred in the context of cond ...
of random systems or networks (
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
s), and the nature of the connectivity in them. The percolation threshold is the
critical value
Critical value may refer to:
*In differential topology, a critical value of a differentiable function between differentiable manifolds is the image (value of) Æ’(''x'') in ''N'' of a critical point ''x'' in ''M''.
*In statistical hypothesis ...
of the occupation probability ''p'', or more generally a critical surface for a group of parameters ''p''
1, ''p''
2, ..., such that infinite connectivity (''
percolation
Percolation (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials.
It is described by Darcy's law.
Broader applicatio ...
'') 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 ''p
c'', large clusters and long-range connectivity first appears, 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 ''p''
1, ''p''
2, 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 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 ''p
c''. For finite large systems, ''P(p
c)'' is a constant whose value depends upon the shape of the system; for the square system discussed above, ''P(p
c)='' 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, ''n
s(p
c) ~ s
−τ'', where τ is a dimension-dependent
percolation critical exponents
In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of ''universal'' critical exponents, which describe the fractal properties of the percolating medium at large scales and ...
. 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 Bernoulli can refer to:
People
*Bernoulli family of 17th and 18th century Swiss mathematicians:
** Daniel Bernoulli (1700–1782), developer of Bernoulli's principle
**Jacob Bernoulli (1654–1705), also known as Jacques, after whom Bernoulli numbe ...
percolation.'' For a continuum system, random occupancy corresponds to the points being placed by a
Poisson process
In probability, statistics and related fields, a Poisson point process is a type of random mathematical object that consists of points randomly located on a mathematical space with the essential feature that the points occur independently of one ...
. 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
In statistical mechanics, a universality class is a collection of mathematical models which share a single scale invariant limit under the process of renormalization group flow. While the models within a class may differ dramatically at finite s ...
altogether, is
directed percolation
In statistical physics, directed percolation (DP) refers to a class of models that mimic filtering of fluids through porous materials along a given direction, due to the effect of gravity. Varying the microscopic connectivity of the pores, these ...
, where connectivity along a bond depends upon the direction of the flow.
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 , and self-dual lattices (square, martini-B) have bond thresholds of .
The notation such as (4,8
2) 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
Network, networking and networked may refer to:
Science and technology
* Network theory, the study of graphs as a representation of relations between discrete objects
* Network science, an academic field that studies complex networks
Mathematics
...
without degree-degree correlation, it can be shown that such network can have a
giant component
In network theory, a giant component is a connected component of a given random graph that contains a finite fraction of the entire graph's vertices.
Giant component in Erdős–Rényi model
Giant components are a prominent feature of the ErdÅ ...
, 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 seri ...
corresponding to the
excess degree distribution,
is the average degree of the network and
is the second
moment
Moment or Moments may refer to:
* Present time
Music
* The Moments, American R&B vocal group Albums
* ''Moment'' (Dark Tranquillity album), 2020
* ''Moment'' (Speed album), 1998
* ''Moments'' (Darude album)
* ''Moments'' (Christine Guldbrand ...
of the
degree distribution
In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.
Definition
The degree o ...
. So, for example, for an
ER network, since the degree distribution is a
Poisson distribution
In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time or space if these events occur with a known co ...
, the threshold is at
.
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.
Percolation on 2D lattices
Thresholds on Archimedean lattices
![Archimedean-Lattice](https://upload.wikimedia.org/wikipedia/commons/9/9e/Archimedean-Lattice.png)
Note: sometimes "hexagonal" is used in place of honeycomb, although in some fields, a triangular lattice is also called a
hexagonal lattice
The hexagonal lattice or triangular lattice is one of the five two-dimensional Bravais lattice types. The symmetry category of the lattice is wallpaper group p6m. The primitive translation vectors of the hexagonal lattice form an angle of 120° ...
. ''z'' = bulk
coordination number
In chemistry, crystallography, and materials science, the coordination number, also called ligancy, of a central atom in a molecule or crystal is the number of atoms, molecules or ions bonded to it. The ion/molecule/atom surrounding the central i ...
.
2d lattices with extended and complex neighborhoods
In this section, sq-1,2,3 corresponds to square (NN+2NN+3NN),
etc. Equivalent to square-2N+3N+4N,
sq(1,2,3).
tri = triangular, hc = honeycomb.
Here NN = nearest neighbor, 2NN = second nearest neighbor (or next nearest neighbor), 3NN = third nearest neighbor (or next-next nearest neighbor), etc. These are also called 2N, 3N, 4N respectively in some papers.
*For overlapping or touching squares,
(site) given here is the net fraction of sites occupied
similar to the
in continuum percolation. The case of a 2×2 square is equivalent to percolation of a square lattice NN+2NN+3NN+4NN or sq-1,2,3,4 with threshold
with
.
The 3×3 square corresponds to sq-1,2,3,4,5,6,7,8 with ''z''=44 and
. The value of ''z'' for a ''k'' x ''k'' square is (2''k''+1)
2-5. For larger overlapping squares, see.
Overlapping shapes on 2D lattices
Site threshold is number of overlapping objects per lattice site. ''k'' is the length (net area). Overlapping squares are shown in the complex neighborhood section. Here z is the coordination number to k-mers of either orientation, with
.
The coverage is calculated from
by
Approximate formulas for thresholds of Archimedean lattices
Site-bond percolation in 2D
Site bond percolation. Here
is the site occupation probability and
is the bond occupation probability, and connectivity is made only if both the sites and bonds along a path are occupied. The criticality condition becomes a curve
= 0, and some specific critical pairs
are listed below.
Square lattice:
Honeycomb (hexagonal) lattice:
Kagome lattice:
* For values on different lattices, see "An investigation of site-bond percolation on many lattices".
Approximate formula for site-bond percolation on a honeycomb lattice
Archimedean duals (Laves lattices)
![Dual Archimedean](https://upload.wikimedia.org/wikipedia/commons/1/15/Dual_Archimedean.png)
Laves lattices are the duals to the Archimedean lattices. Drawings from.
See also
Uniform tilings
A uniform is a variety of clothing worn by members of an organization while participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency services, se ...
.
2-uniform lattices
Top 3 lattices: #13 #12 #36
Bottom 3 lattices: #34 #37 #11
Top 2 lattices: #35 #30
Bottom 2 lattices: #41 #42
Top 4 lattices: #22 #23 #21 #20
Bottom 3 lattices: #16 #17 #15
Top 2 lattices: #31 #32
Bottom lattice: #33
Inhomogeneous 2-uniform lattice
This figure shows something similar to the 2-uniform lattice #37, except the polygons are not all regular—there is a rectangle in the place of the two squares—and the size of the polygons is changed. This lattice is in the isoradial representation in which each polygon is inscribed in a circle of unit radius. The two squares in the 2-uniform lattice must now be represented as a single rectangle in order to satisfy the isoradial condition. The lattice is shown by black edges, and the dual lattice by red dashed lines. The green circles show the isoradial constraint on both the original and dual lattices. The yellow polygons highlight the three types of polygons on the lattice, and the pink polygons highlight the two types of polygons on the dual lattice. The lattice has vertex types ()(3
3,4
2) + ()(3,4,6,4), while the dual lattice has vertex types ()(4
6)+()(4
2,5
2)+()(5
3)+()(5
2,4). The critical point is where the longer bonds (on both the lattice and dual lattice) have occupation probability p = 2 sin (π/18) = 0.347296... which is the bond percolation threshold on a triangular lattice, and the shorter bonds have occupation probability 1 − 2 sin(π/18) = 0.652703..., which is the bond percolation on a hexagonal lattice. These results follow from the isoradial condition
but also follow from applying the star-triangle transformation to certain stars on the honeycomb lattice. Finally, it can be generalized to having three different probabilities in the three different directions, p
1, p
2 and ''p''
3 for the long bonds, and , , and for the short bonds, where ''p''
1, ''p''
2 and ''p''
3 satisfy the critical surface for the inhomogeneous triangular lattice.
Thresholds on 2D bow-tie and martini lattices
To the left, center, and right are: the martini lattice, the martini-A lattice, the martini-B lattice. Below: the martini covering/medial lattice, same as the 2×2, 1×1 subnet for kagome-type lattices (removed).
![Martini](https://upload.wikimedia.org/wikipedia/commons/1/10/Martini.png)
Some other examples of generalized bow-tie lattices (a-d) and the duals of the lattices (e-h):
Thresholds on 2D covering, medial, and matching lattices
Thresholds on 2D chimera non-planar lattices
Thresholds on subnet lattices
The 2 x 2, 3 x 3, and 4 x 4 subnet kagome lattices. The 2 × 2 subnet is also known as the "triangular kagome" lattice.
[
]
Thresholds of random sequentially adsorbed objects
(For more results and comparison to the jamming density, see
Random sequential adsorption Random sequential adsorption (RSA) refers to a process where particles are randomly introduced in a system, and if they do not overlap any previously adsorbed particle, they adsorb and remain fixed for the rest of the process. RSA can be carried out ...
)
The threshold gives the fraction of sites occupied by the objects when site percolation first takes place (not at full jamming). For longer k-mers see Ref.
[
]
Thresholds of full dimer coverings of two dimensional lattices
Here, we are dealing with networks that are obtained by covering a lattice with dimers, and then consider bond percolation on the remaining bonds. In discrete mathematics, this problem is known as the 'perfect matching' or the 'dimer covering' problem.
Thresholds of polymers (random walks) on a square lattice
System is composed of ordinary (non-avoiding) random walks of length l on the square lattice.
[
]
Thresholds of self-avoiding walks of length k added by random sequential adsorption
Thresholds on 2D inhomogeneous lattices
Thresholds for 2D continuum models
equals critical total area for disks, where N is the number of objects and L is the system size.
gives the number of disk centers within the circle of influence (radius 2 r).
is the critical disk radius.
for ellipses of semi-major and semi-minor axes of a and b, respectively. Aspect ratio
with
.
for rectangles of dimensions
and
. Aspect ratio
with
.
for power-law distributed disks with
,
.
equals critical area fraction.
equals number of objects of maximum length
per unit area.
For ellipses,
For void percolation,
is the critical void fraction.
For more ellipse values, see
For more rectangle values, see
Both ellipses and rectangles belong to the superellipses, with
. For more percolation values of superellipses, see.
For the monodisperse particle systems, the percolation thresholds of concave-shaped superdisks are obtained as seen in
For binary dispersions of disks, see
[
][
]
Thresholds on 2D random and quasi-lattices
*Theoretical estimate
Thresholds on 2D correlated systems
Assuming power-law correlations
Thresholds on slabs
''h'' is the thickness of the slab, ''h'' × ∞ × ∞. Boundary conditions (b.c.) refer to the top and bottom planes of the slab.
Thresholds on 3D lattices and 3D continuum space
Filling factor = fraction of space filled by touching spheres at every lattice site (for systems with uniform bond length only). Also called
Atomic Packing Factor In crystallography, atomic packing factor (APF), packing efficiency, or packing fraction is the fraction of volume in a crystal structure that is occupied by constituent particles. It is a dimensionless quantity and always less than unity. In atomi ...
.
Filling fraction (or Critical Filling Fraction) = filling factor * p
c(site).
NN = nearest neighbor, 2NN = next-nearest neighbor, 3NN = next-next-nearest neighbor, etc.
kxkxk cubes are cubes of occupied sites on a lattice, and are equivalent to extended-range percolation of a cube of length (2k+1), with edges and corners removed, with z = (2k+1)
3-12(2k-1)-9 (center site not counted in z).
Question: the bond thresholds for the hcp and fcc lattice
agree within the small statistical error. Are they identical,
and if not, how far apart are they? Which threshold is expected to be bigger? Similarly for the ice and diamond lattices. See
[
]
Overlapping shapes on 3D lattices
Site threshold is the number of overlapping objects per lattice site. The coverage φ
c is the net fraction of sites covered, and ''v'' is the volume (number of cubes). Overlapping cubes are given in the section on thresholds of 3D lattices. Here z is the coordination number to k-mers of either orientation, with
The coverage is calculated from
by
for sticks, and
for plaquettes.
Dimer percolation in 3D
Thresholds for 3D continuum models
All overlapping except for jammed spheres and polymer matrix.
is the total volume (for spheres), where N is the number of objects and L is the system size.
is the critical volume fraction, valid for overlapping randomly placed objects.
For disks and plates, these are effective volumes and volume fractions.
For void ("Swiss-Cheese" model),
is the critical void fraction.
For more results on void percolation around ellipsoids and elliptical plates, see.
For more ellipsoid percolation values see.
[
For spherocylinders, H/D is the ratio of the height to the diameter of the cylinder, which is then capped by hemispheres. Additional values are given in.][
For superballs, m is the deformation parameter, the percolation values are given in., In addition, the thresholds of concave-shaped superballs are also determined in ]
For cuboid-like particles (superellipsoids), m is the deformation parameter, more percolation values are given in.
Void percolation in 3D
Void percolation refers to percolation in the space around overlapping objects. Here refers to the fraction of the space occupied by the voids (not of the particles) at the critical point, and is related to by
. is defined as in the continuum percolation section above.
Thresholds on 3D random and quasi-lattices
Thresholds for other 3D models
In drilling percolation, the site threshold represents the fraction of columns in each direction that have not been removed, and . For the 1d drilling, we have (columns) (sites).
†In tube percolation, the bond threshold represents the value of the parameter such that the probability of putting a bond between neighboring vertical tube segments is , where is the overlap height of two adjacent tube segments.
Thresholds in different dimensional spaces
Continuum models in higher dimensions
In 4d, .
In 5d, .
In 6d, .
is the critical volume fraction, valid for overlapping objects.
For void models, is the critical void fraction, and is the total volume of the overlapping objects
Thresholds on hypercubic lattices
For thresholds on high dimensional hypercubic lattices, we have the asymptotic series expansions
where .
Thresholds in other higher-dimensional lattices
Thresholds in one-dimensional long-range percolation
In a one-dimensional chain we establish bonds between distinct sites and with probability decaying as a power-law with an exponent . Percolation occurs at a critical value for . The numerically determined percolation thresholds are given by:
Thresholds on hyperbolic, hierarchical, and tree lattices
In these lattices there may be two percolation thresholds: the lower threshold is the probability above which infinite clusters appear, and the upper is the probability above which there is a unique infinite cluster.
Note: is the Schläfli symbol, signifying a hyperbolic lattice in which n regular m-gons meet at every vertex
For bond percolation on , we have by duality . For site percolation, because of the self-matching of triangulated lattices.
Cayley tree (Bethe lattice) with coordination number
Thresholds for directed percolation
nn = nearest neighbors. For a (''d'' + 1)-dimensional hypercubic system, the hypercube is in d dimensions and the time direction points to the 2D nearest neighbors.
Exact critical manifolds of inhomogeneous systems
Inhomogeneous triangular lattice bond percolation
Inhomogeneous honeycomb lattice bond percolation = kagome lattice site percolation
Inhomogeneous (3,12^2) lattice, site percolation[
]
or
Inhomogeneous union-jack lattice, site percolation with probabilities [
]
Inhomogeneous martini lattice, bond percolation[
Inhomogeneous martini lattice, site percolation. ''r'' = site in the star
Inhomogeneous martini-A (3–7) lattice, bond percolation. Left side (top of "A" to bottom): . Right side: . Cross bond: .
Inhomogeneous martini-B (3–5) lattice, bond percolation
Inhomogeneous martini lattice with outside enclosing triangle of bonds, probabilities from inside to outside, bond percolation][
]
Inhomogeneous checkerboard lattice, bond percolation[
]
Inhomogeneous bow-tie lattice, bond percolation
where are the four bonds around the square and is the diagonal bond connecting the vertex between bonds and .
See also
* 2D percolation cluster
* Bootstrap percolation In statistical mechanics, bootstrap percolation is a percolation process in which a random initial configuration of active cells is selected from a lattice or other space, and then cells with few active neighbors are successively removed from the a ...
* Directed percolation
In statistical physics, directed percolation (DP) refers to a class of models that mimic filtering of fluids through porous materials along a given direction, due to the effect of gravity. Varying the microscopic connectivity of the pores, these ...
* Effective medium approximations
In materials science, effective medium approximations (EMA) or effective medium theory (EMT) pertain to analytical or theoretical modeling that describes the macroscopic properties of composite materials. EMAs or EMTs are developed from averagin ...
* Epidemic models on lattices
Classic epidemic models of disease transmission are described in Compartmental models in epidemiology. Here we discuss the behavior when such models are simulated on a lattice.
Introduction
The mathematical modelling of epidemics was originally ...
* Graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
* Network science
Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors repre ...
* Percolation
Percolation (from Latin ''percolare'', "to filter" or "trickle through"), in physics, chemistry and materials science, refers to the movement and filtering of fluids through porous materials.
It is described by Darcy's law.
Broader applicatio ...
* Percolation critical exponents
In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of ''universal'' critical exponents, which describe the fractal properties of the percolating medium at large scales and ...
* Percolation theory
In statistical physics and 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 ...
* Random sequential adsorption Random sequential adsorption (RSA) refers to a process where particles are randomly introduced in a system, and if they do not overlap any previously adsorbed particle, they adsorb and remain fixed for the rest of the process. RSA can be carried out ...
* Uniform tilings
A uniform is a variety of clothing worn by members of an organization while participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency services, se ...
References
{{DEFAULTSORT:Percolation Threshold
Percolation theory
Critical phenomena
Random graphs