Explosive percolation

Explosive percolation refers to the emergence of large-scale connectivity in a random network that grows under a rule designed to delay that connectivity. The emergence of a large macroscopic connected component is a commonly known phase transition in percolation theory and is also known as the formation of a giant component. In 2009, the work by Dimitris Achlioptas, Raissa D'Souza, and Joel Spencer proposed a variant of the Erdős–Rényi model (ER) known as the 'product rule'. In this work they introduce a small selection bias: sample two edges, for each candidate edge, take the product (a sum variant also exists) of the sizes of the two clusters that the edge would have joined, and then choose the edge with a smaller product. As a consequence of this selection bias, smaller clusters are favoured, causing the formation of the giant component to be delayed. The standard percolation result shows that the giant component forms when the number of links is roughly ${\displaystyle 0.5n}$ whereas the product rule delayed this transition to ${\displaystyle 0.888n}$. ${\displaystyle n}$ here refers to the number of nodes in the network.

A more surprising aspect of this transition apart from delaying the formation of giant components is the fact that once this transition occurs, it is extremely abrupt – a phenomenon they termed explosive percolation. The authors measured the number of time steps from the point when the size of the largest cluster is just smaller than ${\displaystyle {\sqrt {n}}}$ until the stage where the large cluster is of the size ${\displaystyle n/2}$. They measured how this ${\displaystyle \Delta t}$ scales with ${\displaystyle n}$ and found that while the ER model scales linearly (${\displaystyle \Delta t\sim n^{1}}$), the product rule transition scales sublinearly (${\displaystyle \Delta t\sim n^{2/3}}$). As the system size increases, the window relative to the system size (${\displaystyle \Delta t/n}$) shrinks to zero, showing an abrupt jump in connectivity.

Achlioptas processes

In the year 2000, at a Fields Institute workshop, Achlioptas introduced various rules modifying the standard percolation thresholds and delay it based on 'power of two choices' (see also: Balls into bins problem). Start with ${\displaystyle n}$ isolated nodes. Instead of adding a single random edge, ${\displaystyle m\geq 2}$ candidate edges ${\displaystyle \{e_{1},e_{2}..e_{m}\}}$ are sampled at each time step and a pre-set selection criterion is applied. The edge that satisfies the set of criteria is chosen for a given timestep and the other edges are discarded. Such m-edge graph evolution algorithms are referred to as Achlioptas processes. Some examples of rules can be listed as follows:

Sum rule (SR)

A variant of the product rule in which the candidate edge connecting the smaller sum of component sizes is chosen.

Mechanism

Since the product rule delays the merger of large components, by the time a giant component is formed, the network already contains isolated structures of intermediate sizes. This means that even a single edge coalesces two large components. Since intermediate sized portions are already formed, the process to get to a giant component is rapid. Eric Friedman and Adam Landsberg equate this idea to a "powder keg" and argued that these "kegs" once formed "guarantees an eventual explosive transition in the network".

Order of phase transition

Classical percolation shows a continuous phase transition. Initially, in contrast to this result, Achlioptas, D'Souza and Spencer claimed that the product rule leads to a first-order or discontinuous phase transition. This result led to widespread debate and discussion among mathematicians and physicists and led to many follow-up studies. By 2011, many groups argued that the phase transition is indeed not first order, but continuous in the limit of infinite system size. The ${\displaystyle \Delta t\sim n^{2/3}}$ result claimed earlier was shown to be a finite-size effect that did not hold in the large-${\displaystyle n}$ limit. This did not, however, change the fact that the transition is still unexpectedly steep.

R.A. da Costa, S. N. Dorogovtsev, A. V. Goltsev and J. F. F. Mendes published a paper titled "'Explosive Percolation' Transition is Actually Continuous" where they studied a system close to the product rule where: two pairs of vertices are chosen, the vertex belonging to the smaller cluster is chosen from each pair, and these two are joined by an edge. The group argued that this rule delays the formation of a giant component much later than what the product rule had. Hence, the continuity of this transition also implies the transition for the product rule should be continuous. The authors found that the maximum change in the relative size of the largest component from the addition of a single edge decays as a power law with system size, ${\displaystyle \Delta C\sim n^{-1/18}}$. They also suggested that the small scaling exponent makes it "virtually impossible to distinguish this phase transition from a discontinuous one even in very large systems".

Eventually, Oliver Riordan and Lutz Warnke provided a mathematical proof and showed analytically that every Achlioptas process with a fixed number of random choices has a continuous transition.

While Achlioptas processes may not show discontinuous transitions, there are variants that were created later that show truly discontinuous percolation transitions. Some instances of these include:

• Growing number of choices: a two-choice-style rule where the number of candidates grows with the size of the network.
• Araújo–Herrmann: edges that would grow the largest cluster are rejected more often, so clusters grow at a similar pace.
• Spanning-cluster avoidance: on a lattice, choose among the candidate bonds so as to avoid creating a cluster that spans the whole grid.

Applications

The mechanism for explosive percolation has found applications across various disciplines including epidemiology, power grids, and protein homology. According to Raissa D'Souza, “For normal operating systems [like the Internet, airline networks or the stock exchange], we want them to be heavily connected,” she said. “But when we think about epidemics spreading, we want to curtail the extent of the connectivity.”

Rozenfeld, Gallos and Makse proposed that giant clusters in human protein homology form explosively with slow growth and separation until small added links suddenly merge them. The process for protein homology deviates from standard percolation.

Pan and colleagues in 2011 also tried fitting explosive percolation models on large social networks. They managed to show that for a few kinds of networks there do exist forms of explosive percolation.

References