Explosive synchronization transitions in scale-free networks

Explosive collective phenomena have attracted much attention since the discovery of an explosive percolation transition. In this Letter, we demonstrate how an explosive transition shows up in the synchronization of scale-free networks by incorporating a microscopic correlation between the structural and the dynamical properties of the system. The characteristics of the explosive transition are analytically studied in a star graph reproducing the results obtained in synthetic networks. Our findings represent the first abrupt synchronization transition in complex networks and provide a deeper understanding of the microscopic roots of explosive critical phenomena.     

Explosive phenomena in complex networks

The emergence of large-scale connectivity and synchronization are crucial to the structure, function and failure of many complex socio-technical networks. Thus, there is great interest in analyzing phase transitions to large-scale connectivity and to global synchronization, including how to enhance or delay the onset. These phenomena are traditionally studied as second-order phase transitions where, at the critical threshold, the order parameter increases rapidly but continuously. In 2009, an extremely abrupt transition was found for a network growth process where links compete for addition in an attempt to delay percolation. This observation of ‘explosive percolation’ was ultimately revealed to be a continuous transition in the thermodynamic limit, yet with very atypical finite-size scaling, and it started a surge of work on explosive phenomena and their consequences. Many related models are now shown to yield discontinuous percolation transitions and even hybrid transitions. Explosive percolation enables many other features such as multiple giant components, modular structures, discrete scale invariance and non-self-averaging, relating to properties found in many real phenomena such as explosive epidemics, electric breakdowns and the emergence of molecular life. Models of explosive synchronization provide an analytic framework for the dynamics of abrupt transitions and reveal the interplay between the distribution in natural frequencies and the network structure, with applications ranging from epileptic seizures to waking from anesthesia. Here we review the vast literature on explosive phenomena in networked systems and synthesize the fundamental connections between models and survey the application areas. We attempt to classify explosive phenomena based on underlying mechanisms and to provide a coherent overview and perspective for future research to address the many vital questions that remained unanswered.     

The nature of explosive percolation phase transition

In this Letter, we show that the explosive percolation is a novel continuous phase transition. The order-parameter-distribution histogram at the percolation threshold is studied in Erd?s-Rényi networks, scale-free networks, and square lattice. In finite system, two well-defined Gaussian-like peaks coexist, and the valley between the two peaks is suppressed with the system size increasing. This finite-size effect always appears in typical first-order phase transition. However, both of the two peaks shift to zero point in a power law manner, which indicates the explosive percolation is continuous in the thermodynamic limit. The nature of explosive percolation in all the three structures belongs to this novel continuous phase transition. Various scaling exponents concerning the order-parameter-distribution are obtained.     

Erdös Rényi随机网络上爆炸渗流模型相变性质的数值模拟研究

基于改进的Newman和Ziff算法以及有限尺寸标度理论, 通过对表征渗流相变特征物理量的序参量、平均集团尺寸、二阶矩、标准偏差及尺寸不均匀性的数值模拟, 分析研究了Erdös Rényi随机网络上Achlioptas爆炸渗流模型的相变性质.研究表明: 尽管序参量表现出了不连续相变的特征, 但序参量以及其他特征物理量仍具有连续相变的幂律标度行为.因此严格地说, Erdös Rényi随机网络中的爆炸渗流相变是一种奇异相变, 它既不是标准的不连续相变, 又与常规随机渗流表现出的连续相变处于不同的普适类. 关键词： Erdös Rényi随机网络 爆炸渗流模型 相变 幂律标度行为     

Dynamic percolation transition induced by phase separation: A Monte Carlo analysis

The percolation transition of geometric clusters in the three-dimensional, simple cubic, nearest neighbor Ising lattice gas model is investigated in the temperature and concentration region inside the coexistence curve. We consider quenching experiments, where the system starts from an initially completely random configuration (corresponding to equilibrium at infinite temperature), letting the system evolve at the considered temperature according to the Kawasaki spinexchange dynamics. Analyzing the distributionn _l(t) of clusters of sizel at timet, we find that after a time of the order of about 100 Monte Carlo steps per site a percolation transition occurs at a concentration distinctly lower than the percolation concentration of the initial random state. This dynamic percolation transition is analyzed with finite-size scaling methods. While at zero temperature, where the system settles down at a frozen-in cluster distribution and further phase separation stops, the critical exponents associated with this percolation transition are consistent with the universality class of random percolation, the critical behavior of the transient time-dependent percolation occurring at nonzero temperature possibly belongs to a different, new universality class.     

