Unstable supercritical discontinuous percolation transitions

The location and nature of the percolation transition in random networks is a subject of intense interest. Recently, a series of graph evolution processes have been introduced that lead to discontinuous percolation transitions where the addition of a single edge causes the size of the largest component to exhibit a significant macroscopic jump in the thermodynamic limit. These processes can have additional exotic behaviors, such as displaying a “Devil's staircase” of discrete jumps in the supercritical regime. Here we investigate whether the location of the largest jump coincides with the percolation threshold for a range of processes, such as Erdős-Rényipercolation, percolation via edge competition and via growth by overtaking. We find that the largest jump asymptotically occurs at the percolation transition for Erdős-Rényiand other processes exhibiting global continuity, including models exhibiting an “explosive” transition. However, for percolation processes exhibiting genuine discontinuities, the behavior is substantially richer. In percolation models where the order parameter exhibits a staircase, the largest discontinuity generically does not coincide with the percolation transition. For the generalized Bohman-Frieze-Wormald model, it depends on the model parameter. Distinct parameter regimes well in the supercritical regime feature unstable discontinuous transitions—a novel and unexpected phenomenon in percolation. We thus demonstrate that seemingly and genuinely discontinuous percolation transitions can involve a rich behavior in supercriticality, a regime that has been largely ignored in percolation.

Figure 1

Continuous percolation models. (a) A typical evolution of $C_1$ as a function of the link density $p=t/N$ for ER, and for the ${\text{PR}}_{\text{max}}$, ${\text{PR}}_{\text{min}}$ models with the number of candidate edges $c=2$ and $c=4$, respectively. The system size $N={10}^6$. (b) $(t_{\Delta }-t_c)/N$ versus number of nodes $N$ for these models, all of which follow a power-law distribution. Each data point in (b) is averaged over 1000 realizations.

Figure 2

Unstable supercritical discontinuous transitions. Typical evolutions of $C_1$ and $C_2$ versus the link density for the DS model (a), NG model (b), and mER model (c) with system size $N={10}^6$. The link density $p_1$ at which the largest jump in $C_1$ occurs, the link density $p_2$ when the second largest jump in $C_1$ occurs, and $p_1-p_2$ versus system size $N$ for the DS model (d), NG model (e), and mER model (f). Each data point in (d), (e), and (f) is averaged over 100 realizations.

Figure 3

Critical and unstable supercritical discontinuous transitions. (a) For $\alpha =0.600$, one giant component emerges in a phase transition. (b) For $\alpha =0.530$, $C_1,C_2$ versus the link density, showing that two giant components emerge simultaneously in the first phase transition. They are, however, unstable as they merge at a second transition. (c) For $\alpha =0.500$, $C_1,C_2,C_3$ versus the link density, showing that two giant components emerge simultaneously. (d) For $\alpha =0.350$, $C_1,C_2,C_3$ versus the link density, showing that three giant components emerge simultaneously in the first phase transition. This configuration is unstable as in a second transition the second-largest and the third-largest components merge. (e) For $\alpha =0.300$, $C_1,C_2,C_3,C_4$ versus link density, showing the simultaneous emergence of three giant components. (f) For $\alpha =0.260$, $C_1,C_2,C_3,C_4$ versus density of links, showing that four giant components emerge simultaneously in the first phase transition. Two smallest macroscopic components $C_3$ and $C_4$ merge together and overtake $C_1$, the other macroscopic components are stable in the remaining process, $C_3+C_4\to C_1$, $C_1\to C_2,C_2\to C_3$. System size is $N={10}^6$ for all simulations.

Figure 4

Scaling of critical and unstable supercritical discontinuous transitions. (a) For $\alpha =0.600$, $C_1$ at $p_1$, $p_1-p_3$ versus system size. (b) For $\alpha =0.530$, $C_1$ at $p_2$, the largest jump in $C_1$, $p_2-p_3$, $p_1-p_2$ versus system size. (c) For $\alpha =0.500$, $C_1,C_2$ at $p_1$, $p_1-p_3$ versus system size. (d) For $\alpha =0.350$, $C_1,C_2$ at $p_2$, the largest jump in $C_1,C_2$, $p_2-p_3$, $p_1-p_2$ versus system size. (e) For $\alpha =0.300$, $C_1,C_2,C_3$ at $p_1$, $p_1-p_3$ versus system size. (f) For $\alpha =0.260$, $C_1,C_2,C_3$ at $p_2$, the largest jump in $C_1,C_2,C_3$, $p_2-p_3$, $p_1-p_2$ versus system size. Each data point is averaged over 1000 realizations.

Figure 5

Phase diagram for the BFW model. The number of giant components that appear in the first discontinuous phase transition (percolation transition point) in dependence on $\alpha$. In the stable region, the giant components remain distinct in the supercritical regime while in the unstable region the two smallest giant components merge in the supercritical regime at a well-defined transition point.