Critical phenomena in complex networks

S. N. Dorogovtsev; A. V. Goltsev; J. F. F. Mendes

Source-linked AI summary

Critical phenomena in complex networks

S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes

arXiv:0705.0010v6Apr 30, 2007cond-mat.stat-mechcs.NImath-phphysics.soc-ph

TL;DR

Critical phenomena in complex networks differ from lattice systems, motivating a synthesis of their diverse structural and cooperative transitions. The paper reviews these phenomena and presents a unified framework for explaining them.

Problem
The model dependence of network degree-distribution cutoffs and the unknown effects of loops limit a general understanding of critical phenomena in complex networks.
Method
The paper synthesizes critical effects across network models and cooperative systems using a unified theoretical framework.
Results
The review identifies diverse critical phenomena in networks that greatly differ from those in lattices and shows they can be explained within one framework.
Takeaways & Limitations
A unified perspective organizes critical effects across structural transitions and cooperative models on complex networks.
Takeaways & Limitations
It remains unknown when and how loops change cooperative phenomena in complex networks.

Abstract

from arXiv · show

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.

II. MODELS OF COMPLEX NETWORKS … 1. Evolution of the giant connected component

The paper introduces complex-network architectures and shows how their geometry, degree distributions, correlations, and evolution shape critical structural transitions. It then derives the giant-component transition in uncorrelated networks, including its criterion, classical threshold, and critical susceptibility.

A. Structural characteristics of networks: Complex networks are characterized through adjacency matrices, clustering, loops, distances, betweenness, and the giant connected component.The giant component is the mutually reachable set containing a finite fraction of vertices in an infinite network.
B. Cayley tree versus Bethe lattice: Cayley trees have boundary dead ends that affect interacting systems, whereas Bethe lattices lack boundaries and are approached by random regular graphs.Both regular graphs are small worlds when vertex degree exceeds 2.
C. Equilibrium random trees versus growing ones: Equilibrium random trees have dh = 2 and ℓ(N) ∼N 1/2, while growing trees are small worlds with ℓ∼ln N, even when degree distributions are identical.For equilibrium scale-free trees, dh = 2 when γ ≥3 and dh = (γ −1)/(γ −2) > 2 when 2 < γ < 3.
D. Classical random graphs; E. Uncorrelated networks with arbitrary degree distributions; 1. Configuration model: Classical random graphs are maximally random under a fixed mean degree and have Poissonian degree distributions, while uncorrelated-network architecture is determined by its degree distribution.The configuration model fixes a degree sequence by randomly pairing stubs and has ℓ(N) ∼= ln N/ ln(z2/z1), with asymptotically vanishing relative distance width.
1. Configuration model; F. Equilibrium correlated networks: In the configuration model, z2 = ⟨q2⟩−⟨q⟩ and zℓ= z1(z2/z1)ℓ−1 determine branching and neighborhood growth, while correlated models constrain P(q, q′).Correlated networks can also be constructed with hidden variables whose pairwise connection probabilities depend on assigned hidden values.
4. Cutoffs of degree distributions: Finite heavy-tailed networks require model-dependent degree cutoffs: qcut(N) ∼N 1/2 for γ ≥3, while 2 < γ < 3 yields qcut(N) ∼ N 1/(γ−1) with multiple connections and qcut(N) ∼ N 1/2 without them.For 1<γ<2, qcut(N, 1<γ<2) ∼N 1/γ and ⟨q⟩∼N (2−γ)/γ; growing networks with γ>2 have qcut(N, γ>2) ∼ N 1/(γ−1).
G. Loops in networks; H. Evolving networks; 1. Preferential attachment; 2. Deterministic graphs; I. Small-world networks: Sparse equilibrium networks are locally tree-like at short scales but contain many long loops, with exponentially many long loops and especially many loops when 2 < γ < 3.Evolving networks inevitably have correlations; random recursive trees have exponential degree distributions, whereas preferential attachment generates heavy-tailed distributions.

2. Percolation on uncorrelated networks · 3. Statistics of finite connected components · 4. Finite size effects

Percolation on uncorrelated networks exhibits threshold-free or anomalous critical behavior for heavy-tailed degree distributions, while finite components and finite-size networks show distinct scaling laws and strong size effects.

2. Percolation on uncorrelated networks: The giant connected component persists whenever the percolation condition holds, with pc = 1/⟨q⟩ for classical random graphs and pc = 1/(q −1) for random regular graphs.If the degree distribution’s second moment diverges, eliminating the giant component in an infinite uncorrelated network is practically impossible.
2. Percolation on uncorrelated networks: For scale-free networks, S ∝p−pc when γ > 4, but S ∝(p −pc)1/(γ−3) when 3 < γ < 4.These anomalous exponents arise from the fat-tailed degree distribution within an essentially mean-field theory.
3. Statistics of finite connected components: For 3 < γ < 4, every largest finite component scales as s(i≥1)(N) ∼N (γ−2)/(γ−1) within the scaling window.For γ > 4, the classical random-graph formulas apply; outside the scaling window, the classical results hold.
3. Statistics of finite connected components: For finite components, df(γ ≥4) = 4 and df(3 < γ < 4) = 2γ −2, while du(γ ≥4) = 6 and du(3 < γ < 4) = 2γ −1.For γ > 3, the susceptibility exponent is ˜γ = 1 throughout the region.
3. Statistics of finite connected components: Without a giant component and for γ > 3, finite-component sizes follow P(s) ∼s−(γ−1), while the largest component contains ∼N 1/(γ−1) vertices.The largest-component size coincides with the finite-network cutoff kcut(N).
3. Statistics of finite connected components: For 2 < γ < 3, scaling relations fail because the giant component disappears only at p = 0; nevertheless, ⟨s⟩∝p, τ = 3, and σ = 3 −γ.The resulting values imply qcut ∼N 1/2.
4. Finite size effects: Finite-size networks can exhibit noticeable percolation thresholds even when pc(N →∞) →0, effectively breaking infinite-network ultraresilience against random failures.A poor-man’s estimate substitutes the finite network’s degree distribution into the infinite-network threshold relation with qcut ∼N 1/2.

