Suppression effect on explosive percolation

Explosive Percolation Obeys Standard Finite-Size Scaling in an Event-Based Ensemble

Explosive percolation in the Achlioptas process, which has attracted much research attention, is known to exhibit a rich variety of critical phenomena that are anomalous from the perspective of continuous phase transitions. Hereby, we show that, in an event-based ensemble, the critical behaviors in explosive percolation are rather clean and obey the standard finite-size scaling theory, except for the large fluctuation of pseudo-critical points. In the fluctuation window, multiple fractal structures emerge and the values can be derived from a crossover scaling theory. Further, their mixing effects account well for the previously observed anomalous phenomena. Making use of the clean scaling in the event-based ensemble, we determine with a high precision the critical points and exponents for a number of bond-insertion rules and clarify ambiguities about their universalities. Our findings hold true for any spatial dimensions.

Scaling behavior of information entropy in explosive percolation transitions

An explosive percolation transition is the abrupt emergence of a giant cluster at a threshold caused by a suppression of the growth of large clusters. In this paper, we consider the information entropy of the cluster-size distribution, which is the probability distribution for the size of a randomly chosen cluster. It has been reported that information entropy does not reach its maximum at the threshold in explosive percolation models, a result seemingly contrary to other previous results that the cluster-size distribution shows power-law behavior and the cluster-size diversity (number of distinct cluster sizes) is maximum at the threshold. Here, we show that this phenomenon is due to the fact that the scaling form of the cluster-size distribution is given differently below and above the threshold. We also establish the scaling behaviors of the first and second derivatives of the information entropy near the threshold to explain why the first derivative has a negative minimum at the threshold and the second derivative diverges negatively (positively) at the left (right) limit of the threshold, as predicted through previous simulation.

A hybrid percolation transition at a finite transition point in scale-free networks

Percolation transition (PT) means the formation of a macroscopic-scale large cluster, which exhibits a continuous transition. However, when the growth of large clusters is globally suppressed, the type of PT is changed to a discontinuous transition for random networks. A question arises as to whether the type of PT is also changed for scale-free (SF) network, because the existence of hubs incites the formation of a giant cluster. Here, we apply a global suppression rule to the static model for SF networks and investigate properties of the PT. We find that even for SF networks with the degree exponent 2<λ<3, a hybrid PT occurs at a finite transition point t_c, which we can control by the suppression strength. The order parameter jumps at t_c ^- and exhibits a critical behavior at t_c ⁺.

Explosive synchronization as a process of explosive percolation in dynamical phase space

Explosive synchronization and explosive percolation are currently two independent phenomena occurring in complex networks, where the former takes place in dynamical phase space while the latter in configuration space. It has been revealed that the mechanism of EP can be explained by the Achlioptas process, where the formation of a giant component is controlled by a suppressive rule. We here introduce an equivalent suppressive rule for ES. Before the critical point of ES, the suppressive rule induces the presence of multiple, small sized, synchronized clusters, while inducing the abrupt formation of a giant cluster of synchronized oscillators at the critical coupling strength. We also show how the explosive character of ES degrades into a second-order phase transition when the suppressive rule is broken. These results suggest that our suppressive rule can be considered as a dynamical counterpart of the Achlioptas process, indicating that ES and EP can be unified into a same framework.

Crossover behavior of conductivity in a discontinuous percolation model

When conducting bonds are occupied randomly in a two-dimensional square lattice, the conductivity of the system increases continuously as the density of those conducting bonds exceeds the percolation threshold. Such a behavior is well known in percolation theory; however, the conductivity behavior has not been studied yet when the percolation transition is discontinuous. Here we investigate the conductivity behavior through a discontinuous percolation model evolving under a suppressive external bias. Using effective medium theory, we analytically calculate the conductivity behavior as a function of the density of conducting bonds. The conductivity function exhibits a crossover behavior from a drastically to a smoothly increasing function beyond the percolation threshold in the thermodynamic limit. The analytic expression fits well our simulation data.

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.

Growth dominates choice in network percolation

The onset of large-scale connectivity in a network (i.e., percolation) often has a major impact on the function of the system. Traditionally, graph percolation is analyzed by adding edges to a fixed set of initially isolated nodes. Several years ago, it was shown that adding nodes as well as edges to the graph can yield an infinite order transition, which is much smoother than the traditional second-order transition. More recently, it was shown that adding edges via a competitive process to a fixed set of initially isolated nodes can lead to a delayed, extremely abrupt percolation transition with a significant jump in large but finite systems. Here we analyze a process that combines both node arrival and edge competition. If started from a small collection of seed nodes, we show that the impact of node arrival dominates: although we can significantly delay percolation, the transition is of infinite order. Thus, node arrival can mitigate the trade-off between delay and abruptness that is characteristic of explosive percolation transitions. This realization may inspire new design rules where network growth can temper the effects of delay, creating opportunities for network intervention and control.

