Critical phenomena in complex networks

Abstract

The combination of the compactness of networks, featuring small diameters, and their complex architectures results in a variety of critical effects dramatically different from those in cooperative systems on lattices. In the last few years, researchers have made important steps toward understanding the qualitatively new critical phenomena in complex networks. We review the results, concepts, and methods of this rapidly developing field. Here we mostly consider two closely related classes of these critical phenomena, namely structural phase transitions in the network architectures and transitions in cooperative models on networks as substrates. We also discuss systems where a network and interacting agents on it influence each other. We overview a wide range of critical phenomena in equilibrium and growing networks including the birth of the giant connected component, percolation, k-core percolation, phenomena near epidemic thresholds, condensation transitions, critical phenomena in spin models placed on networks, synchronization, and self-organized criticality effects in interacting systems on networks. We also discuss strong finite size effects in these systems and highlight open problems and perspectives.

Review article, 79 pages, 43 figures, 1 table, 508 references, extended

References in corpus (99)

• Efficient Immunization Strategies for Computer Networks and Populations
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Adaptive Coevolutionary Networks: A Review
• Cascade control and defense in complex networks
• New Model of Internet Topology Using k-shell Decomposition
• Modeling the Worldwide Spread of Pandemic Influenza: Baseline Case and Containment Interventions
• Co-evolution of strategy and structure in complex networks with dynamical linking
• The Rich-Club Phenomenon In The Internet Topology
• Clique percolation in random networks
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Network Synchronization, Diffusion, and the Paradox of Heterogeneity
• Paths to Synchronization on Complex Networks
• How to calculate the fractal dimension of a complex network: the box covering algorithm
• Enhancing complex-network synchronization
• Dynamics of Social Balance on Networks
• Delays, connection topology, and synchronization of coupled chaotic maps
• Consensus formation on adaptive networks
• Sandpile on Scale-Free Networks
• Dynamics of jamming transitions in complex networks
• Clustering of solutions in the random satisfiability problem
• Scaling theory of transport in complex networks
• Conservation laws for the voter model in complex networks
• Limited resolution in complex network community detection with Potts model approach
• Optimal Paths in Disordered Complex Networks
• Predicting the size and probability of epidemics in a population with heterogeneous infectiousness and susceptibility
• Maximizing Modularity is hard
• Synchronization processes in complex networks
• Clustering in complex networks. I. General formalism
• Self-similar disk packings as model spatial scale-free networks
• Maximum Performance at Minimum Cost in Network Synchronization
• Improving immunization strategies
• Finite-size scaling in complex networks
• On the scaling of the chemical distance in long-range percolation models
• Synchronization transition in scale-free networks: Clusters of synchrony
• On network bipartivity
• Clustering in complex networks. II. Percolation properties
• Performance of networks of artificial neurons: The role of clustering
• Local structure of directed networks
• Non-equilibrium phase transition in negotiation dynamics
• Synchronizability determined by coupling strengths and topology on Complex Networks
• Entrainment transition in populations of random frequency oscillators
• Component sizes in networks with arbitrary degree distributions
• Percolation in Hierarchical Scale-Free Nets
• Scale-free networks with an exponent less than two
• An adaptive routing strategy for packet delivery in complex networks
• Sandpile avalanche dynamics on scale-free networks
• Evolution of scale-free random graphs: Potts model formulation
• Percolation transition in networks with degree-degree correlation
• An efficient approach of controlling traffic congestion in scale-free networks
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Optimal Paths in Complex Networks with Correlated Weights: The World-wide Airport Network
• Social Structure and Opinion Formation
• The role of clustering and gridlike ordering in epidemic spreading
• Routes to thermodynamic limit on scale-free networks
• Size of Outbreaks Near the Epidemic Threshold
• BKT-like transition in the Potts model on an inhomogeneous annealed network
• Localization Transition of Biased Random Walks on Random Networks
• Does dynamics reflect topology in directed networks?
• Exact Solution of Ising Model on a Small-World Network
• Condensation in a zero range process on weighted scale-free networks
• Stationary and dynamical properties of a zero range process on scale-free networks
• Topological phase transitions of random networks
• Magnetization reversal in spin patterns with complex geometry
• Testing the Collective Properties of Small-World Networks through Roughness Scaling
• Bounding network spectra for network design
• Limited path percolation in complex networks
• Finite-size scaling of synchronized oscillation on complex networks
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Olami-Feder-Christensen Model on different Networks
• Loop Calculus Helps to Improve Belief Propagation and Linear Programming Decodings of Low-Density-Parity-Check Codes
• Comment on "Localization Transition of Biased Random Walks on Random Networks"
• Condensation in zero-range processes on inhomogeneous networks
• Navigating Networks with Limited Information
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Excitable Scale Free Networks
• Transport and Percolation Theory in Weighted Networks
• Numerical evaluation of the upper critical dimension of percolation in scale-free networks
• Phase transitions in Ising model on a Euclidean network
• Interfaces and the edge percolation map of random directed networks
• Reply to the Comment on the paper "Non-mean-field behavior of the contact process on scale-free networks"
• Is small-world network disordered?
• Transition from small to large world in growing networks
• Finite size effects in Barabasi-Albert growing networks
• Self-organization of structures and networks from merging and small-scale fluctuations
• On Cavity Approximations for Graphical Models
• Coevolution of agents and networks in an epidemiological model
• Balls-in-boxes condensation on networks
• Non-converging hysteretic cycles in random spin networks
• Graph Partitioning Induced Phase Transitions
• Avalanches in complex spin networks
• Ising spin glass models versus Ising models: an effective mapping at high temperature I. General result
• Ising spin glass models versus Ising models: an effective mapping at high temperature II. Applications to graphs and networks
• Diffusion-Limited One-Species Reactions in the Bethe Lattice
• Free zero-range processes on networks
• Maximal entropy random networks with given degree distribution
• Apollonian networks
• Universality Class of Bak-Sneppen Model on Scale-Free Network
• Socio-economical dynamics as a solvable spin system on co-evolving networks