5. k-core architecture of networks · C. Percolation on degree-degree correlated networks

The paper characterizes k-cores through pruning and tree-ansatz equations, revealing hybrid transitions and corona divergences, while degree-degree correlations generalize percolation through conditional probabilities and an eigenvalue criterion. Scale-free networks support extensive k-core sequences, whereas correlated giant-component formation remains continuous and ultra-resilience depends on a divergent second degree moment rather than correlations.

5. k-core architecture of networks: A k-core is the largest subgraph whose vertices each have at least k neighbors within it, obtainable by iteratively pruning lower-degree vertices.For a 3-core, vertices 1, 2, and 4 are removed first, followed by vertex 3 after its degree falls to 1.
5. k-core architecture of networks: For k≥3, tree-like networks have only giant k-cores, and the tree ansatz describes their organization despite loops in the giant core.The configuration model’s k-core architecture is asymptotically described by this ansatz.
5. k-core architecture of networks: For k≥3, the k-core order parameter and size jump at the critical point while exhibiting a square-root singularity, producing a hybrid phase transition.This differs from an ordinary first- or second-order transition by combining a discontinuous jump with critical singularity.
5. k-core architecture of networks: At k = 2, the k-core transition coincides with giant-component birth and is continuous, with M2 ∝ (p −pc)^2 when the degree distribution decays rapidly.The 2-core is obtained by pruning dangling branches from the giant connected component.
5. k-core architecture of networks: The corona, consisting of k-core vertices with exactly k core neighbors, develops diverging cluster sizes and intervertex distances at the k-core threshold.Its mean cluster size Ncrn acts as a susceptibility, with singularity exponent 1/2 rather than the standard mean-field exponent ˜γ = 1.
5. k-core architecture of networks: In scale-free networks with 2 < γ < 3, an infinite sequence of k-cores occurs, while finite size imposes a maximum highest-core index kh.Uncorrelated estimates of kh were several (3) times smaller than observed values, whereas incorporating high clustering produced more realistic estimates.
C. Percolation on degree-degree correlated networks: For degree-degree correlated networks, conditional probabilities P(q′|q) define locally tree-like component equations whose solutions determine the giant-component size S.The resulting S(p) depends significantly on whether correlations are assortative or disassortative.
C. Percolation on degree-degree correlated networks: Correlated-network percolation remains continuous, and a giant component exists when the largest eigenvalue of Cqq′ = −δqq′ + p(q′ −1)P(q′|q) is positive.The threshold occurs when this largest eigenvalue equals zero, reducing to the uncorrelated criterion without correlations.

D. The role of clustering · E. Giant component in directed networks · F. Giant component in growing networks

Clustering changes percolation resilience depending on degree heterogeneity, while directed networks have multiple giant-component transitions shaped by same-vertex degree correlations. Growing networks exhibit an infinite-order, BKT-like giant-component transition with critical-phase behavior unlike equilibrium networks.

D. The role of clustering: Highly clustered networks are difficult to analyze, but tree-ansatz-based constructions characterize percolation using degree-dependent clustering C(q).The construction assumes triangles have no joint edges and neglects long loops.
D. The role of clustering: Finite second-degree moments make weak clustering reduce resilience to random edge damage, whereas strong clustering shifts the percolation threshold oppositely but makes small damage diminish the giant component.Damage is measured by Q = 1−p, the fraction of removed edges.
D. The role of clustering: When the second moment of the degree distribution diverges, neither weak nor strong clustering destroys the giant connected component in an infinite network.This contrasts with the finite-second-moment case, where clustering affects percolation resilience.
E. Giant component in directed networks: Directed networks can contain several specifically interconnected giant subcomponents with different birth points, whose locations and sizes follow from the joint in- and out-degree distribution P(qi, qo).The resulting organization is more complex than in undirected networks.
E. Giant component in directed networks: Critical points and exponents for directed giant-component transitions depend essentially on correlations between vertices’ in- and out-degrees.In- and out-degrees across different vertices may be uncorrelated while arbitrary correlations remain within each vertex.
F. Giant component in growing networks: Growing-network inhomogeneity, caused by vertex-age differences and denser older regions, can produce an unexpected giant-component transition controlled by the edge-inflow rate b.The model adds new vertices at unit rate and randomly interconnects vertex pairs with edge rate b.
F. Giant component in growing networks: An infinite-order phase transition occurs because the giant-component singularity has all derivatives vanishing at the critical point.The size S would instead be proportional to b−bc in an equilibrium network with the same degree distribution.
F. Giant component in growing networks: In growing networks, finite-component sizes decay by a power law throughout the no-giant-component phase and rapidly after giant-component birth, producing a BKT-like critical phase.The transition has the opposite ordering of the power-law and rapidly decreasing phases compared with canonical BKT transitions, and similar behavior appears across several growing models and some network spin or percolation systems.

