Finite-size scaling theory for explosive percolation transitions

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.

Statistical Properties of the Quantum Internet

Steady technological advances are paving the way for the implementation of the quantum internet, a network of locations interconnected by quantum channels. Here we propose a model to simulate a quantum internet based on optical fibers and employ network-theory techniques to characterize the statistical properties of the photonic networks it generates. Our model predicts a continuous phase transition between a disconnected and a highly connected phase and that the typical photonic networks do not present the small world property. We compute the critical exponents characterizing the phase transition, provide quantitative estimates for the minimum density of nodes needed to have a fully connected network and for the average distance between nodes. Our results thus provide quantitative benchmarks for the development of a quantum internet.

Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks

The study of network robustness focuses on the way the overall functionality of a network is affected as some of its constituent parts fail. Failures can occur at random or be part of an intentional attack and, in general, networks behave differently against different removal strategies. Although much effort has been put on this topic, there is no unified framework to study the problem. While random failures have been mostly studied under percolation theory, targeted attacks have been recently restated in terms of network dismantling. In this work, we link these two approaches by performing a finite-size scaling analysis to four dismantling strategies over Erdös-Rényi networks: initial and recalculated high degree removal and initial and recalculated high betweenness removal. We find that the critical exponents associated with the initial attacks are consistent with the ones corresponding to random percolation. For recalculated high degree, the exponents seem to deviate from mean field, but the evidence is not conclusive. Finally, recalculated betweenness produces a very abrupt transition with a hump in the cluster size distribution near the critical point, resembling some explosive percolation processes.

Entropy, specific heat, susceptibility, and Rushbrooke inequality in percolation

We investigate percolation, a probabilistic model for continuous phase transition, on square and weighted planar stochastic lattices. In its thermal counterpart, entropy is minimally low where order parameter (OP) is maximally high and vice versa. In addition, specific heat, OP, and susceptibility exhibit power law when approaching the critical point and the corresponding critical exponents α,β,γ respectably obey the Rushbrooke inequality (RI) α+2β+γ≥2. Their analogs in percolation, however, remain elusive. We define entropy and specific heat and redefine susceptibility for percolation and show that they behave exactly in the same way as their thermal counterpart. We also show that RI holds for both the lattices albeit they belong to different universality classes.

Explosive percolation on a scale-free multifractal weighted planar stochastic lattice

In this article, we investigate explosive bond percolation (EBP) with the product rule, formally known as the Achlioptas process, on a scale-free multifractal weighted planar stochastic lattice. One of the key features of the EBP transition is the delay, compared to the corresponding random bond percolation (RBP), in the onset of the spanning cluster. However, when it happens, it happens so dramatically that initially it was believed, although ultimately proved wrong, that explosive percolation (EP) exhibits a first-order transition. In the case of EP, much effort has been devoted to resolving the issue of its order of transition and almost no effort has been devoted to finding the critical point, critical exponents, etc., to classify it into universality classes. This is in sharp contrast to the situation for classical random percolation. We do not even know all the exponents of EP for a regular planar lattice or for an Erdös-Renyi network. We first find the critical point p_{c} numerically and then obtain all the critical exponents, β, γ, and ν, as well as the Fisher exponent τ and the fractal dimension d_{f} of the spanning cluster. We also compare our results for EBP with those for RBP and find that all the exponents of EBP obey the same scaling relations as do those for RBP. Our findings suggest that EBP is not special except for the fact that the exponent β is unusually small compared to that for RBP.

Kinetics of aggregation with choice