Cited by in corpus (49)

• Synchronization in complex networks
• Extracting the multiscale backbone of complex weighted networks
• Community detection in networks with positive and negative links
• The entropy of network ensembles
• Traffic-driven Epidemic Spreading in Finite-size Scale-Free Networks
• Explosive percolation in scale-free networks
• Percolation on correlated networks
• Exact solution for mean first-passage time on a pseudofractal scale-free web
• Langevin approach for the dynamics of the contact process on annealed scale-free networks
• Bond percolation on a class of clustered random networks
• Standard random walks and trapping on the Koch network with scale-free behavior and small-world effect
• Spectral tripartitioning of networks
• Random walks on complex trees
• Random walks on the Apollonian network with a single trap
• Organization of modular networks
• Routes to thermodynamic limit on scale-free networks
• Small-World Bonds and Patchy Percolation on the Hanoi Network
• Bosonic reaction-diffusion processes on scale-free networks
• Maximizing Influence Propagation in Networks with Community Structure
• Percolation on hyperbolic lattices
• Ising model on the Apollonian network with node dependent interactions
• Monte-Carlo simulation study of the two-stage percolation transition in enhanced binary trees
• Anomalous behavior of trapping on a fractal scale-free network
• Recursive solutions for Laplacian spectra and eigenvectors of a class of growing treelike networks
• Phase diagram of an Ising model with competitive interactions on a Husimi tree and its disordered counterpart
• Different thresholds of bond percolation in scale-free networks with identical degree sequence
• Phase of Ising spins on modular networks analogous to social polarization
• Energy-landscape network approach to the glass transition
• Glass transition and random walks on complex energy landscapes
• Growing community networks with local events
• Transition from small to large world in growing networks
• Communication and correlation among communities
• Dynamics of condensation in growing complex networks
• Percolation transition in correlated hypergraphs
• Effective field theory for models defined over small-world networks. First and second order phase transitions
• Antiferromagnetic Ising model in scale-free networks
• Nested Subgraphs of Complex Networks
• Structural and spectral properties of a family of deterministic recursive trees: Rigorous solutions
• Percolation transition and distribution of connected components in generalized random network ensembles
• Contact graphs of disk packings as a model of spatial planar networks
• Zero-temperature Glauber dynamics on small-world networks
• Structural phase transition in evolving networks
• Approaching the thermodynamic limit in equilibrated scale-free networks
• Around the gap between sociophysics and sociology
• Viable flux distribution in metabolic networks
• Communities in networks - a continuous approach
• Magnetism of frustrated regular networks
• Small-world of communities: communication and correlation of the meta-network
• Frustration and collectivity in spatial networks