G. Percolation on small-world networks

Percolation on small-world networks can be analyzed using a tree ansatz despite lattice loops, revealing crossover behavior and critical exponents that approach classical random-graph values. Scaling functions describe the crossover between lattice and small-world regimes through characteristic lengths and finite-size effects.

Component statistics: The absence of finite loops containing shortcuts permits the usual tree ansatz for connected-component statistics in small-world bond percolation.Finite loops consist only of lattice edges in the infinite-network limit.
Threshold condition: At the percolation threshold, the mean density of shortcut ends equals the mean size of the lattice component containing a vertex: 2dφpc = 1/⟨n0⟩(pc).This expresses the condition that each retained shortcut-connected component has one shortcut end on average.
Lattice regime: For two-dimensional small-world bond percolation, the lattice baseline is pc0 = 1/2 with ˜γ = 43/18 = 2.39 . . ..These values characterize the lattice connected-component scaling entering the small-shortcut analysis.
Critical exponents: The connected-component critical exponent equals 1, and the other percolation exponents coincide with classical random-graph values.The same conclusion is stated for cooperative models on small-world networks near criticality.
Crossover scaling: Crossover and finite-size effects are described by scaling functions involving L, ξsw ≡ 1/(2dφp)1/d, and the lattice correlation length ξl.For an arbitrary quantity, the scaling form is X(L) = L^x f(ξsw/L, ξl/L).

H. k-clique percolation

k-clique percolation applies connectivity concepts to overlapping fully connected subgraphs, forming a k-clique graph whose giant component emerges at a threshold. Although the giant component in the k-clique graph grows conventionally near criticality, its counterpart in the original graph appears abruptly and becomes nearly extensive above threshold.

Definition: A k-clique is a fully connected subgraph of k vertices, and two k-cliques are adjacent when they share k −1 vertices.For k=3, this requires triangles to share an edge.
k-clique graph: The k-clique graph represents k-cliques as vertices and their adjacency connections as edges, with approximately N kpk(k−1)/2/k! k-cliques and mean degree ⟨q⟩∼= Nkpk−1.Its degree distribution is Poissonian, and its mean degree may be much less than the Gilbert model’s Np.
Threshold: Applying the Molloy-Reed criterion to the k-clique graph determines the birth point of its giant connected component.Because sparse classical random graphs contain few (k≥3)-cliques, this percolation implies dense networks with a divergent mean degree.
Critical behavior: Near pc(k), the k-clique graph’s giant component has relative size proportional to [p −pc(k)], whereas the corresponding component in the original graph emerges abruptly.For any p above pc(k), the original-graph component contains almost all vertices.

I. e-core · IV. CONDENSATION TRANSITION

Leaf removal reveals a second-order e-core transition at mean degree e, with critical slowing down and links to optimization and spectral localization. Complex networks can also exhibit condensation, aggregating finite fractions of motifs into ultra-compact subgraphs.

I. e-core: Leaf removal algorithms recursively eliminate dead-end vertices, supporting matching and minimal vertex-cover procedures.Here, a leaf includes a dead-end vertex, its sole nearest neighbor, and their connecting edge.
I. e-core: At ⟨q⟩= e, the network undergoes a second-order transition in which the e-core is born.Below e, only O(N) isolated vertices and components totaling o(N) vertices remain; above e, a finite fraction Se occupies the e-core.
I. e-core: At birth, the e-core’s mean vertex degree is exactly 2, corresponding to a tree graph.The critical region also includes isolated vertices and negligible finite components, as described in the surrounding transition behavior.
I. e-core: The e-core transition is singular, unlike the analytic birth of the usual giant connected component, while isolated vertices change discontinuously only in the second derivative.This distinguishes the e-core’s critical behavior from that of the usual giant component.
I. e-core: Leaf removal exhibits critical slowing down as ⟨q⟩ approaches the e-core critical point.The slowing is described as a direct analog of critical slowing down in continuous phase transitions.
I. e-core: The same threshold ⟨q⟩= e separates rapidly solvable regimes from very long algorithmic runtimes in several combinatorial optimization problems.This applies to both polynomial-time P problems and nondeterministic polynomial-time NP problems.
I. e-core: Leaf removal preserves adjacency-matrix zero-eigenvalue degeneracy, linking the e-core to spectral localization and delocalization phenomena.The adjacency spectrum is relevant to quantum-particle localization on graphs.
IV. CONDENSATION TRANSITION: Condensation aggregates a finite fraction of network motifs, including edges and triangles, into ultra-compact subgraphs with diameters much smaller than the network’s diameter.The section considers various types of this condensation.

A. Condensation of edges in equilibrium networks … 2. Spin correlations

The review surveys condensation transitions in equilibrium and growing networks, epidemic thresholds and outbreak behavior, and Ising criticality on complex networks. It emphasizes condensate structure, finite-size effects, and nonstandard spin correlations on treelike graphs.