We generalize the ordinary aggregation process to allow for choice. In ordinary aggregation, two random clusters merge and form a larger aggregate. In our implementation of choice, a target cluster and two candidate clusters are randomly selected and the target cluster merges with the larger of the two candidate clusters. We study the long-time asymptotic behavior and find that as in ordinary aggregation, the size density adheres to the standard scaling form. However, aggregation with choice exhibits a number of different features. First, the density of the smallest clusters exhibits anomalous scaling. Second, both the small-size and the large-size tails of the density are overpopulated, at the expense of the density of moderate-size clusters. We also study the complementary case where the smaller candidate cluster participates in the aggregation process and find an abundance of moderate clusters at the expense of small and large clusters. Additionally, we investigate aggregation processes with choice among multiple candidate clusters and a symmetric implementation where the choice is between two pairs of clusters.

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.

Scaling of clusters near discontinuous percolation transitions in hyperbolic networks

We investigate the onset of the discontinuous percolation transition in small-world hyperbolic networks by studying the systems-size scaling of the typical largest cluster approaching the transition, p ↗ p(c). To this end, we determine the average size of the largest cluster 〈s(max)〉 ∼ N(Ψ(p)) in the thermodynamic limit using real-space renormalization of cluster-generating functions for bond and site percolation in several models of hyperbolic networks that provide exact results. We determine that all our models conform to the recently predicted behavior regarding the growth of the largest cluster, which found diverging, albeit subextensive, clusters spanning the system with finite probability well below p(c) and at most quadratic corrections to unity in Ψ(p) for p ↗ p(c). Our study suggests a large universality in the cluster formation on small-world hyperbolic networks and the potential for an alternative mechanism in the cluster formation dynamics at the onset of discontinuous percolation transitions.

Percolation transitions with nonlocal constraint

We investigate percolation transitions in a nonlocal network model numerically. In this model, each node has an exclusive partner and a link is forbidden between two nodes whose r-neighbors share any exclusive pair. The r-neighbor of a node x is defined as a set of at most N(r) neighbors of x, where N is the total number of nodes. The parameter r controls the strength of a nonlocal effect. The system is found to undergo a percolation transition belonging to the mean-field universality class for r<1/2. On the other hand, for r>1/2, the system undergoes a peculiar phase transition from a nonpercolating phase to a quasicritical phase where the largest cluster size G scales as G~N(α) with α=0.74(1). In the marginal case with r=1/2, the model displays a percolation transition that does not belong to the mean-field universality class.

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.

Discontinuous percolation transitions in epidemic processes, surface depinning in random media, and Hamiltonian random graphs

Discontinuous percolation transitions and the associated tricritical points are manifest in a wide range of both equilibrium and nonequilibrium cooperative phenomena. To demonstrate this, we present and relate the continuous and first-order behaviors in two different classes of models: The first are generalized epidemic processes that describe in their spatially embedded version--either on or off a regular lattice--compact or fractal cluster growth in random media at zero temperature. A random graph version of these processes is mapped onto a model previously proposed for complex social contagion. We compute detailed phase diagrams and compare our numerical results at the tricritical point in d = 3 with field theory predictions of Janssen et al. [Phys. Rev. E 70, 026114 (2004)]. The second class consists of exponential ("Hamiltonian," i.e., formally equilibrium) random graph models and includes the Strauss and the two-star model, where "chemical potentials" control the densities of links, triangles, or two-stars. When the chemical potentials in either graph model are O(logN), the percolation transition can coincide with a first-order phase transition in the density of links, making the former also discontinuous. Hysteresis loops can then be of mixed order, with second-order behavior for decreasing link fugacity, and a jump (first order) when it increases.

Continuous percolation phase transitions of random networks under a generalized Achlioptas process

Using finite-size scaling, we have investigated the percolation phase transitions of evolving random networks under a generalized Achlioptas process (GAP). During this GAP, the edge with a minimum product of two connecting cluster sizes is taken with a probability p from two randomly chosen edges. This model becomes the Erdös-Rényi network at p=0.5 and the random network under the Achlioptas process at p=1. Using both the fixed point of the size ratio s{2}/s{1} and the straight line of lns{1}, where s{1} and s{2} are the reduced sizes of the largest and the second-largest cluster, we demonstrate that the phase transitions of this model are continuous for 0.5 ≤ p ≤ 1. From the slopes of lns{1} and ln(s{2}/s{1})' at the critical point, we get critical exponents β and ν of the phase transitions. At 0.5 ≤ p ≤ 0.8, it is found that β, ν, and s{2}/s{1} at critical point are unchanged and the phase transitions belong to the same universality class. When p ≥ 0.9, β, ν, and s{2}/s{1} at critical point vary with p and the universality class of phase transitions depends on p.

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.

