Bootstrap percolation

Last updated

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 active set until the system stabilizes. The order in which this removal occurs makes no difference to the final stable state. [1] [2]

When the threshold of active neighbors needed for an active cell to survive is high enough (depending on the lattice), the only stable states are states with no active cells, or states in which every cluster of active cells is infinitely large. For instance, on the square lattice with the von Neumann neighborhood, there are finite clusters with at least two active neighbors per cluster cell, but when three or four active neighbors are required, any stable cluster must be infinite. [1] With three active neighbors needed to stay active, an infinite cluster must stretch infinitely in three or four of the possible cardinal directions, and any finite holes it contains will necessarily be rectangular. In this case, the critical probability is 1, meaning that when the probability of each cell being active in the initial state is anything less than 1, then almost surely there is no infinite cluster. [3] If the initial state is active everywhere except for an n × n square, within which one cell in each row and column is inactive, then these single-cell voids will merge to form a void that covers the whole square if and only if the inactive cells have the pattern of a separable permutation. [4] In any higher dimension, for any threshold, there is an analogous critical probability below which all cells almost surely become inactive and above which some clusters almost surely survive. [5]

Bootstrap percolation can be interpreted as a cellular automaton, resembling Conway's Game of Life, in which live cells die when they have too few live neighbors. However, unlike Conway's Life, cells that have become dead never become alive again. [6] [7] It can also be viewed as an epidemic model in which inactive cells are considered as infected and active cells with too many infected neighbors become infected themselves. [5] The smallest threshold that allows some cells of an initial cluster to survive is called the degeneracy of its adjacency graph, and the remnant of a cluster that survives with threshold k is called the k-core of this graph. [8]

One application of bootstrap percolation arises in the study of fault tolerance for distributed computing. If some processors in a large grid of processors fail (become inactive), then it may also be necessary to inactivate other processors with too few active neighbors, in order to preserve the high connectivity of the remaining network. The analysis of bootstrap percolation can be used to determine the failure probability that can be tolerated by the system. [9]

Related Research Articles

<span class="mw-page-title-main">Percolation theory</span> Mathematical theory on behavior of connected clusters in a random graph

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 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 and percolation.

The Ising 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 magnetic dipole moments of atomic "spins" that can be in one of two states. The spins are arranged in a graph, usually a lattice, allowing each spin to interact with its neighbors. Neighboring spins that agree have a lower energy than those that disagree; the system tends to the lowest energy but heat disturbs this tendency, thus creating the possibility of different structural phases. The model allows the identification of phase transitions as a simplified model of reality. The two-dimensional square-lattice Ising model is one of the simplest statistical models to show a phase transition.

<span class="mw-page-title-main">Random graph</span> Graph generated by a random process

In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs. Its practical applications are found in all areas in which complex networks need to be modeled – many random graph models are thus known, mirroring the diverse types of complex networks encountered in different areas. In a mathematical context, random graph refers almost exclusively to the Erdős–Rényi random graph model. In other contexts, any graph model may be referred to as a random graph.

<span class="mw-page-title-main">Complex network</span> Network with non-trivial topological features

In the context of network theory, a complex network is a graph (network) with non-trivial topological features—features that do not occur in simple networks such as lattices or random graphs but often occur in networks representing real systems. The study of complex networks is a young and active area of scientific research inspired largely by empirical findings of real-world networks such as computer networks, biological networks, technological networks, brain networks, climate networks and social networks.

Critical exponents describe the behavior of physical quantities near continuous phase transitions. It is believed, though not proven, that they are universal, i.e. they do not depend on the details of the physical system, but only on some of its general features. For instance, for ferromagnetic systems, the critical exponents depend only on:

<span class="mw-page-title-main">Contact process (mathematics)</span>

The contact process is a stochastic process used to model population growth on the set of sites of a graph in which occupied sites become vacant at a constant rate, while vacant sites become occupied at a rate proportional to the number of occupied neighboring sites. Therefore, if we denote by the proportionality constant, each site remains occupied for a random time period which is exponentially distributed parameter 1 and places descendants at every vacant neighboring site at times of events of a Poisson process parameter during this period. All processes are independent of one another and of the random period of time sites remains occupied. The contact process can also be interpreted as a model for the spread of an infection by thinking of particles as a bacterium spreading over individuals that are positioned at the sites of , occupied sites correspond to infected individuals, whereas vacant correspond to healthy ones.

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 models display a phase transition from a macroscopically permeable (percolating) to an impermeable (non-percolating) state. Directed percolation is also used as a simple model for epidemic spreading with a transition between survival and extinction of the disease depending on the infection rate.

<span class="mw-page-title-main">Gabriel graph</span>

In mathematics and computational geometry, the Gabriel graph of a set of points in the Euclidean plane expresses one notion of proximity or nearness of those points. Formally, it is the graph with vertex set in which any two distinct points and are adjacent precisely when the closed disc having as a diameter contains no other points. Another way of expressing the same adjacency criterion is that and should be the two closest given points to their midpoint, with no other given point being as close. Gabriel graphs naturally generalize to higher dimensions, with the empty disks replaced by empty closed balls. Gabriel graphs are named after K. Ruben Gabriel, who introduced them in a paper with Robert R. Sokal in 1969.

<span class="mw-page-title-main">Oded Schramm</span> Israeli mathematician

Oded Schramm 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 and probability theory.

<span class="mw-page-title-main">Erdős–Rényi model</span> Two closely related models for generating random graphs