Explosive percolation in the human protein homology network

We study the explosive character of the percolation transition in a real-world network. We show that the emergence of a spanning cluster in the Human Protein Homology Network (H-PHN) exhibits similar features to an Achlioptas-type process and is markedly different from regular random percolation. The underlying mechanism of this transition can be described by slow-growing clusters that remain isolated until the later stages of the process, when the addition of a small number of links leads to the rapid interconnection of these modules into a giant cluster. Our results indicate that the evolutionary-based process that shapes the topology of the H-PHN through duplication-divergence events may occur in sudden steps, similarly to what is seen in first-order phase transitions.     

Percolation analysis of stochastic models of galactic evolution

The stochastic star formation model of galactic evolution can be cast as a problem of directed percolation, the time dimension being that along which the directed bonds exist. We study various aspects of this percolation, those of general interest for the percolation phase transition and those of particular importance for the astrophysical application. Both analytical calculations and computer simulations are provided and the results compared. Among the properties are: value of the percolation threshold, critical indices, percolation probability (star density) near and away from the critical point, local density, cluster sizes, effects of rotation (for disk galaxy models) on the percolation threshold. Astrophysical consequences of some of these properties are discussed, in particular the way in which general phase transition behavior contributes to spiral arm morphology. We look at 1 (space) + 1 (time), 2 + 1 and + 1 dimensions, the 2 + 1 case being of interest for disk galaxies.     

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.     

Renormalized Field Theory of Resistor Diode Percolation

We study resistor diode percolation at the transition from the non-percolating to the directed percolating phase. We derive a field theoretic Hamiltonian which describes not only geometric aspects of directed percolation clusters but also their electric transport properties. By employing renormalization group methods we determine the average two-port resistance of critical clusters, which is governed by a resistance exponent . We calculate to two-loop order.     

Recent advances and open challenges in percolation

Percolation is the paradigm for random connectivity and has been one of the most applied statistical models. With simple geometrical rules a transition is obtained which is related to magnetic models. This transition is, in all dimensions, one of the most robust continuous transitions known. We present a very brief overview of more than 60 years of work in this area and discuss several open questions for a variety of models, including classical, explosive, invasion, bootstrap, and correlated percolation.     

Cluster Structure of Collapsing Polymers

In order to better understand the geometry of the polymer collapse transition, we study the distribution of geometric clusters made up of the nearest neighbor interactions of an interacting self-avoiding walk. We argue for this new correlated percolation problem that in two dimensions, and possibly also in three dimensions, a percolation transition takes place at a temperature lower than the collapse transition. Hence this novel transition should be governed by exponents unrelated to the -point exponents. This also implies that there is a temperature range in which the polymer has collapsed, but has no long-range cluster structure. We use Monte Carlo to study the distribution of clusters on the simple cubic and Manhattan lattices. On the Manhattan lattice, where the data are most convincing, we find that the percolation transition occurs at _p =1.461(3), while the collapse transition is known to occur exactly at =1.414.... We propose a finite-size scaling form for the cluster distribution and estimate several of the critical exponents. Regardless of the value of _p , this percolation problem sheds new light on polymer collapse.     

The phase transition in the fully frustrated XY model as a percolation problem

The fully frustrated planar rotator and fully frustrated XY models in two dimensions have two phase transitions: one of the Berezinskii–Kosterlitz–Thouless type and other in the Ising universality class. We use Monte Carlo simulation to study both models. We fix our attention in the Ising-like transition, which we show can be understood as a percolation transition. We obtain the critical temperature as well as the critical exponents of the mean cluster size, γ, and Fisher's exponent τ. The critical temperature agree very well with other calculations. We found that the critical exponents are smaller than in the pure two-dimensional percolation case. We interpret this as due to the long-range interaction between vortex and antivortex.     

Percolation on infinitely ramified fractals

We present a family of exact fractals with a wide range of fractal and fracton dimensionalities. This includes the case of the fracton dimensionality of 2, which is critical for diffusion. This is achieved by adjusting the scaling factor as well as an internal geometrical parameter of the fractal. These fractals include the cases of finite and infinite ramification characterized by a ramification exponentp. The infinite ramification makes the problem of percolation on these lattices a nontrivial one. We give numerical evidence for a percolation transition on these fractals. This transition is tudied by a real-space renormalization group technique on lattices with fractal dimensionality ¯d between 1 and 2. The critical exponents for percolation depend strongly on the geometry of the fractals.     