A. Condensation of edges in equilibrium networks: Equilibrium edge condensation occurs when the mean degree exceeds qc, producing a non-exponential degree distribution and a finite edge condensate.At ⟨q⟩ = qc, P(q) ∼ q^-γ is scale-free; above qc, condensation occurs.
A. Condensation of edges in equilibrium networks: Without multiple connections, condensed edges form a highly interconnected core of Nh vertices, with Nh scaling between N^1/2 and N^2/3.The core contains ∼N edges, and its mean degree scales as ∼N/Nh.
B. Condensation of triangles in equilibrium nets: Triangle-favoring equilibrium networks develop clique-like condensation, but a homogeneous metastable state is separated from it by a barrier diverging with N.For sufficiently small G, relaxation from a homogeneous configuration practically cannot reach condensation in large networks.
C. Condensation of edges in growing networks: Fitness-driven growing networks condense when g exceeds gc, attaching a finite edge fraction d ∝ (g − gc) to the fittest vertex.The condensed phase also has γ = 1 + g > γ0 and power-law relaxation dj(t) − d ∼ t^−(g−gc)/g.
A. The SIS, SIR, SI, and SIRS models: Epidemic models distinguish SIS, SIR, and SI dynamics, with infections transmitted between nearest-neighbor individuals and recovery or immunity determining subsequent evolution.The SI model has no epidemic threshold, while SIS and SIR thresholds arise by linearizing their dynamical equations.
B. Epidemic thresholds and prevalence: In uncorrelated networks with diverging ⟨q^2⟩, epidemic thresholds approach zero in the infinite-size limit but remain finite for finite networks.SIR final states are practically equivalent to bond percolation, transferring finite-size relations and giant-component estimates to epidemic prevalence.
B. Epidemic thresholds and prevalence: Near the SIR threshold, maximum and mean outbreaks scale as N^2/3 and N^1/3, while SIS counterparts scale as N and N^1/2.For γ = 3 scale-free networks, prevalence has an essential singularity proportional to exp[−g(⟨q⟩)/λ].
VI. THE ISING MODEL ON NETWORKS; 1. Bethe approach; 2. Belief-propagation algorithm; 3. Annealed network approach; 2. Spin correlations: Ising criticality on complex networks can depart from lattice mean-field behavior, while treelike spin correlations retain a one-dimensional character.On growing Barabási-Albert networks, Tc(N) ∼ ln N; on treelike graphs, even-spin correlations factor into pair correlations and odd-spin correlations vanish at zero field.

3. Magnetic properties · C. The ferromagnetic Ising model on uncorrelated networks · 1. Derivation of thermodynamic quantities

The ferromagnetic Ising model exhibits topology-dependent critical behavior: trees can show no zero-field transition or an infinite-order field-driven transition, while network heterogeneity raises the critical temperature and weakens the transition. On uncorrelated networks, thermodynamics follows from a self-consistent message distribution under the Bethe-Peierls framework.

3. Magnetic properties: Exact free energy on an arbitrary tree is analytic in T, so no phase transition occurs as N →∞ and magnetization remains zero except at T = 0.This contrasts with a regular Bethe lattice.
3. Magnetic properties: A regular Cayley tree with branching parameter B = q −1 ≥2 develops a field-dependent nonanalyticity below the critical temperature TBP.The transition appears only in the magnetic-field dependence of the free energy.
3. Magnetic properties: The Cayley-tree transition is of infinite order: κ = ln B/ ln[Bt] increases smoothly from 1 to ∞ as temperature rises from 0 to TBP, while all H-derivatives remain finite at TBP.Here t ≡ tanh βJ, and F(T, H) is continuous at T = TBP.
3. Magnetic properties: At T = T1 < TBP, the correlation volume of a boundary spin and the zero-field susceptibility diverge; only below T1 do long-ranged correlations span the whole system.The Cayley-tree structure therefore produces distinct critical temperatures for magnetic response and system-wide correlations.
3. Magnetic properties: Cayley trees support metastable domain states stable against single-spin flips, with reversal barriers proportional to the logarithm of domain size and consequently very slow relaxation.These metastable states arise from the specific Cayley-tree structure and do not exist on a Bethe lattice.
C. The ferromagnetic Ising model on uncorrelated networks: Increasing network heterogeneity makes the ferromagnetic phase transition less sharp while simultaneously increasing the critical temperature.The section also considers the resulting spin correlations and finite-size effects.
1. Derivation of thermodynamic quantities: On uncorrelated random networks, the Bethe-Peierls recursion method and replica trick derive thermodynamics through a self-consistent distribution Ψ(h) of random spin messages.The message distribution accounts for intrinsic network heterogeneity; self-averageness equates graph averages with statistical-ensemble averages as N →∞.

2. Phase transition … 1. The Ising spin glass

The paper reviews Ising critical behavior on complex networks, where degree heterogeneity, topology, and interaction structure produce distinct transitions, correlations, and universality classes. Spin-glass behavior additionally depends on frustration, branching, coupling distributions, and network degree exponents.