Nonlocal product rules for percolation

Despite original claims of a first-order transition in the product rule model proposed by Achlioptas et al. [Science 323, 1453 (2009)], recent studies indicate that this percolation model, in fact, displays a continuous transition. The distinctive scaling properties of the model at criticality, however, strongly suggest that it should belong to a different universality class than ordinary percolation. Here we introduce a generalization of the product rule that reveals the effect of nonlocality on the critical behavior of the percolation process. Precisely, pairs of unoccupied bonds are chosen according to a probability that decays as a power law of their Manhattan distance, and only that bond connecting clusters whose product of their sizes is the smallest becomes occupied. Interestingly, our results for two-dimensional lattices at criticality shows that the power-law exponent of the product rule has a significant influence on the finite-size scaling exponents for the spanning cluster, the conducting backbone, and the cutting bonds of the system. In all three cases, we observe a clear transition from ordinary to (nonlocal) explosive percolation exponents.

Bohman-Frieze-Wormald model on the lattice, yielding a discontinuous percolation transition

The BFW model introduced by Bohman, Frieze, and Wormald [Random Struct. Algorithms, 25, 432 (2004)], and recently investigated in the framework of discontinuous percolation by Chen and D'Souza [Phys. Rev. Lett. 106, 115701 (2011)], is studied on the square and simple-cubic lattices. In two and three dimensions, we find numerical evidence for a strongly discontinuous transition. In two dimensions, the clusters at the threshold are compact with a fractal surface of fractal dimension d(f)=1.49±0.02. On the simple-cubic lattice, distinct jumps in the size of the largest cluster are observed. We proceed to analyze the tree-like version of the model, where only merging bonds are sampled, for dimension two to seven. The transition is again discontinuous in any considered dimension. Finally, the dependence of the cluster-size distribution at the threshold on the spatial dimension is also investigated.

Suppression effect on explosive percolation

Percolation transitions (PTs) of networks, leading to the formation of a macroscopic cluster, are conventionally considered to be continuous transitions. However, a modified version of the classical random graph model was introduced in which the growth of clusters was suppressed, and a PT occurs explosively at a delayed transition point. Whether the explosive PT is indeed discontinuous or continuous becomes controversial. Here, we show that the behavior of the explosive PT depends on detailed dynamic rules. Thus, when dynamic rules are designed to suppress the growth of all clusters, the discontinuity of the order parameter tends to a finite value as the system size increases, indicating that the explosive PT could be discontinuous.

Discontinuous percolation transitions in real physical systems

We study discontinuous percolation transitions (PTs) in the diffusion-limited cluster aggregation model of the sol-gel transition as an example of real physical systems, in which the number of aggregation events is regarded as the number of bonds occupied in the system. When particles are Brownian, in which cluster velocity depends on cluster size as v(s)~s(η) with η=-0.5, a larger cluster has less probability to collide with other clusters because of its smaller mobility. Thus, the cluster is effectively more suppressed in growth of its size. Then the giant cluster size increases drastically by merging those suppressed clusters near the percolation threshold, exhibiting a discontinuous PT. We also study the tricritical behavior by controlling the parameter η, and the tricritical point is determined by introducing an asymmetric Smoluchowski equation.

Continuity of the explosive percolation transition

