Achlioptas processes are not always self-averaging

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.

Heterogeneity in outcomes of repeated instances of percolation experiments

We investigate the heterogeneity of outcomes of repeated instances of percolation experiments in complex networks using a message-passing approach to evaluate heterogeneous, node-dependent probabilities of belonging to the giant or percolating cluster, i.e., the set of mutually connected nodes whose size scales linearly with the size of the system. We evaluate these both for large finite single instances and for synthetic networks in the configuration model class in the thermodynamic limit. For the latter, we consider both Erdős-Rényi and scale-free networks as examples of networks with narrow and broad degree distributions, respectively. For real-world networks we use an undirected version of a Gnutella peer-to-peer file-sharing network with N=62568 nodes as an example. We derive the theory for multiple instances of both uncorrelated and correlated percolation processes. For the uncorrelated case, we also obtain a closed-form approximation for the large mean degree limit of Erdős-Rényi networks.

Fluctuations and self-averaging in random trapping transport: The diffusion coefficient

On the basis of a self-consistent cluster effective-medium approximation for random trapping transport, we study the problem of self-averaging of the diffusion coefficient in a nonstationary formulation. In the long-time domain, we investigate different cases that correspond to the increasing degree of disorder. In the regular and subregular cases the diffusion coefficient is found to be a self-averaging quantity-its relative fluctuations (relative standard deviation) decay in time in a power-law fashion. In the subdispersive case the diffusion coefficient is self-averaging in three dimensions (3D) and weakly self-averaging in two dimensions (2D) and one dimension (1D), when its relative fluctuations decay anomalously slowly logarithmically. In the dispersive case, the diffusion coefficient is self-averaging in 3D, weakly self-averaging in 2D, and non-self-averaging in 1D. When non-self-averaging, its fluctuations remain of the same order as, or larger than, its average value. In the irreversible case, the diffusion coefficient is non-self-averaging in any dimension. In general, with the decreasing dimension and/or increasing disorder, the self-averaging worsens and eventually disappears. In the cases of weak self-averaging and, especially, non-self-averaging, the reliable reproducible experimental measurements are highly problematic. In all the cases under consideration, asymptotics with prefactors are obtained beyond the scaling laws. Transition between all cases is analyzed as the disorder increases.

Non-self-averaging in random trapping transport: The diffusion coefficient in the fluctuation regime

The nonstationary diffusion of particles in a medium with static random traps or sinks is considered. The question of the self-averaging of the diffusion coefficient (or, equivalently, of the mean-square displacement) is addressed for the fluctuation regime in the long-time limit. The property of self-averaging is needed for the result of a single measurement to be representative and reproducible. It is demonstrated that the diffusion coefficient of the surviving particles is a strongly non-self-averaging quantity: In a d-dimensional system its reciprocal standard deviation grows with time exponentially ≈exp[const_{d,1}t^{d/(d+2)}]. The same result is reproduced in the "normalized" formulation "per one survivor on average." The case when all the particles, both the survivors and the trapped ones, are contributing to the diffusion coefficient and its variance is considered also. Non-self-averaging is demonstrated for this case as well, the fluctuations of the diffusion coefficient being of the same order as its average value. The critical dimension, above which the mean-field result becomes exact, is infinite-due to the drastic difference between the classes of trajectories, upon which the corresponding results are being built. In high dimensions the strong non-self-averaging of survivors is preserved. For the case of all the particles taken into account, the nonstrong non-self-averaging is retained for any finite dimension. However, for d→∞ the limiting value of the reciprocal standard deviation, calculated for all the particles, decreases to zero. This signifies restoration of the self-averaging in some sense. In all the cases, the time evolution of the average characteristics and of their variances is governed by the decaying concentration of the survivors in fluctuational cavities.

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

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.

Densification and structural transitions in networks that grow by node copying