2. Phase transition: In uncorrelated random networks, a nontrivial ferromagnetic solution appears below Tc, while susceptibility remains universal with exponent ˜γ = 1 for γ > 3.For 2 < γ ≤ 3, susceptibility has paramagnetic temperature dependence χ ∝ 1/T even in the ordered state.
4. Ferromagnetic correlations: Ferromagnetic correlations have finite correlation length at every temperature on uncorrelated random networks, so correlation volume rather than ξ characterizes critical fluctuations.The correlation volume diverges as ln N at continuous transitions, with criticality determined by B tanh βcJ = 1.
4. Ferromagnetic correlations: Hubs and rich-club clusters generate larger, increasingly heterogeneous correlation volumes in scale-free networks, while for 2 < γ < 3 only nearest-neighbor pair correlations survive as N →∞.The hub-centered correlated region grows as temperature decreases and absorbs smaller correlated clusters.
5. Degree-dependent interactions: Topology-dependent couplings Jij = Jz2µ(qiqj)−µ map a scale-free network with exponent γ to an equivalent constant-coupling model with γ′ = (γ−µ)/(1−µ).Varying µ over [2 − γ, 1] spans the universality classes represented in Table I.
D. The Ising model on small-world networks: Small-world Ising models show ordinary mean-field behavior near Tc because shortcuts create effectively locally tree-like structures, while thermodynamics far from criticality resembles the substrate lattice.The critical-temperature shift obeys Tc(p) − Tc(0) ∼ p1/˜γ.
1. The Ising spin glass: Spin-glass analysis relies on replica and cavity methods, with replica-symmetry breaking needed to describe many pure states and avoid unphysical replica-symmetric results.The spin-glass state is associated with frustrations and nonzero local magnetic moments emerging below a critical temperature.
1. The Ising spin glass: On random networks, spin-glass and ferromagnetic transitions are governed by susceptibility divergences; asymmetric couplings can place Tc above TSG, with equality at a multicritical point.Coupling distributions can also produce non-magnetic spin-glass, mixed, or ferromagnetic states, while scale-free networks with 3 < γ < 4 alter spin-glass critical behavior.

2. The antiferromagnetic Ising model and MAX-CUT problem

On complex networks, the antiferromagnetic Ising ground state is frustrated by odd loops and is equivalent to solving MAX-CUT. Random uncorrelated networks have nearly half their edges frustrated, while the model may exhibit an antiferromagnetic-to-spin-glass transition.

Ground-state frustration: Odd loops frustrate antiferromagnetic ordering, raising the random-graph ground-state energy above the bipartite value −JL.Bipartite graphs are 2-colorable and attain E0 = −JL, whereas giant-component random networks generally contain numerous odd loops.
Ground-state frustration: The antiferromagnetic ground-state problem maps to MAX-CUT, an NP-complete optimization problem maximizing edges between two vertex sets.Assigning opposite spins to the two sets makes the maximum cut correspond to the minimum AF Ising energy.
Random-network MAX-CUT: Almost half of the edges are frustrated in arbitrary uncorrelated random networks, extending the result beyond classical random graphs.The frustrated-edge fraction is given as (L − Kc)/L = 1/2 −2A/√z1.
Phase behavior: At (z2/z1) tanh βJ = 1, the AF model on an uncorrelated random network may transition from an antiferromagnetic state to a spin-glass state as temperature decreases.This transition is associated with the critical temperature TBP, and the model’s pairwise spin correlations are non-trivial.
Network bipartivity: The ground-state fraction of opposite-spin edges provides a measure of network bipartivity and is equivalent to the graph’s maximum-cut fraction.A larger fraction indicates a network closer to bipartite structure.

3. Antiferromagnet in a magnetic field, the hard-core gas model, and vertex covers … G. The Ising model on growing networks

The paper connects vertex covers, hard-core gases, and antiferromagnetic Ising models on random graphs, then examines random-field criticality, hysteresis, and Ising models on growing networks. These systems exhibit topology- and degree-distribution-dependent phase transitions, degeneracies, and strong hysteresis effects.

3. Antiferromagnet in a magnetic field, the hard-core gas model, and vertex covers: Vertex covers undergo a threshold transition at x = xc: below xcN covers are absent with high probability, whereas above xcN exponentially many covers appear.The threshold satisfies Ξ(xc) = 0, with xc(z1) ≈1 −2 ln z1/z1 + O(ln ln z1) for z1 ≫1.
3. Antiferromagnet in a magnetic field, the hard-core gas model, and vertex covers: On scale-free networks, increasing assortative degree correlations raises vertex-cover computational complexity, and correlations beyond a critical threshold produce many nontrivial covers.For the antiferromagnetic Ising mapping, the zero-temperature state is paramagnetic for 0 < z1 < 1 and ferromagnetic for 1 < z1 < e.
3. Antiferromagnet in a magnetic field, the hard-core gas model, and vertex covers: The hard-core gas ground state occupies a maximum independent set, contains (1−xc)N particles, has E0 = 0, and is equivalent to minimum vertex cover.The antiferromagnetic model maps onto this hard-core representation, with spins S = +1 on the maximum independent set and S = −1 on the minimum vertex cover.
1. Phase diagram: For the fully connected random-field model, Gaussian disorder gives a second-order para- to ferromagnetic transition, while sufficiently strong fields suppress it at σ > σc = J[2/π]1/2.With bimodal disorder, the phase diagram contains a tricritical point separating second- and first-order transition lines.
2. Hysteresis on a fully connected graph: At T = 0, fully connected hysteresis disappears for σ > σc = J[2/π]1/2, and near (σc, Hc(σc)) magnetization follows mean-field exponents β = 1/2 and δ = 3.For σ < σc, the critical field Hc(σ) is non-zero.
3. Hysteresis on a complex network: On random regular networks, hysteresis persists without a magnetization jump for σ > σc, unlike the fully connected graph, while Hc is independent of q > 3.The critical field depends on the degree-distribution exponent γ only when 2 < γ < 4, and topology strongly influences hysteresis loops.
4. The random-field model at T = 0: On scale-free networks, concave random-field distributions yield β(γ > 5) = 1/2 and β(3 < γ ⩽5) = 1/(γ −3), whereas convex distributions produce first-order transitions for all γ > 3.For 2 < γ ⩽3, the model remains ferromagnetic for arbitrary disorder strength and distribution.
G. The Ising model on growing networks: For growing networks, the analysis assumes the spin system reaches equilibrium much faster than the network changes, so the network is grown first and the Ising model is then placed on it.This is the stated adiabatic approximation for studying the Ising model on an infinite growing network.

