Cluster aggregation model for discontinuous percolation transitions

Percolation critical exponents in cluster kinetics of pulse-coupled oscillators

Transient dynamics leading to the synchrony of a type of pulse-coupled oscillators, so-called scrambler oscillators, has previously been studied as an aggregation process of synchronous clusters, and a rate equation for the cluster size distribution has been proposed. However, the evolution of the cluster size distribution for general cluster sizes has not been fully understood yet. In this paper, we study the evolution of the cluster size distribution from the perspective of a percolation model by regarding the number of aggregations as the number of attached bonds. Specifically, we derive the scaling form of the cluster size distribution with specific values of the critical exponents using the property that the characteristic cluster size diverges as the percolation threshold is approached from below. Through simulation, it is confirmed that the scaling form well explains the evolution of the cluster size distribution. Based on the distribution behavior, we find that a giant cluster of all oscillators is formed discontinuously at the threshold and also that further aggregation does not occur like in a one-dimensional bond percolation model. Finally, we discuss the origin of the discontinuous formation of the giant cluster from the perspective of global suppression in explosive percolation models. For this, we approximate the aggregation process as a cluster-cluster aggregation with a given collision kernel. We believe that the theoretical approach presented in this paper can be used to understand the transient dynamics of a broad range of synchronizations.

No-exclaves percolation

Network robustness has been a pivotal issue in the study of system failure in network science since its inception. To shed light on this subject, we introduce and study a new percolation process based on a new cluster called an 'exclave' cluster. The entities comprising exclave clusters in a network are the sets of connected unfailed nodes that are completely surrounded by the failed (i.e., nonfunctional) nodes. The exclave clusters are thus detached from other unfailed parts of the network, thereby becoming effectively nonfunctional. This process defines a new class of clusters of nonfunctional nodes. We call it the no-exclave percolation cluster (NExP cluster), formed by the connected union of failed clusters and the exclave clusters they enclose. Here we showcase the effect of NExP cluster, suggesting a wide and disruptive collapse in two empirical infrastructure networks. We also study on two-dimensional Euclidean lattice to analyze the phase transition behavior using finite-size scaling. The NExP model considering the collective failure clusters uncovers new aspects of network collapse as a percolation process, such as quantitative change of transition point and qualitative change of transition type. Our study discloses hidden indirect damage added to the damage directly from attacks, and thus suggests a new useful way for finding nonfunctioning areas in complex systems under external perturbations as well as internal partial closures.

Statistical physics approaches to the complex Earth system

Global warming, extreme climate events, earthquakes and their accompanying socioeconomic disasters pose significant risks to humanity. Yet due to the nonlinear feedbacks, multiple interactions and complex structures of the Earth system, the understanding and, in particular, the prediction of such disruptive events represent formidable challenges to both scientific and policy communities. During the past years, the emergence and evolution of Earth system science has attracted much attention and produced new concepts and frameworks. Especially, novel statistical physics and complex networks-based techniques have been developed and implemented to substantially advance our knowledge of the Earth system, including climate extreme events, earthquakes and geological relief features, leading to substantially improved predictive performances. We present here a comprehensive review on the recent scientific progress in the development and application of how combined statistical physics and complex systems science approaches such as critical phenomena, network theory, percolation, tipping points analysis, and entropy can be applied to complex Earth systems. Notably, these integrating tools and approaches provide new insights and perspectives for understanding the dynamics of the Earth systems. The overall aim of this review is to offer readers the knowledge on how statistical physics concepts and theories can be useful in the field of Earth system science.

Coagulation with product kernel and arbitrary initial conditions: Exact kinetics within the Marcus-Lushnikov framework

The time evolution of a system of coagulating particles under the product kernel and arbitrary initial conditions is studied. Using the improved Marcus-Lushnikov approach, the master equation is solved for the probability W(Q,t) to find the system in a given mass spectrum Q={n_{1},n_{2},⋯,n_{g}⋯}, with n_{g} being the number of particles of size g. The exact expression for the average number of particles 〈n_{g}(t)〉 at arbitrary time t is derived and its validity is confirmed in numerical simulations of several selected initial mass spectra.

Anomalous percolation features in molecular evolution