In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs or the evolution of a random network. They are named after Hungarian mathematicians Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959, while Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, also called the Erdős–Rényi–Gilbert model, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

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.

The clique percolation method is a popular approach for analyzing the overlapping community structure of networks. The term network community has no widely accepted unique definition and it is usually defined as a group of nodes that are more densely connected to each other than to other nodes in the network. There are numerous alternative methods for detecting communities in networks, for example, the Girvan–Newman algorithm, hierarchical clustering and modularity maximization.

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 sufficiently close to the transition. The exponents are universal in the sense that they only depend on the type of percolation model and on the space dimension. They are expected to not depend on microscopic details such as the lattice structure, or whether site or bond percolation is considered. This article deals with the critical exponents of random percolation.

<span class="mw-page-title-main">Epidemic models on lattices</span>

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.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

Conductivity near the percolation threshold in physics, occurs in a mixture between a dielectric and a metallic component. The conductivity and the dielectric constant of this mixture show a critical behavior if the fraction of the metallic component reaches the percolation threshold.

In mathematics and probability theory, continuum percolation theory is a branch of mathematics that extends discrete percolation theory to continuous space. More specifically, the underlying points of discrete percolation form types of lattices whereas the underlying points of continuum percolation are often randomly positioned in some continuous space and form a type of point process. For each point, a random shape is frequently placed on it and the shapes overlap each with other to form clumps or components. As in discrete percolation, a common research focus of continuum percolation is studying the conditions of occurrence for infinite or giant components. Other shared concepts and analysis techniques exist in these two types of percolation theory as well as the study of random graphs and random geometric graphs.

<span class="mw-page-title-main">Global cascades model</span>

Global cascades models are a class of models aiming to model large and rare cascades that are triggered by exogenous perturbations which are relatively small compared with the size of the system. The phenomenon occurs ubiquitously in various systems, like information cascades in social systems, stock market crashes in economic systems, and cascading failure in physics infrastructure networks. The models capture some essential properties of such phenomenon.

Physicists often use various lattices to apply their favorite models in them. For instance, the most favorite lattice is perhaps the square lattice. There are 14 Bravais space lattice where every cell has exactly the same number of nearest, next nearest, nearest of next nearest etc. neighbors and hence they are called regular lattice. Often physicists and mathematicians study phenomena which require disordered lattice where each cell do not have exactly the same number of neighbors rather the number of neighbors can vary wildly. For instance, if one wants to study the spread of disease, viruses, rumors etc. then the last thing one would look for is the square lattice. In such cases a disordered lattice is necessary. One way of constructing a disordered lattice is by doing the following.

In statistical mechanics, probability theory, graph theory, etc. the random cluster model is a random graph that generalizes and unifies the Ising model, Potts model, and percolation model. It is used to study random combinatorial structures, electrical networks, etc. It is also referred to as the RC model or sometimes the FK representation after its founders Kees Fortuin and Piet Kasteleyn.

References

  1. 1 2 Chalupa, J.; Leath, P. L.; Reich, G. R. (1979), "Bootstrap percolation on a Bethe lattice", Journal of Physics C: Solid State Physics , 12 (1): L31–L35, Bibcode:1979JPhC...12L..31C, doi:10.1088/0022-3719/12/1/008 .
  2. ↑ Adler, Joan (1991), "Bootstrap percolation", Physica A: Statistical Mechanics and its Applications , 171 (3): 453–470, Bibcode:1991PhyA..171..453A, doi:10.1016/0378-4371(91)90295-n .
  3. ↑ van Enter, Aernout C. D. (1987), "Proof of Straley's argument for bootstrap percolation", Journal of Statistical Physics , 48 (3–4): 943–945, Bibcode:1987JSP....48..943V, doi:10.1007/BF01019705, MR   0914911, S2CID   119825786 .
  4. ↑ Shapiro, Louis; Stephens, Arthur B. (1991), "Bootstrap percolation, the Schröder numbers, and the N-kings problem", SIAM Journal on Discrete Mathematics , 4 (2): 275–280, doi:10.1137/0404025, MR   1093199 .
  5. 1 2 Balogh, József; Bollobás, Béla; Duminil-Copin, Hugo; Morris, Robert (2012), "The sharp threshold for bootstrap percolation in all dimensions", Transactions of the American Mathematical Society , 364 (5): 2667–2701, arXiv: 1010.3326 , doi:10.1090/S0002-9947-2011-05552-2, MR   2888224, S2CID   2708046 .
  6. ↑ Aizenman, M.; Lebowitz, J. L. (1988), "Metastability effects in bootstrap percolation", Journal of Physics A: Mathematical and General , 21 (19): 3801–3813, Bibcode:1988JPhA...21.3801A, doi:10.1088/0305-4470/21/19/017 .
  7. ↑ Schonmann, Roberto H. (1992), "On the behavior of some cellular automata related to bootstrap percolation", Annals of Probability , 20 (1): 174–193, doi: 10.1214/aop/1176989923 , JSTOR   2244552, MR   1143417 .
  8. ↑ Gottschau, Marinus (2016), Bootstrap percolation on degenerate graphs, arXiv: 1605.07002 , Bibcode:2016arXiv160507002G .
  9. ↑ Kirkpatrick, Scott; Wilcke, Winfried W.; Garner, Robert B.; Huels, Harald (2002), "Percolation in dense storage arrays", Physica A: Statistical Mechanics and its Applications , 314 (1–4): 220–229, Bibcode:2002PhyA..314..220K, doi:10.1016/S0378-4371(02)01153-6, MR   1961703 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.