Critical exponents of the explosive percolation transition

Universality of explosive percolation under product and sum rule

We study explosive percolation processes on random graphs for the so-called product rule (PR) and sum rule (SR), in which M candidate edges are randomly selected from all possible ones at each time step, and the edge with the smallest product or sum of the sizes of the two components that would be joined by the edge is added to the graph, while all other M-1 candidate edges are being discarded. These two rules are prototypical "explosive" percolation rules, which exhibit an extremely abrupt yet continuous phase transition in the thermodynamic limit. Recently, it has been demonstrated that PR and SR belong to the same universality class for two competing edges, i.e., M=2. Here we investigate whether the claimed PR-SR universality is valid for higher-order models with M larger than 2. Based on traditional finite-size scaling theory and largest-gap scaling, we obtain the percolation threshold and the critical exponents of the order parameter, susceptibility, and the derivative of entropy for PR and SR for M from 2 to 9. Our results strongly suggest PR-SR universality, for any fixed M.

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.

Size-independent scaling analysis for explosive percolation

The Achlioptas process, a percolation algorithm on random network, shows a rapid second-order phase transition referred to as explosive percolation. To obtain the transition point and critical exponent β for percolations on a random network, especially for bond percolations, we propose a new scaling analysis that is independent of the system size. The transition point and critical exponent β are estimated for the product-rule (PR) and da Costa-Dorogovtsev-Goltsev-Mendes (dCDGM) (m=2) models of the Achlioptas process, as well as for the Erdős-Rényi (ER) model, which is a classical model in which the analytic values are known. The validity of the scaling analysis is confirmed, especially for the transition point. The estimations of β are also consistent with previously reported values for the ER and dCDGM(2) models, whereas the β estimation for the PR model deviates somewhat. By introducing a parameter representing the maximum cluster size, we develop an extrapolation scheme for the critical exponent β from the simulation just at the transition point in order to obtain a more accurate value. The estimated value of β is improved compared with that obtained by the scaling analysis for the ER model and is also consistent with the β value obtained for the dCDGM(2) model, whereas its deviation from the previously reported value is larger for the PR model. We discuss the accuracy of the present estimations and draw conclusions about their reliability.

Random adsorption process of linear k-mers on square lattices under the Achlioptas process

We study the explosive percolation with k-mer random sequential adsorption (RSA) process. We consider both the Achlioptas process (AP) and the inverse Achlioptas process (IAP), in which giant cluster formation is prohibited and accelerated, respectively. By employing finite-size scaling analysis, we confirm that the percolation transitions are continuous, and thus we calculate the percolation threshold and critical exponents. This allows us to determine the universality class of the k-mer explosive percolation transition. Interestingly, the numerical simulation suggests that the universality class of the explosive percolation transition with the AP alters when the k-mer size changes. In contrast, the universality class of the transition with the IAP is independent of k, but it differs from that of the RSA without the IAP.

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.

Critical phenomena of a hybrid phase transition in cluster merging dynamics

Recently, a hybrid percolation transition (HPT) that exhibits both a discontinuous transition and critical behavior at the same transition point has been observed in diverse complex systems. While the HPT induced by avalanche dynamics has been studied extensively, the HPT induced by cluster merging dynamics (HPT-CMD) has received little attention. Here, we aim to develop a theoretical framework for the HPT-CMD. We find that two correlation-length exponents are necessary for characterizing the giant cluster and finite clusters separately. The conventional formula of the fractal dimension in terms of the critical exponents is not valid. Neither the giant nor finite clusters are fractals, but they have fractal boundaries. A finite-size scaling method for the HPT-CMD is also introduced.

Percolation under noise: Detecting explosive percolation using the second-largest component

We consider the problem of distinguishing between different rates of percolation under noise. A statistical model of percolation is constructed allowing for the birth and death of edges as well as the presence of noise in the observations. This graph-valued stochastic process is composed of a latent and an observed nonstationary process, where the observed graph process is corrupted by type-I and type-II errors. This produces a hidden Markov graph model. We show that for certain choices of parameters controlling the noise, the classical (Erdős-Rényi) percolation is visually indistinguishable from a more rapid form of percolation. In this setting, we compare two different criteria for discriminating between these two percolation models, based on the interquartile range (IQR) of the first component's size, and on the maximal size of the second-largest component. We show through data simulations that this second criterion outperforms the IQR of the first component's size, in terms of discriminatory power. The maximal size of the second component therefore provides a useful statistic for distinguishing between different rates of percolation, under physically motivated conditions for the birth and death of edges, and under noise. The potential application of the proposed criteria for the detection of clinically relevant percolation in the context of applied neuroscience is also discussed.