Phase transitions in supercritical explosive percolation

Percolation describes the sudden emergence of large-scale connectivity as edges are added to a lattice or random network. In the Bohman-Frieze-Wormald model (BFW) of percolation, edges sampled from a random graph are considered individually and either added to the graph or rejected provided that the fraction of accepted edges is never smaller than a decreasing function with asymptotic value of α, a constant. The BFW process has been studied as a model system for investigating the underlying mechanisms leading to discontinuous phase transitions in percolation. Here we focus on the regime αε[0.6,0.95] where it is known that only one giant component, denoted C(1) , initially appears at the discontinuous phase transition. We show that at some point in the supercritical regime C(1) stops growing and eventually a second giant component, denoted C(2), emerges in a continuous percolation transition. The delay between the emergence of C(1) and C(2) and their asymptotic sizes both depend on the value of α and we establish by several techniques that there exists a bifurcation point α(c)=0.763±0.002. For αε[0.6,α(c)), C(1) stops growing the instant it emerges and the delay between the emergence of C(1) and C(2) decreases with increasing α. For αε(α(c),0.95], in contrast, C(1) continues growing into the supercritical regime and the delay between the emergence of C(1) and C(2) increases with increasing α. As we show, α(c) marks the minimal delay possible between the emergence of C(1) and C(2) (i.e., the smallest edge density for which C(2) can exist). We also establish many features of the continuous percolation of C(2) including scaling exponents and relations.

Avoiding a spanning cluster in percolation models

When dynamics in a system proceeds under suppressive external bias, the system can undergo an abrupt phase transition, as can happen when an epidemic spreads. Recently, an explosive percolation (EP) model was introduced to understand such phenomena. The order of the EP transition has not been clarified in a unified framework covering low-dimensional systems and the mean-field limit. We introduce a stochastic model in which a rule for dynamics is designed to avoid the formation of a spanning cluster through competitive selection in Euclidean space. We use heuristic arguments to show that in the thermodynamic limit and depending on a control parameter, the EP transition can be either continuous or discontinuous if d < d(c) and is always continuous if d ≥ d(c), where d(c) is the spatial dimension and d is the upper critical dimension.

Correlated percolation and tricriticality

The recent proliferation of correlated percolation models--models where the addition of edges and/or vertices is no longer independent of other edges and/or vertices--has been motivated by the quest to find discontinuous percolation transitions. The leader in this proliferation is what is known as explosive percolation. A recent proof demonstrates that a large class of explosive percolation-type models does not, in fact, exhibit a discontinuous transition [Riordan and Warnke, Science, 333, 322 (2011)]. Here, we discuss two lesser known correlated percolation models--the k ≥ 3-core model on random graphs and the counter-balance model in two-dimensions--both exhibiting discontinuous transitions. To search for tricriticality, we construct mixtures of these models with other percolation models exhibiting the more typical continuous transition. Using a powerful rate equation approach, we demonstrate that a mixture of k = 2-core and k = 3-core vertices on the random graph exhibits a tricritical point. However, for a mixture of k-core and counter-balance vertices in two dimensions, as the fraction of counter-balance vertices is increased, numerics and heuristic arguments suggest that there is a line of continuous transitions with the line ending at a discontinuous transition, i.e., when all vertices are counter-balanced. Interestingly, these heuristic arguments may help identify the ingredients needed for a discontinuous transition in low dimensions. In addition, our results may have potential implications for glassy and jamming systems.

Achlioptas processes are not always self-averaging

We consider a class of percolation models, called Achlioptas processes, discussed in Science 323, 1453 (2009) and Science 333, 322 (2011). For these, the evolution of the order parameter (the rescaled size of the largest connected component) has been the main focus of research in recent years. We show that, in striking contrast to "classical" models, self-averaging is not a universal feature of these new percolation models: there are natural Achlioptas processes whose order parameter has random fluctuations that do not disappear in the thermodynamic limit.

Explosive percolation on the Bethe lattice

Based on self-consistent equations of the order parameter P∞ and the mean cluster size S, we develop a self-consistent simulation method for arbitrary percolation on the Bethe lattice (infinite homogeneous Cayley tree). By applying the self-consistent simulation to well-known percolation models, random bond percolation, and bootstrap percolation, we obtain prototype functions for continuous and discontinuous phase transitions. By comparing key functions obtained from self-consistent simulations for Achlioptas models with a product rule and a sum rule to the prototype functions, we show that the percolation transition of Achlioptas models on the Bethe lattice is continuous regardless of details of growth rules.