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 (121)

• Statistical Mechanics of Community Detection
• 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
• Nonequilibrium phase transition in the coevolution of networks and opinions
• 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
• Universality in the synchronization of weighted random networks
• Enhancing complex-network synchronization
• Dynamics of Social Balance on Networks
• Delays, connection topology, and synchronization of coupled chaotic maps
• Consensus formation on adaptive networks
• Synchronization is optimal in non-diagonalizable 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
• Percolation and Epidemic Thresholds in Clustered Networks
• Limited resolution in complex network community detection with Potts model approach
• Optimal Paths in Disordered Complex Networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Predicting the size and probability of epidemics in a population with heterogeneous infectiousness and susceptibility
• Maximizing Modularity is hard
• Loop series for discrete statistical models on graphs
• 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
• Analysis of Self-Organized Criticality in the Olami-Feder-Christensen model and in real earthquakes
• 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
• Coevolution of agents and networks: Opinion spreading and community disconnection
• 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
• Phenomenological Models of Socio-Economic Network Dynamics
• 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
• An efficient approach of controlling traffic congestion in scale-free networks
• Percolation transition in networks with degree-degree correlation
• 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
• Message passing for vertex covers
• Social Structure and Opinion Formation
• The role of clustering and gridlike ordering in epidemic spreading
• Routes to thermodynamic limit on scale-free networks
• Congestion-gradient driven transport on complex networks
• Size of Outbreaks Near the Epidemic Threshold
• Failure and avalanches in complex networks
• 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
• Topological phase transitions of random networks
• Stationary and dynamical properties of a zero range process on scale-free networks
• Condensation in a zero range process on weighted scale-free networks
• Magnetization reversal in spin patterns with complex geometry
• Testing the Collective Properties of Small-World Networks through Roughness Scaling
• Limited path percolation in complex networks
• Bounding network spectra for network design
• Spreading dynamics on small-world networks with connectivity fluctuations and correlations
• Finite-size scaling of synchronized oscillation on complex networks
• Olami-Feder-Christensen Model on different Networks
• The critical point of k-clique percolation in the Erdos-Renyi graph
• Search in Complex Networks : a New Method of Naming
• Zero temperature Glauber dynamics on complex 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
• Criticality on networks with topology-dependent interactions
• 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
• Reply to the Comment on the paper "Non-mean-field behavior of the contact process on scale-free networks"
• Phase transitions in Ising model on a Euclidean network
• Interfaces and the edge percolation map of random directed 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
• Random field Ising model on networks with inhomogeneous connections
• Effects of decision-making on the transport costs across complex networks
• Ising spin glass models versus Ising models: an effective mapping at high temperature I. General result
• Non-converging hysteretic cycles in random spin networks
• Graph Partitioning Induced Phase Transitions
• Avalanches in complex spin networks
• Scale-free networks with a large- to hypersmall-world transition
• Statics and dynamics of the Lebwohl-Lasher model in the Bethe approximation
• Ising spin glass models versus Ising models: an effective mapping at high temperature II. Applications to graphs and networks
• Statistical mechanics of combinatorial auctions
• 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