1. Deterministic graphs with BKT-like transitions … A. Solution for uncorrelated networks

Deterministic, strongly inhomogeneous networks can exhibit widespread BKT-like criticality across Ising and Potts models, while growing random networks remain analytically unresolved. For uncorrelated configuration-model networks, the Potts critical temperature simultaneously encodes percolation, Ising criticality, or hysteresis boundaries depending on the number of states.

1. Deterministic graphs with BKT-like transitions: Deterministic graphs can make analysis tractable while producing behavior qualitatively similar to models on random networks, including scale-free Ising features.The Apollonian network exhibits features typical of Ising models on random scale-free networks with γ < 3.
1. Deterministic graphs with BKT-like transitions: The Ising model on an asymmetric annealed network exhibits BKT-like singularities and an inhomogeneous magnetization profile centered on the oldest vertex.The exact mean-field solution gives m(i) ∼= 1 − const(i/t)2/T, with m(i = 0) = 1 outside the normal zero-field phase.
1. Deterministic graphs with BKT-like transitions: The response to a local magnetic field has a power-law distribution throughout the normal phase, paralleling connected-component size distributions at BKT-like transitions.The same power-law decay applies to the distribution of correlations ∂m(i)/∂Hj|H=0.
1. Deterministic graphs with BKT-like transitions: For power-law interaction heterogeneity ∝j−α, BKT criticality occurs only at α = 1; α > 1 eliminates finite-temperature ordering, whereas 0 < α < 1 yields a second-order transition.Another deterministic graph also displays a BKT-like transition, indicating that this singularity occurs broadly in evolving networks with large-scale inhomogeneity.
1. Deterministic graphs with BKT-like transitions: The q-state Potts model on this network has Ising-like results for all q ≥1, transforming both first- and second-order transitions into BKT-like ones.Here q = 1 corresponds to bond percolation, while q = 2 is the Ising model.
2. The Ising model on growing random networks: No analytical solution exists for the Ising model on growing random networks, although simulations on the Barabási-Albert network resemble uncorrelated scale-free networks with γ = 3.Growth generally produces a broad spectrum of structural correlations.
2. The Ising model on growing random networks: On recursive growing graphs, a single connection per new vertex produces a tree with ferromagnetic ordering only at zero temperature, whereas additional connections create non-tree networks.The passage frames this as the expected picture based on known percolation results.
A. Solution for uncorrelated networks: For the ferromagnetic p-state Potts model on an uncorrelated configuration model, TP represents percolation for p = 1, the Ising critical temperature for p = 2, and the lower hysteresis boundary for p ⩾3.The model uses positive uniform couplings Jij = J > 0 and average branching parameter B = z2/z1.

B. A first order transition … B. Mean-field approach

Across networked Potts, coloring, community-detection, XY, Landau, finite-size-scaling, and synchronization problems, network structure and model symmetry shape critical behavior, phase organization, and computational difficulty.

B. A first order transition: For p-state ferromagnetic Potts models, γ > 3 yields a first-order transition for p ⩾3 with coexistence and hysteresis, whereas 2 < γ ⩽3 yields an infinite-order transition.At γ →3^+, Tc increases while the magnetic-moment jump vanishes; for 2 < γ ⩽3, Tc(N)/J ≈z2/(z1p) ≫1 and the infinite network is ordered at any finite T.
C. Coloring a graph: Graph coloring has a p-COL/UNCOL threshold cp, with cp ∼2p ln p −ln p + o(1) at large p, while the colorable phase contains distinct clustered phases and frozen variables.Coloring is equivalent to the zero-energy ground state of an antiferromagnetic p-state Potts model; solutions become harder at higher mean degrees below cp, while Watts-Strogatz networks are hardest at intermediate shortcut density.
D. Extracting communities: Potts-model community detection represents communities as aligned-spin domains, and at λ = 1 its ground-state energy is proportional to modularity, H = −QL.The method balances a ferromagnetic term favoring mergers against a repulsive term favoring many communities, using a configuration-model null model with pij = qiqj/2L.
VIII. THE XY MODEL ON NETWORKS; A. The XY model on small-world networks; B. The XY model on uncorrelated networks: The XY model exhibits topology-dependent ordering: Watts-Strogatz networks undergo a second-order transition for any tiny shortcut fraction p, whereas uncorrelated networks have Tc = J⟨q2⟩/2z1 when ⟨q2⟩ is finite.At p = 0 the Watts-Strogatz system is one-dimensional and has no transition; when ⟨q2⟩ diverges, the uncorrelated-network model is ordered at every finite T.
IX. PHENOMENOLOGY OF CRITICAL PHENOMENA IN NETWORKS; A. Generalized Landau theory: Generalized Landau theory attributes universal network critical behavior to network structure and model symmetry, with degree-distribution nonanalyticities altering standard mean-field behavior.For Ising-like models, the singular term is relevant for 2 < γ ≤5 and δ(3 < γ < 5) = γ −2; for percolation-like odd-power cases, it is relevant for 2 < γ ≤4.
B. Finite-size scaling: Finite-size scaling requires an analytic scaling function and cannot be obtained by naively substituting the singular Landau potential into the scaling relation.The scaling relation contains exactly N on its left-hand side, while Δ may be min(4, γ −1) for Ising models or min(3, γ −1) for percolation.
X. SYNCHRONIZATION ON NETWORKS; A. The Kuramoto model: Kuramoto synchronization begins above Jc, with r ∝|J −Jc|β and β = 1/2 for the standard model, while the transition order depends on the natural-frequency distribution.Below Jc, r decays to O(N −1/2); above Jc, it approaches a finite value, and Jc = 2/[πg(0)] for the symmetric frequency distribution.

