Achlioptas Processes

Achlioptas Processes is about incorporating a limited amount of choice in the classic Erdös-Rényi network formation model, that causes its percolation transition to becoming discontinuous.

Networks in which the formation of connections is governed by a random process often undergo a percolation transition, wherein around a critical point, the addition of a small number of connections causes a sizable fraction of the network to suddenly become linked together.

Typically such transitions are continuous so that the percentage of the network linked together tends to zero right above the transition point.

Whether percolation transitions could be discontinuous has been an open question.

The paper in question is Explosive Percolation in Random Networks by Dimitris Achlioptas, R.M. D’Souza, and J. Spencer.

What is an Achlioptas Process

TL;DR: An Achlioptas process is a generalization of a common procedure of forming an Erdös-Rényi (ER) random graph that:

  1. Adds a rule for choosing amongst a set of candidate links to add to the network and
  2. thereby may allow for percolation transitions that differ in character from the transition in the ER model.

How do Achlioptas processes work?

Suppose we begin with a graph of 𝑁N isolated nodes and then incrementally build a network from there.

In one common procedure for generating an Erdös-Rényi (ER) random graph, we choose two nodes at random and add a link between them.

To get an ER random graph where the mean degree is 2𝑟2r, we simply repeat this procedure until we’ve added 𝑟𝑁rN links to our network. 

In an Achlioptas process, we instead randomly choose 𝑘k pairs of nodes.

The most common and simplest choice is 𝑘=2k=2.

With two randomly chosen links in hand, we then use some rule to decide between them.

If we make this decision randomly, we would again recover an ER random graph.

However, we can also consider a variety of non-random selection rules.

Many of these are formulated in terms of the component sizes connected by each proposed link.

For example, we can choose to:

  • minimize the sum of the component sizes connected by the links (a.k.a. a sum rule).
  • minimize the product of the component sizes connected by the links (a.k.a. a product rule).
  • choose the first randomly selected pair if it connects two components of size 𝐾K or smaller, otherwise, choose the second randomly selected pair (a.k.a. a bounded-size rule).

Percolation in Achlioptas processes

In the ER random graph procedure, 𝑟=12r=12 is a special point, corresponding to a percolation phase transition.

For 𝑟<12r<12, the largest connected component of the network includes a vanishingly small fraction of the total number of nodes as 𝑁→∞N→∞; in particular, the size of the largest component scales logarithmically with 𝑁N.

Exactly at 𝑟=12r=12, the size of the largest component scales like 𝑁23N23.

For 𝑟>12r>12, the largest component becomes macroscopically large, occupying a finite fraction of nodes as 𝑁→∞N→∞.

Specifically, the fraction varies like 4𝛿4δ for 𝑟=12+𝛿r=12+δ and small 𝛿δ.

There is no discontinuous jump of the fraction at the transition, so the percolation transition is “second order” in traditional statistical physics nomenclature.

Researchers have looked to Achlioptas processes to determine whether introducing choice (i.e., the selection rule) can fundamentally change the character of the percolation transition.

Before the work of Achliotpas et al., there was apparently already evidence that bounded-size rules always give rise to continuous, second-order transitions, as in the ER model.

However, in 2009, Achlioptas et al. reported numerical evidence that the product rule results in a first-order phase transition, with an apparently discontinuous jump of the fraction of nodes in the giant component.

This is “explosive percolation” that they refer to in their title.

Here’s a figure from the paper which compares component fraction 𝐶𝑁CN in ER network generation to Achlioptas processes with a bounded-size rule with K=1 (labeled BF) and with the product rule (labeled PR):

Achlioptas Process: component fraction compare in ER network

It’s worth noting that both the bounded-size rule and product rule attempt to suppress the formation of large components, so it’s unsurprising that the transitions in these models are shifted to 𝑟>12r>12.

The more interesting question is whether there’s a true discontinuity in the 𝑁→∞N→∞ limit.

In 2011, Riordan and Warnke published proof that the transition in the process considered by Achlioptas et al. actually must be continuous in 𝑁→∞N→∞ limit.

The numerical results above are, therefore, misleading due to finite-size effects.

Very recently, Waagen and D’Souza have put out a preprint identifying a process that recovers discontinuity by allowing the size of the candidate set of randomly chosen links to grow with system size.