We introduce a growing network model, the copying model, in which a new node attaches to a randomly selected target node and, in addition, independently to each of the neighbors of the target with copying probability p. When p<1/2, this algorithm generates sparse networks, in which the average node degree is finite. A power-law degree distribution also arises, with a nonuniversal exponent whose value is determined by a transcendental equation in p. In the sparse regime, the network is "normal," e.g., the relative fluctuations in the number of links are asymptotically negligible. For p≥1/2, the emergent networks are dense (the average degree increases with the number of nodes N), and they exhibit intriguing structural behaviors. In particular, the N dependence of the number of m cliques (complete subgraphs of m nodes) undergoes m-1 transitions from normal to progressively more anomalous behavior at an m-dependent critical values of p. Different realizations of the network, which start from the same initial state, exhibit macroscopic fluctuations in the thermodynamic limit: absence of self-averaging. When linking to second neighbors of the target node can occur, the number of links asymptotically grows as N^{2} as N→∞, so that the network is effectively complete as N→∞.

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.

Structural Transitions in Densifying Networks

We introduce a minimal generative model for densifying networks in which a new node attaches to a randomly selected target node and also to each of its neighbors with probability p. The networks that emerge from this copying mechanism are sparse for p<1/2 and dense (average degree increasing with number of nodes N) for p≥1/2. The behavior in the dense regime is especially rich; for example, individual network realizations that are built by copying are disparate and not self-averaging. Further, there is an infinite sequence of structural anomalies at p=2/3, 3/4, 4/5, etc., where the N dependences of the number of triangles (3-cliques), 4-cliques, undergo phase transitions. When linking to second neighbors of the target can occur, the probability that the resulting graph is complete-all nodes are connected-is nonzero as N→∞.

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.

Method for estimating critical exponents in percolation processes with low sampling

In phase-transition phenomena, the estimation of the critical point is crucial for the calculation of the various critical exponents and the determination of the universality class they belong to. However, this is not an easy task, since a large amount of realizations is needed to eliminate the noise in the data. In this paper, we introduce a novel method for the simultaneous estimation of the critical point p(c) and the critical exponent β/ν, applied for the case of "explosive" bond percolation on two-dimensional square lattices and Erdös-Rényi networks. The results show that with only a few hundred realizations, it is possible to acquire accurate values for these quantities. Guidelines are given at the end for the applicability of the method to other cases as well.

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.

Microtransition cascades to percolation

We report the discovery of a discrete hierarchy of microtransitions occurring in models of continuous and discontinuous percolation. The precursory microtransitions allow us to target almost deterministically the location of the transition point to global connectivity. This extends to the class of intrinsically stochastic processes the possibility to use warning signals anticipating phase transitions in complex systems.

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.

Criticality and scaling behavior of percolation with multiple giant clusters under an Achlioptas process

Achlioptas processes, a class of percolation models which can lead to rich critical phenomena, including the well-known explosive percolation, have attracted much attention in recent years. In this paper, we show that, in a three-vertex Achlioptas process, two giant clusters emerge after the percolation transition with size fluctuations in different realizations, and the choice of the connecting vertex in the smaller cluster depends on a probability parameter p, the increase of which can make the transition sharper. Using finite-size scaling analysis, we can determine the critical point r(c) and critical exponents η, 1/ν, and β through Monte Carlo simulations. Comparison of such exponents for different giant clusters indicates that their critical nature is always the same. However, when link choice is strongly biased, it is surprising that the scaling relation η=β/ν is violated, and the data collapse for scaling function diverges. Furthermore, by inspecting the variance of exponents with p, three distinct scaling phases are classified for different parameter intervals according to the divergence scaling function, which suggests an inconsistent scaling form in the critical window with the supercritical region. The study on the criticality and scaling behavior of multiple giant clusters in an Achlioptas process, in particular, the discovery of three scaling phases that depend on the parameter p, may help us in finding a complete scaling theory for the Achlioptas-process percolation and give insight into understanding the accelerating nature of the phase transition for Achlioptas processes once reaching criticality.

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.

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.

Weakly explosive percolation in directed networks

Percolation, the formation of a macroscopic connected component, is a key feature in the description of complex networks. The dynamical properties of a variety of systems can be understood in terms of percolation, including the robustness of power grids and information networks, the spreading of epidemics and forest fires, and the stability of gene regulatory networks. Recent studies have shown that if network edges are added "competitively" in undirected networks, the onset of percolation is abrupt or "explosive." The unusual qualitative features of this phase transition have been the subject of much recent attention. Here we generalize this previously studied network growth process from undirected networks to directed networks and use finite-size scaling theory to find several scaling exponents. We find that this process is also characterized by a very rapid growth in the giant component, but that this growth is not as sudden as in undirected networks.

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.