C. Numerical study of the Kuramoto model … B. Cascading failures

The paper examines synchronization and stability in complex networks, then turns to self-organized criticality and cascading failures, showing how network architecture controls critical behavior. Numerical and analytical results identify topology-dependent synchronization criteria, avalanche scaling regimes, and cascade thresholds.

C. Numerical study of the Kuramoto model: Synchronization emerges on Watts-Strogatz networks with few shortcuts, while scale-free networks synchronize at smaller critical coupling than comparable Erdős-Rényi networks.For N = 1000 oscillators, the scale-free network had a smaller Jc than the Erdős-Rényi network with the same average degree.
C. Numerical study of the Kuramoto model: On a Barabási-Albert network of size N = 5×10^4, the critical coupling is finite but small and the measured exponent is β ∼0.5.This result contrasts with the infinite-order transition and zero Jc predicted by mean-field theory as N →∞.
D. Coupled dynamical systems: Coupled dynamical systems possess coherent solutions because the network Laplacian has zero row sum, so xi = s(t) for every vertex follows any individual trajectory ˙s = F(s).The coupling strength is J, and topology is encoded by Lij = qiδij −aij.
1. Stability criterion.: The master stability function determines synchronization stability: the synchronized state is stable if and only if Λ(Jλn) < 0 for all n = 2, ...N.Here Λ is the largest Lyapunov exponent of the master stability equation, with α = Jλ.
2. Numerical study.: Synchronizability improves as the eigenratio λN/λ2 decreases, because stable coupling lies in the interval (α1/λ2, α2/λN).The network spectrum determines λ2 and λN, while α1 and α2 depend on the dynamical functions; α2/α typically ranges from 5 to 100 for chaotic oscillators.
2. Numerical study.: A small fraction of shortcuts sharply decreases λN/λ2 and makes sufficiently large ring networks synchronizable, whereas heterogeneity worsens synchronization in scale-free networks.For scale-free networks, the eigenratio increases as γ decreases; normalized or weighted couplings can instead make synchronizability less dependent on degree distribution and network size.
A. Sandpiles and avalanches: In uncorrelated scale-free sandpiles, avalanches form branching trees with power-law size and duration distributions, and γc = 3 −η separates scaling regimes.For γ > 3−η, τ = 3/2 and δ = z = 2.
B. Cascading failures: Cascading failures redistribute load after vertex removal, with outcomes depending on network architecture, tolerance α, and the initial failed vertex.In scale-free networks with 2 < γ ≤3, αc ≈0.15 separates giant from finite avalanches, whose critical size distribution has τ ≈2.1(1).

C. Congestion · XII. OTHER PROBLEMS AND APPLICATIONS · A. Contact and reaction-diffusion processes

The congestion models describe a transition driven by routers’ limited forwarding capacity, with critical power-law signatures and competing interpretations of self-similar traffic. Analytical and protocol-based approaches connect congestion to search costs and routing decisions, while the broader section introduces additional critical network processes.

C. Congestion: Hosts inject targeted packets at rate λ, while routers forward at most one packet per time step and queue packets in infinite buffers.The model distinguishes hosts from routers and routes each packet through a chain of routers.
C. Congestion: A critical injection rate λc marks a sharp rise in packet delivery time and the transition to a congestion phase.The observations suggest a continuous transition without a jump or hysteresis, caused by routers’ one-packet-per-step forwarding limit.
C. Congestion: At criticality, router packet-count time series exhibit a 1/f-type power spectrum and queue lengths follow a power-law distribution.These scaling effects were also reported in an analytically treatable model of traffic on hierarchically branching networks.
C. Congestion: Computer scientists criticized the claim that self-similar Internet traffic requires operation at a special critical load λc.They argued that self-similar scaling appears under low, medium, and high network loads.
C. Congestion: Minimizing mean queue length can be reformulated as minimizing network search cost, enabling analytical optimization of architectures for reduced congestion.Search cost is the mean number of steps needed to find a target vertex.
C. Congestion: A congestion-relief protocol routes packets toward neighboring routers with shorter queues, using queue length, shortest-path distance, and a parameter h with 0 ≤ h ≤1.Simulations on a real Internet map found that for h smaller than 1, the congestion transition has a distinct behavior measured by the order parameter ρ.
XII. OTHER PROBLEMS AND APPLICATIONS: The broader review section introduces critical effects and processes in networks that were missed in earlier sections.The supplied passage does not provide specific content for the subsection on contact and reaction-diffusion processes.

1. Contact process … 2. Biased random walks

The section surveys nonequilibrium transitions and dynamical phenomena on complex networks, including contact and reaction-diffusion processes, condensation, consensus, co-evolution, localization, and biased walks. Across these models, degree heterogeneity, network evolution, and finite-size effects determine thresholds, scaling, and long-time behavior.

