Achlioptas process

guillefix 4th November 2016 at 2:43pm

An Achlioptas process is a type of Explosive percolation, also known as mm-edge processes, that involve choosing mm candidate edges uniformly at random between any pair of nodes (compare with other Spanning cluster-avoiding process)and applying a rule to select which one is actually chosen. These have been proven to be continuous in the thermodynamic limit, for a fixed mm. They are generalizations of Erdos-Renyi Random graphs.

The first proposed type, were proposed (in Explosive Percolation in Random Networks) and thought to maybe show a discontinuous phase transition.

Achlioptas processes phase transitions are continuous

It has now been show that the Percolation phase transition for Achlioptas processes (and in fact a more general class of k-vertex rule percolation process) is continuous (in the thermodynamic limit), but very steep (see Explosive Percolation Transition is Actually Continuous and Achlioptas process phase transitions are continuous). One can prove the continuity by looking at the asymptotic effect of removing a single link, as the total size goes to infinity. However, Oliver Riordan and Lutz Warnke proved it by proving, in essence, that the number of subcritical components that join together to form the emergent macroscopic-sized component is not sub-extensive in system size. In the words of Friedman and Landsberg, Achlioptas Processes do not lead to the build-up of a “powder keg" (which is a type of cluster configuration that does lead to discontinuous transitions).

However, the model can be generalized to one that shows genuinely discontinuous transitions (see Anomalous critical and supercritical phenomena in explosive percolation). One way to achieve discontinuity is actually to allow the number of edges in the rule, mm to scale up with NN, the network size, in a certain way.

22-edge Achli Achlioptas process is the simplest type: Start with N isolated nodes and add undirected, unweighted edges one at a time. This is done by choosing, at each step, two possible edges uniformly (and independently) at random from the set of N(N1)/2N(N-1)/2 possible {edges between a pair of distinct nodes}. One adds only one of these edges, making a choice based on a systematic rule that affects the speed of development of a GCC.

mm-edge rules are defined similarly.

Selection rules

Product rule. One choice that yields "explosive" percolation is to use the so-called "product rule", in which one always retains the edge that minimizes the product of the sizes of the two components that it merges (with an arbitrary choice when there is a tie).

Sum rule. The size of the new component formed is minimized.

Bohman–Frieze (BF) rule. edge 1 is chosen if it joins two isolated vertices, and edge 2 otherwise.

A selection rule can be classified as a bounded-size or an unbounded-size rule. In a bounded-size selection rule, decisions depend only on the sizes of the components and, moreover, all sizes greater than some (rule-specific) constant KK are treated identically.

There are also the more general mm-edge rules based on chosing mm edges at each step, and selecting one (or potentially more).

See more rules here: Explosive percolation: Unusual transitions of a simple model

The Evolution of Random Graphs (product rule first suggested here).

Avoiding a giant component. Bounded-size rules are able to switch the percolation threshold.

Birth control for giants. The percolation transition is strongly conjectured to be continuous for all bounded-size rules

Product rule wins a competitive game

Hamiltonicity thresholds in Achlioptas processes