The Ising model and percolation on trees and tree-like graphs

We calculate the exact temperature of phase transition for the Ising model on an arbitrary infinite tree with arbitrary interaction strengths and no external field. In the same setting, we calculate the critical temperature for spin percolation. The same problems are solved for the diluted models and for more general random interaction strengths. In the case of no interaction, we generalize to percolation on certain tree-like graphs. This last calculation supports a general conjecture on the coincidence of two critical probabilities in percolation theory.Research partially supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship     

Percolation quantum phase transitions in diluted magnets

We show that the interplay of geometric criticality and quantum fluctuations leads to a novel universality class for the percolation quantum phase transition in diluted magnets. All critical exponents involving dynamical correlations are different from the classical percolation values, but in two dimensions they can nonetheless be determined exactly. We develop a complete scaling theory of this transition, and we relate it to recent experiments in La2Cu(1-p)(Zn,Mg)(p)O4. Our results are also relevant for disordered interacting boson systems.     

Resonant localized states and quantum percolation on random chains with power-law-diluted long-range couplings

We investigate the nature of one-electron eigenstates in power-law-diluted chains for which the probability of occurrence of a bond between sites separated by a distance r decays as p(r) = p/r(1+σ). Using an exact diagonalization scheme and a phenomenological finite-size scaling analysis, we determine the quantum percolation transition phase diagram in the full parameter space (p,σ). We show that the density of states displays singularities at some resonance energies associated with degenerate eigenstates localized in a pair of sites with special symmetries. This model is shown to present an intermediate phase for which there is classical percolation but no quantum percolation. Quantum percolation only takes place for σ < 0.78, a value larger than the corresponding one for the Anderson transition in long-ranged coupled chains with random diagonal disorder. The fractality of critical wavefunctions is also characterized.     

Percolation transition in an irreversible-surface reaction model

Monte Carlo simulation studies of percolation transition in a surface reaction model describing the oxidation of carbon mono-oxide on a catalytic surface are presented. The percolation transition for adsorbed oxygen atoms occurs below the poisoning transition where carbon mono-oxide completely covers the surface of the catalyst and takes place for an oxygen coverage of about 0.525 which is close to the percolation transition in an Ising lattice gas with nearest-neighbor attractive interactions. In several respects the oxygen clusters near the percolation threshold resemble those of the Ising lattice gas near its critical point.     

Dynamic transitions in Domany-Kinzel cellular automata on small-world network

We study Domany-Kinzel cellular automata on small-world network. Every link on a one dimensional chain is rewired and coupled with any node with probability p. We observe that, the introduction of long-range interactions does not remove the critical character of the model and the system still exhibits a well-defined phase transition to absorbing state. In case of directed percolation (DP), we observe a very anomalous behavior as a function of size. The system shows long lived metastable states and a jump in order parameter. This jump vanishes in thermodynamic limit and we recover second-order transition. The critical exponents are not equal to the mean-field values even for large p. However, for compact directed percolation(CDP), the critical exponents reach their mean-field values even for small p.     

Criticality of Parasitic Disease Transmission in a Diffusive Population

Through using the methods of finite-size effect and short time dynamic scaling, we study the critical behavior of parasitic disease spreading process in a diffusive population mediated by a static vector environment. Through comprehensive analysis of parasitic disease spreading we find that this model presents a dynamical phase transition from disease-free state to endemic state with a finite population density. We determine the critical population density, above which the system reaches an epidemic spreading stationary state. We also perform a scaling analysis to determine the order parameter and critical relaxation exponents. The results show that the model does not belong to the usual directed percolation universality class and is compatible with the class of directed percolation with diffusive and conserved fields.     

Localization transition of the three-dimensional lorentz model and continuum percolation

The localization transition and the critical properties of the Lorentz model in three dimensions are investigated by computer simulations. We give a coherent and quantitative explanation of the dynamics in terms of continuum percolation theory and obtain an excellent matching of the critical density and exponents. Within a dynamic scaling ansatz incorporating two divergent length scales we achieve data collapse for the mean-square displacements and identify the leading corrections to scaling. We provide evidence for a divergent non-Gaussian parameter close to the transition.