1. Contact process: The contact process has an absorbing phase for p > pc and an active phase for p < pc, with pc = 1/2 in uncorrelated configuration-model networks.The critical exponent β depends on the degree distribution; for scale-free networks with 2 < γ ≤3, β = 1/(γ−2).
2. Reaction-diffusion processes: Reaction-diffusion thresholds depend on whether A particles diffuse: ρc = µ/λ without diffusion, but ρc = ⟨q⟩2µ/(⟨q2⟩λ) with diffusion.With divergent ⟨q2⟩, the latter threshold is zero as N →∞; without A diffusion, critical behavior does not depend on degree distribution.
B. Zero-range processes: In zero-range processes, condensation occurs above a critical concentration when u(n) decays asymptotically as u(∞)(1 + b/n) with b > 2.For u(n) = nδ on uncorrelated scale-free networks, the fluid phase persists at any density when δ > δc = 1/(γ −2), while condensation otherwise occupies high-degree vertices.
C. The voter model: The voter model conserves a degree-weighted fraction of up spins on random networks, making consensus unreachable in infinite uncorrelated networks but finite in finite systems.Consensus times scale as τN ∼N for converging ⟨q2⟩, τN ∼N/ ln N for P(q) ∼q−3, and slower than N when ⟨q2⟩ diverges.
D. Co-evolution models: In adaptive voter dynamics, opinion-dependent rewiring and neighbor imitation produce internally consensual components, while increasing φ destroys the giant component at φc = φc(⟨q⟩, N/G).The transition is nonequilibrium, has a seemingly power-law component-size distribution with a nonstandard exponent, and depends on the initial state.
E. Localization transitions: Localization transitions occur for quantum states on Erdős-Rényi graphs and for classical walks, but quantum delocalization does not coincide with the classical giant-component threshold.The localization phase has ⟨q⟩< qdeloc = 1.421529 . . ., the conducting phase lies above it, and relocalization occurs at qreloc = 3.154985 . . ..
2. Biased random walks: For exponentially biased walks, the localization transition occurs at λc = B = (⟨q2⟩−⟨q⟩)/⟨q⟩, the mean branching coefficient.The mean return time scales as N^ε below λc, as ∝ln N at λ = λc, and approaches a finite value above λc, with ε = ln(B/λ)/ ln B.
2. Biased random walks: Returns at sufficiently short odd times are virtually absent for biased walks because locally tree-like networks lack small loops.In this time range, a walker can return to its starting vertex only by retracing the route used to leave it.

F. Decentralized search … APPENDIX E: EQUATIONS OF STATE OF THE POTTS MODEL ON A NETWORK

The paper surveys diverse critical phenomena in complex networks, emphasizing unified analytical descriptions alongside distinctive effects of compactness, heterogeneity, finite size, and network structure. Its appendices connect decentralized search, graph partitioning, cooperative-model methods, replica calculations, max-cut bounds, and Potts-model equations.

F. Decentralized search: α = d gives the best performance for Kleinberg’s greedy decentralized search and therefore defines a “searchable” network.Related searchability occurs at special ξ values in trees with exponentially distributed shortcut lengths, while a growing-tree transition has ℓ(N) ∼ln2 N.
G. Graph partitioning: As the retained-edge fraction p decreases, optimal graph partitioning produces a sequence of jumps in the largest partition S, unlike ordinary percolation.Beyond the threshold, the largest partition is giant, with S ∼N.
A. Open problems: Open problems include synchronization, co-evolving networks, finite-size effects, loops, degree correlations, structural correlations, and the poorly understood critical behavior of growing networks.Loop effects on cooperative phenomena and a strict statistical-mechanics theory of finite networks remain unresolved.
XIII. SUMMARY AND OUTLOOK; B. Conclusions: Critical phenomena in networks can be understood through a unified approach, while their emergence reflects the combination of small-world compactness, heterogeneity, and complex architecture.The review also stresses that applications to real-world networks remain comparatively modest.
APPENDIX A: BETHE-PEIERLS APPROACH: THERMODYNAMIC PARAMETERS; APPENDIX B: BELIEF-PROPAGATION ALGORITHM: MAGNETIC MOMENT AND THE BETHE FREE ENERGY: The Bethe-Peierls and belief-propagation frameworks determine neighboring-spin correlations, thermodynamic quantities, local magnetic moments, and Bethe free-energy stationary points.At a fixed point, the beliefs yield the correlation function Cij and a local minimum of the Bethe free energy.
APPENDIX C: REPLICA TRICK: The replica trick averages quenched disorder over network ensembles and, in the thermodynamic limit, yields saddle-point equations whose replica-symmetric solution reproduces the Bethe-Peierls self-consistent message equation.The resulting Ψ(h) is the distribution function of additional fields in the network.
APPENDIX D: MAX-CUT ON THE ERD˝OS-R´ENYI GRAPH; APPENDIX E: EQUATIONS OF STATE OF THE POTTS MODEL ON A NETWORK: For the Potts model on uncorrelated networks, the equations of state unify percolation, the ferromagnetic Ising model, and first-order transitions, and are exact as N →∞.The one-state case recovers bond percolation with r(T = TP) = z1/z2, while p = 2 reduces to the Ising equation after rescaling J, H, and h; max-cut analysis separately bounds Kc through Ξ(αc) = 0.