Explosive percolation transitions in growing networks

Recent extensive studies of the explosive percolation (EP) model revealed that the EP transition is second order with an extremely small value of the critical exponent β associated with the order parameter. This result was obtained from static networks, in which the number of nodes in the system remains constant during the evolution of the network. However, explosive percolating behavior of the order parameter can be observed in social networks, which are often growing networks, where the number of nodes in the system increases as dynamics proceeds. However, extensive studies of the EP transition in such growing networks are still missing. Here we study the nature of the EP transition in growing networks by extending an existing growing network model to a general case in which m node candidates are picked up in the Achiloptas process. When m = 2, this model reduces to the existing model, which undergoes an infinite-order transition. We show that when m ≥ 3, the transition becomes second order due to the suppression effect against the growth of large clusters. Using the rate-equation approach and performing numerical simulations, we also show that the exponent β decreases algebraically with increasing m, whereas it does exponentially in a corresponding static random network model. Finally, we find that the hyperscaling relations hold but in different forms.

Solution of the explosive percolation quest. II. Infinite-order transition produced by the initial distributions of clusters

We describe the effect of power-law initial distributions of clusters on ordinary percolation and its generalizations, specifically, models of explosive percolation processes based on local optimization. These aggregation processes were shown to exhibit continuous phase transitions if the evolution starts from a set of disconnected nodes. Since the critical exponents of the order parameter in explosive percolation transitions turned out to be very small, these transitions were first believed to be discontinuous. In this article we analyze the evolution starting from clusters of nodes whose sizes are distributed according to a power law. We show that these initial distributions change dramatically the position and order of the phase transitions in these problems. We find a particular initial power-law distribution producing a peculiar effect on explosive percolation, namely, before the emergence of the percolation cluster, the system is in a "critical phase" with an infinite generalized susceptibility. This critical phase is absent in ordinary percolation models with any power-law initial conditions. The transition from the critical phase is an infinite-order phase transition, which resembles the scenario of the Berezinskii-Kosterlitz-Thouless phase transition. We obtain the critical singularity of susceptibility at this peculiar infinite-order transition in explosive percolation. It turns out that susceptibility in this situation does not obey the Curie-Weiss law.

Inverting the Achlioptas rule for explosive percolation

In the usual Achlioptas processes the smallest clusters of a few randomly chosen ones are selected to merge together at each step. The resulting aggregation process leads to the delayed birth of a giant cluster and the so-called explosive percolation transition showing a set of anomalous features. We explore a process with the opposite selection rule, in which the biggest clusters of the randomly chosen ones merge together. We develop a theory of this kind of percolation based on the Smoluchowsky equation, find the percolation threshold, and describe the scaling properties of this continuous transition, namely, the critical exponents and amplitudes, and scaling functions. We show that, qualitatively, this transition is similar to the ordinary percolation one, though occurring in less connected systems.

Anomalous discontinuity at the percolation critical point of active gels

We develop a percolation model motivated by recent experimental studies of gels with active network remodeling by molecular motors. This remodeling was found to lead to a critical state reminiscent of random percolation (RP), but with a cluster distribution inconsistent with RP. Our model not only can account for these experiments, but also exhibits an unusual type of mixed phase transition: We find that the transition is characterized by signatures of criticality, but with a discontinuity in the order parameter.

Solution of the explosive percolation quest: scaling functions and critical exponents

Percolation refers to the emergence of a giant connected cluster in a disordered system when the number of connections between nodes exceeds a critical value. The percolation phase transitions were believed to be continuous until recently when, in a new so-called "explosive percolation" problem for a competition-driven process, a discontinuous phase transition was reported. The analysis of evolution equations for this process showed, however, that this transition is actually continuous, though with surprisingly tiny critical exponents. For a wide class of representative models, we develop a strict scaling theory of this exotic transition which provides the full set of scaling functions and critical exponents. This theory indicates the relevant order parameter and susceptibility for the problem and explains the continuous nature of this transition and its unusual properties.