The explosive percolation problem on the complete graph is investigated via extensive numerical simulations. We obtain the cluster-size distribution at the moment when the cluster size heterogeneity becomes maximum. The distribution is found to be well described by the power-law form with the decay exponent τ=2.06(2), followed by a hump. We then use the finite-size scaling method to make all the distributions at various system sizes up to N=2(37) collapse perfectly onto a scaling curve characterized solely by the single exponent τ. We also observe that the instant of that collapse converges to a well-defined percolation threshold from below as N→∞. Based on these observations, we show that the explosive percolation transition in the model should be continuous, contrary to the widely spread belief of its discontinuity.

Explosive site percolation with a product rule

We study the site percolation under Achlioptas process with a product rule in a two-dimensional square lattice. From the measurement of the cluster size distribution P(s), we find that P(s) has a very robust power-law regime followed by a stable hump near the transition threshold. Based on the careful analysis on the PP(s) distribution, we show that the transition should be discontinuous. The existence of the hysteresis loop in order parameter also verifies that the transition is discontinuous in two dimensions. Moreover, we also show that the transition nature from the product rule is not the same as that from a sum rule in two dimensions.

Explosive percolation is continuous

"Explosive percolation" is said to occur in an evolving network when a macroscopic connected component emerges in a number of steps that is much smaller than the system size. Recent predictions based on simulations suggested that certain Achlioptas processes (much-studied local modifications of the classical mean-field growth model of Erdős and Rényi) exhibit this phenomenon, undergoing a phase transition that is discontinuous in the scaling limit. We show that, in fact, all Achlioptas processes have continuous phase transitions, although related models in which the number of nodes sampled may grow with the network size can indeed exhibit explosive percolation.

Explosive percolation is continuous, but with unusual finite size behavior

We study four Achlioptas-type processes with "explosive" percolation transitions. All transitions are clearly continuous, but their finite size scaling functions are not entirely holomorphic. The distributions of the order parameter, i.e., the relative size s(max)/N of the largest cluster, are double humped. But-in contrast to first-order phase transitions-the distance between the two peaks decreases with system size N as N(-η) with η>0. We find different positive values of β (defined via (s(max)/N)∼(p-p(c))β for infinite systems) for each model, showing that they are all in different universality classes. In contrast, the exponent Θ (defined such that observables are homogeneous functions of (p-p(c))N(Θ)) is close to-or even equal to-1/2 for all models.

Tricritical point in explosive percolation

The suitable interpolation between classical percolation and a special variant of explosive percolation enables the explicit realization of a tricritical percolation point. With high-precision simulations of the order parameter and the second moment of the cluster size distribution a fully consistent tricritical scaling scenario emerges yielding the tricritical crossover exponent 1/φ(t)=1.8 ± 0.1.

Explosive percolation transition is actually continuous

Recently a discontinuous percolation transition was reported in a new "explosive percolation" problem for irreversible systems [D. Achlioptas, R. M. D'Souza, and J. Spencer, Science 323, 1453 (2009)] in striking contrast to ordinary percolation. We consider a representative model which shows that the explosive percolation transition is actually a continuous, second order phase transition though with a uniquely small critical exponent of the percolation cluster size. We describe the unusual scaling properties of this transition and find its critical exponents and dimensions.

Scaling behavior of explosive percolation on the square lattice

Clusters generated by the product-rule growth model of Achlioptas, D'Souza, and Spencer on a two-dimensional square lattice are shown to obey qualitatively different scaling behavior than standard (random growth) percolation. The threshold with unrestricted bond placement (allowing loops) is found precisely using several different criteria based on both moments and wrapping probabilities, yielding p(c)=0.526 565 ± 0.000005, consistent with the recent result of Radicchi and Fortunato. The correlation-length exponent ν is found to be close to 1. The qualitative difference from regular percolation is shown dramatically in the behavior of the percolation probability P∞ (size of largest cluster), of the susceptibility, and of the second moment of finite clusters, where discontinuities appear at the threshold. The critical cluster-size distribution does not follow a consistent power law for the range of system sizes we study (L ≤ 8192) but may approach a power law with τ>2 for larger L .