Self-replication underlies every species of living beings and simple physical intuition dictates that some sort of autocatalysis invariably constitutes a necessary ingredient for the emergence of molecular life. This led Worst et al. [E. G. Worst, P. Zimmer, E. Wollrab, K. Kruse, and A. Ott, New J. Phys. 18, 103003 (2016)NJOPFM1367-263010.1088/1367-2630/18/10/103003] to study a model of molecular evolution of self-replicating molecules where spontaneous ligation and simple autocatalysis are in competition for their building blocks. We revisit this model, where irreversible aggregation leads to a transition from a regime of small molecules to macromolecules, and find an array of anomalous percolation features, some of them predicted for very specific percolation processes [R. M. D'Souza and J. Nagler, Nat. Phys. 11, 531 (2015)1745-247310.1038/nphys3378].

Exact combinatorial approach to finite coagulating systems

This paper outlines an exact combinatorial approach to finite coagulating systems. In this approach, cluster sizes and time are discrete and the binary aggregation alone governs the time evolution of the systems. By considering the growth histories of all possible clusters, an exact expression is derived for the probability of a coagulating system with an arbitrary kernel being found in a given cluster configuration when monodisperse initial conditions are applied. Then this probability is used to calculate the time-dependent distribution for the number of clusters of a given size, the average number of such clusters, and that average's standard deviation. The correctness of our general expressions is proved based on the (analytical and numerical) results obtained for systems with the constant kernel. In addition, the results obtained are compared with the results arising from the solutions to the mean-field Smoluchowski coagulation equation, indicating its weak points. The paper closes with a brief discussion on the extensibility to other systems of the approach presented herein, emphasizing the issue of arbitrary initial conditions.

Degree product rule tempers explosive percolation in the absence of global information

We introduce a guided network growth model, which we call the degree product rule process, that uses solely local information when adding new edges. For small numbers of candidate edges our process gives rise to a second-order phase transition, but becomes first order in the limit of global choice. We provide the set of critical exponents required to characterize the nature of this percolation transition. Such a process permits interventions which can delay the onset of percolation while tempering the explosiveness caused by cluster product rule processes.

Controlling percolation with limited resources

Connectivity, or the lack thereof, is crucial for the function of many man-made systems, from financial and economic networks over epidemic spreading in social networks to technical infrastructure. Often, connections are deliberately established or removed to induce, maintain, or destroy global connectivity. Thus, there has been a great interest in understanding how to control percolation, the transition to large-scale connectivity. Previous work, however, studied control strategies assuming unlimited resources. Here, we depart from this unrealistic assumption and consider the effect of limited resources on the effectiveness of control. We show that, even for scarce resources, percolation can be controlled with an efficient intervention strategy. We derive such an efficient strategy and study its implications, revealing a discontinuous transition as an unintended side effect of optimal control.

Genuine non-self-averaging and ultraslow convergence in gelation

In irreversible aggregation processes droplets or polymers of microscopic size successively coalesce until a large cluster of macroscopic scale forms. This gelation transition is widely believed to be self-averaging, meaning that the order parameter (the relative size of the largest connected cluster) attains well-defined values upon ensemble averaging with no sample-to-sample fluctuations in the thermodynamic limit. Here, we report on anomalous gelation transition types. Depending on the growth rate of the largest clusters, the gelation transition can show very diverse patterns as a function of the control parameter, which includes multiple stochastic discontinuous transitions, genuine non-self-averaging and ultraslow convergence of the transition point. Our framework may be helpful in understanding and controlling gelation.

Hybrid Percolation Transition in Cluster Merging Processes: Continuously Varying Exponents

Consider growing a network, in which every new connection is made between two disconnected nodes. At least one node is chosen randomly from a subset consisting of g fraction of the entire population in the smallest clusters. Here we show that this simple strategy for improving connection exhibits a more unusual phase transition, namely a hybrid percolation transition exhibiting the properties of both first-order and second-order phase transitions. The cluster size distribution of finite clusters at a transition point exhibits power-law behavior with a continuously varying exponent τ in the range 2<τ(g)≤2.5. This pattern reveals a necessary condition for a hybrid transition in cluster aggregation processes, which is comparable to the power-law behavior of the avalanche size distribution arising in models with link-deleting processes in interdependent networks.

Two Types of Discontinuous Percolation Transitions in Cluster Merging Processes

Percolation is a paradigmatic model in disordered systems and has been applied to various natural phenomena. The percolation transition is known as one of the most robust continuous transitions. However, recent extensive studies have revealed that a few models exhibit a discontinuous percolation transition (DPT) in cluster merging processes. Unlike the case of continuous transitions, understanding the nature of discontinuous phase transitions requires a detailed study of the system at hand, which has not been undertaken yet for DPTs. Here we examine the cluster size distribution immediately before an abrupt increase in the order parameter of DPT models and find that DPTs induced by cluster merging kinetics can be classified into two types. Moreover, the type of DPT can be determined by the key characteristic of whether the cluster kinetic rule is homogeneous with respect to the cluster sizes. We also establish the necessary conditions for each type of DPT, which can be used effectively when the discontinuity of the order parameter is ambiguous, as in the explosive percolation model.

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.

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.

Explosive electric breakdown due to conducting-particle deposition on an insulating substrate

We introduce a theoretical model to investigate the electric breakdown of a substrate on which highly conducting particles are adsorbed and desorbed with a probability that depends on the local electric field. We find that, by tuning the relative strength q of this dependence, the breakdown can change from continuous to explosive. Precisely, in the limit in which the adsorption probability is the same for any finite voltage drop, we can map our model exactly onto the q-state Potts model and thus the transition to a jump occurs at q = 4. In another limit, where the adsorption probability becomes independent of the local field strength, the traditional bond percolation model is recovered. Our model is thus an example of a possible experimental realization exhibiting a truly discontinuous percolation transition.

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.

Degree-dependent network growth: from preferential attachment to explosive percolation

We present a simple model of network growth and solve it by writing the dynamic equations for its macroscopic characteristics such as the degree distribution and degree correlations. This allows us to study carefully the percolation transition using a generating functions theory. The model considers a network with a fixed number of nodes wherein links are introduced using degree-dependent linking probabilities pk. To illustrate the techniques and support our findings using Monte Carlo simulations, we introduce the exemplary linking rule pk∝k-α, with α between -1 and +∞. This parameter may be used to interpolate between different regimes. For negative α, links are most likely attached to high-degree nodes. On the other hand, in case α>0, nodes with low degrees are connected and the model asymptotically approaches a process undergoing explosive percolation.

Critical exponents of the explosive percolation transition

In a new type of percolation phase transition, which was observed in a set of nonequilibrium models, each new connection between vertices is chosen from a number of possibilities by an Achlioptas-like algorithm. This causes preferential merging of small components and delays the emergence of the percolation cluster. First simulations led to a conclusion that a percolation cluster in this irreversible process is born discontinuously, by a discontinuous phase transition, which results in the term "explosive percolation transition." We have shown that this transition is actually continuous (second order) though with an anomalously small critical exponent of the percolation cluster. Here we propose an efficient numerical method enabling us to find the critical exponents and other characteristics of this second-order transition for a representative set of explosive percolation models with different number of choices. The method is based on gluing together the numerical solutions of evolution equations for the cluster size distribution and power-law asymptotics. For each of the models, with high precision, we obtain critical exponents and the critical point.

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.

Critical phenomena in heterogeneous k-core percolation

k-core percolation is a percolation model which gives a notion of network functionality and has many applications in network science. In analyzing the resilience of a network under random damage, an extension of this model is introduced, allowing different vertices to have their own degree of resilience. This extension is named heterogeneous k-core percolation and it is characterized by several interesting critical phenomena. Here we analytically investigate binary mixtures in a wide class of configuration model networks and categorize the different critical phenomena which may occur. We observe the presence of critical and tricritical points and give a general criterion for the occurrence of a tricritical point. The calculated critical exponents show cases in which the model belongs to the same universality class of facilitated spin models studied in the context of the glass transition.

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.

Formation mechanism and size features of multiple giant clusters in generic percolation processes

Percolation is one of the most widely studied models in which a unique giant cluster emerges after the phase transition. Recently, a new phenomenon, where multiple giant clusters are observed in the so called Bohman-Frieze-Wormald (BFW) model, has attracted much attention, and how multiple giant clusters could emerge in generic percolation processes on random networks will be discussed in this paper. By introducing the merging probability and inspecting the distinct mechanisms which contribute to the growth of largest clusters, a sufficient condition to generate multiple stable giant clusters is given. Based on the above results, the BFW model and a multi-Erdös-Rényi (ER) model given by us are analyzed, and the mechanism of multiple giant clusters of these two models is revealed. Furthermore, large fluctuations are observed in the size of multiple giant clusters in many models, but the sum size of all giant clusters exhibits self-averaging as that in the size of unique giant cluster in ordinary percolation. Besides, the growth modes of different giant clusters are discussed, and we find that the large fluctuations observed are mainly due to the stochastic behavior of the evolution in the critical window. For all the discussion above, numerical simulations on the BFW model and the multi-ER model are done, which strongly support our analysis. The investigation of merging probability and the growth mechanisms of largest clusters provides insight for the essence of multiple giant clusters in the percolation processes and can be instructive for modeling or analyzing real-world networks consisting of many large clusters.

Social climber attachment in forming networks produces a phase transition in a measure of connectivity

The formation and fragmentation of networks are typically studied using percolation theory, but most previous research has been restricted to studying a phase transition in cluster size, examining the emergence of a giant component. This approach does not study the effects of evolving network structure on dynamics that occur at the nodes, such as the synchronization of oscillators and the spread of information, epidemics, and neuronal excitations. We introduce and analyze an alternative link-formation rule, called social climber (SC) attachment, that may be combined with arbitrary percolation models to produce a phase transition using the largest eigenvalue of the network adjacency matrix as the order parameter. This eigenvalue is significant in the analyses of many network-coupled dynamical systems in which it measures the quality of global coupling and is hence a natural measure of connectivity. We highlight the important self-organized properties of SC attachment and discuss implications for controlling dynamics on networks.

Transmission of packets on a hierarchical network: statistics and explosive percolation

We analyze an idealized model for the transmission or flow of particles, or discrete packets of information, in a weight bearing branching hierarchical two dimensional network and its variants. The capacities add hierarchically down the clusters. Each node can accommodate a limited number of packets, depending on its capacity, and the packets hop from node to node, following the links between the nodes. The statistical properties of this system are given by the Maxwell-Boltzmann distribution. We obtain analytical expressions for the mean occupation numbers as functions of capacity, for different network topologies. The analytical results are shown to be in agreement with the numerical simulations. The traffic flow in these models can be represented by the site percolation problem. It is seen that the percolation transitions in the 2D model and in its variant lattices are continuous transitions, whereas the transition is found to be explosive (discontinuous) for the V lattice, the critical case of the 2D lattice. The scaling behavior of the second-order percolation case is studied in detail. We discuss the implications of our analysis.

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.

Ordinary percolation with discontinuous transitions

Percolation on a one-dimensional lattice and fractals, such as the Sierpinski gasket, is typically considered to be trivial, because they percolate only at full bond density. By dressing up such lattices with small-world bonds, a novel percolation transition with explosive cluster growth can emerge at a non-trivial critical point. There, the usual order parameter, describing the probability of any node to be part of the largest cluster, jumps instantly to a finite value. Here we provide a simple example in the form of a small-world network consisting of a one-dimensional lattice which, when combined with a hierarchy of long-range bonds, reveals many features of this transition in a mathematically rigorous manner.

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.

Gaussian model of explosive percolation in three and higher dimensions

The Gaussian model of discontinuous percolation, recently introduced by Araújo and Herrmann [Phys. Rev. Lett. 105, 035701 (2010)], is numerically investigated in three dimensions, disclosing a discontinuous transition. For the simple cubic lattice, in the thermodynamic limit we report a finite jump of the order parameter J=0.415±0.005. The largest cluster at the threshold is compact, but its external perimeter is fractal with fractal dimension d(A)=2.5±0.2. The study is extended to hypercubic lattices up to six dimensions and to the mean-field limit (infinite dimension). We find that, in all considered dimensions, the percolation transition is discontinuous. The value of the jump in the order parameter, the maximum of the second moment, and the percolation threshold are analyzed, revealing interesting features of the transition and corroborating its discontinuous nature in all considered dimensions. We also show that the fractal dimension of the external perimeter, for any dimension, is consistent with the one from bridge percolation and establish a lower bound for the percolation threshold of discontinuous models with a finite number of clusters at the threshold.

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 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.

Using explosive percolation in analysis of real-world networks

We apply a variant of the explosive percolation procedure to large real-world networks and show with finite-size scaling that the university class, ordinary or explosive, of the resulting percolation transition depends on the structural properties of the network, as well as the number of unoccupied links considered for comparison in our procedure. We observe that in our social networks, the percolation clusters close to the critical point are related to the community structure. This relationship is further highlighted by applying the procedure to model networks with predefined communities.

Explosive percolation with multiple giant components

We generalize the random graph evolution process of Bohman, Frieze, and Wormald [T. Bohman, A. Frieze, and N. C. Wormald, Random Struct. Algorithms, 25, 432 (2004)]. Potential edges, sampled uniformly at random from the complete graph, are considered one at a time and either added to the graph or rejected provided that the fraction of accepted edges is never smaller than a decreasing function asymptotically approaching the value α=1/2. We show that multiple giant components appear simultaneously in a strongly discontinuous percolation transition and remain distinct. Furthermore, tuning the value of α determines the number of such components with smaller α leading to an increasingly delayed and more explosive transition. The location of the critical point and strongly discontinuous nature are not affected if only edges which span components are sampled.

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.

Criterion for explosive percolation transitions on complex networks

In a recent Letter, Friedman and Landsberg discussed the underlying mechanism of explosive phase transitions on complex networks [Phys. Rev. Lett. 103, 255701 (2009).]. This Brief Report presents a modest though more insightful extension of their arguments. We discuss the implications of their results on the cluster-size distribution and deduce that, under general conditions, the percolation transition will be explosive if the mean number of nodes per cluster diverges in the thermodynamic limit and prior to the transition threshold. In other words, if upon increase of the network size n the amount of clusters in the network does not grow proportionally to n, the percolation transition is explosive. Simulations and analytical calculations on various models support our findings.

Transport on exploding percolation clusters

We propose a simple generalization of the explosive percolation process [Achlioptas et al., Science 323, 1453 (2009)], and investigate its structural and transport properties. In this model, at each step, a set of q unoccupied bonds is randomly chosen. Each of these bonds is then associated with a weight given by the product of the cluster sizes that they would potentially connect, and only that bond among the q set which has the smallest weight becomes occupied. Our results indicate that, at criticality, all finite-size scaling exponents for the spanning cluster, the conducting backbone, the cutting bonds, and the global conductance of the system, change continuously and significantly with q. Surprisingly, we also observe that systems with intermediate values of q display the worst conductive performance. This is explained by the strong inhibition of loops in the spanning cluster, resulting in a substantially smaller associated conducting backbone.

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 .

Finite-size scaling theory for explosive percolation transitions

The finite-size scaling (FSS) theory for continuous phase transitions has been useful in determining the critical behavior from the size-dependent behaviors of thermodynamic quantities. When the phase transition is discontinuous, however, FSS approach has not been well established yet. Here, we develop a FSS theory for the explosive percolation transition arising in the Erdős and Rényi model under the Achlioptas process. A scaling function is derived based on the observed fact that the derivative of the curve of the order parameter at the critical point t(c) diverges with system size in a power-law manner, which is different from the conventional one based on the divergence of the correlation length at t(c). We show that the susceptibility is also described in the same scaling form. Numerical simulation data for different system sizes are well collapsed on the respective scaling functions.

Explosive percolation via control of the largest cluster

We show that considering only the largest cluster suffices to obtain a first-order percolation transition. As opposed to previous realizations of explosive percolation, our models obtain Gaussian cluster distributions and compact clusters as one would expect at first-order transitions. We also discover that the cluster perimeters are fractal at the transition point, yielding a fractal dimension of 1.23 ± 0.03, close to that of watersheds.

Local cluster aggregation models of explosive percolation

We introduce perhaps the simplest models of graph evolution with choice that demonstrate discontinuous percolation transitions and can be analyzed via mathematical evolution equations. These models are local, in the sense that at each step of the process one edge is selected from a small set of potential edges sharing common vertices and added to the graph. We show that the evolution can be accurately described by a system of differential equations and that such models exhibit the discontinuous emergence of the giant component. Yet they also obey scaling behaviors characteristic of continuous transitions, with scaling exponents that differ from the classic Erdos-Rényi model.