Critical phenomena in complex networks

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, important steps have been made toward understanding the qualitatively new critical phenomena in complex networks. The results, concepts, and methods of this rapidly developing field are reviewed. Two closely related classes of these critical phenomena are considered, namely, structural phase transitions in the network architectures and transitions in cooperative models on networks as substrates. Systems where a network and interacting agents on it influence each other are also discussed. 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 are mentioned. Strong finite-size effects in these systems and open problems and perspectives are also discussed.

Figure 1

Cayley tree (on the left) vs the Bethe lattice (on the right).

Figure 2

Statistical ensembles of equilibrium random connected trees (left-hand side) and growing connected trees (right-hand side) for $N=1,2,3,4$. The ensemble of equilibrium trees consists of all possible connected trees of $N$ labeled vertices, where each tree is taken with the same weight. The ensemble of growing (causal) trees is the following construction. Its members are all possible connected trees of size $N$ that can be made by sequential attachment of new labeled vertices. Each of these trees of $N$ vertices is taken with the same weight. Notice that at $N=3$ one of the labeled graphs of the equilibrium ensemble is absent in the ensemble of growing trees. At $N=4$, the numbers of isomorphic graphs is indicated in both ensembles. (By definition, isomorphic graphs differ from each other only by vertex labels.) Already at $N=4$ the equilibrium random tree is less compact, since the probability of realization of the chain is higher in this case.

Figure 3

Distribution of connections and the mean degree of a randomly chosen vertex (on the left) differ sharply from those of end vertices of a randomly chosen edge (on the right).

Figure 4

Examples of deterministic small worlds: (a) 26, (b) 141 and 132, (c) 11 and 150, and (d) 225. The $\gamma$ exponent for each of these four deterministic graphs is $1+\ln 3∕\ln 2=2.585\dots$ .

Figure 5

A simple variation of the Watts-Strogatz model (431; 429). Adapted from 323.

Figure 6

(a) Graphic notation for the probability $x$ that, following a randomly chosen edge to one of its end vertices, we arrive at a finite connected component. (b) Equation (8) or, equivalently, Eq. (10) in graphic form. (c) Graphic representation of Eq. (9) and of equivalent Eq. (11) for the relative size $S$ of the giant connected component.

Figure 7

Effect of the heavy-tailed architecture of a network on the variation of its giant connected component under random damage. The relative size of the giant connected component $S$ is shown as a function of the concentration $p$ of the retained vertices in the infinite network.

Figure 8

Construction of the 3-core of a graph. First we remove vertices 1, 2, and 4 together with their links because they have degrees smaller than 3. In the obtained graph, vertex 3 has degree 1. By removing it, we get the 3-core of the graph.

Figure 9

Diagrammatic representation of Eqs. (29, 30, 31). (a) Graphic notations for the order parameter $R$ and for $1-R$. (b) The probability that both ends of an edge are in the $k$-core, Eq. (29). (c) Configurations contributing to $M_k$, which is the probability that a vertex is in the $k$-core, Eq. (30). The symbol $\forall$ indicates that there may be any number of nearest neighbors that are not trees of infinite $(k-1)$-ary subtrees. (d) A graphic representation of Eq. (31) for the order parameter. Adapted from 183.

Figure 10

Relative sizes of the $k$-cores $M_k$ in classical random graphs with the mean degree $z_1=10$ versus the concentration $Q=1-p$ of randomly removed vertices. Adapted from 136.

Figure 11

Relative size of the $k$-cores vs $k$ in several networks. ○, $M_k$ calculated neglecting correlations, using the degree distribution of Internet router network, $N\approx 190000$. Adapted from 136. △, measurements for the autonomous system network [Cooperative Association for Internet Data Analysis (CAIDA) map], $N=8542$. Adapted from 10. ●, results for a maximally random scale-free $(\gamma =2.5)$ network of ${10}^6$ vertices, and ◼, for a similar network but with a given strong clustering, $C=0.71$. Adapted from 382.

Figure 12

(Color online) Bond percolation on unclustered and strongly and weakly clustered scale-free networks. The exponent $\gamma =3.5$. The relative size $S$ of the giant connected component is shown as a function of the concentration $Q=1-p$ of removed edges. From 384.

Figure 13

Mean number of triangles $⟨T⟩$ as a function of the parameter $G$ in the metastable state of the network of $N=2^{14}$ vertices for three values of the mean degree $⟨q⟩=2,4,8$. The dots are results of a simulation, and the lines are theoretical curves $⟨T⟩=({⟨q⟩}^3∕6)\exp \left(G\right)\lesssim N$. The rightmost dot in each set corresponds to the threshold value $G_t\left(⟨q⟩\right)$ above which the network quickly approaches the condensation state with $⟨T⟩\sim N^{3∕2}$. From 80.

Figure 14

Evolution of the average fraction of infected vertices in the SIR model on the Barabási-Albert network of ${10}^6$ vertices for various initial conditions. At $t=0$, randomly chosen vertices of a given degree $q$ are infected. The spreading rate is $\lambda =0.09$, which is above the epidemic threshold of this finite network. From 309.

Figure 15

A cluster on a graph. Within the Bethe-Peierls approach, we choose a cluster consisting of spin $i$ and its nearest neighbors (closed circles). Cavity fields ${\varphi }_{j\backslash i}$ (vertical arrows) take into account interactions with remaining spins (dotted lines and open circles). $H_i$ is a local field. Arrows along edges show fields created by neighboring spins at vertex $i$.

Figure 16

Diagrammatic representation of Eq. (57). An outgoing message $h_{ij}$ from vertex $i$ to vertex $j$ is determined by the local field $H_i$ and incoming messages to $i$ excluding the message from $j$.

Figure 17

Diagrammatic representation of the belief-propagation update rule. Arrows show incoming messages to a vertex $j$. A factor $\exp \left(\beta H_j{S}_j\right)$ is shown as the closed circle. A solid line between $j$ and $i$ shows a factor $\exp \left(\beta J_{ij}{S}_i{S}_j\right)$. The double line is a new (outgoing) message from $j$ to $i$.

Figure 18

Exponent $\kappa$ vs $T$ for the ferromagnetic Ising model on the regular Cayley tree with degree $q=3$. The critical temperatures $T_l$ are shown by dotted lines.

Figure 19

Domains of flipped spins in the ferromagnetic Ising model on a regular Cayley tree. Filled and open circles represent spins up and down. Double lines shows “frustrated” edges connecting antiparallel spins.

Figure 20

Schematic representation of the critical behavior of the magnetization $M$ (dotted lines), the magnetic susceptibility $\chi$ (dashed lines), and the specific heat $C$ (solid lines) for the ferromagnetic Ising model on uncorrelated random networks with a degree distribution $P\left(q\right)\sim q^{-\gamma }$. (a) $\gamma ⪢1$, the standard mean-field critical behavior. A jump of $C$ disappears when $\gamma \to 5$. (b) $4<\gamma ⩽5$, the ferromagnetic phase transition is of second order. (c) $3<\gamma ⩽4$, the transition becomes of higher order. (d) $2<\gamma ⩽3$, the transition is of infinite order, and $T_c\to \infty$ as $N\to \infty$.

Figure 21

Distribution function $Y\left(M\right)$ of magnetic moments $M$ in the ferromagnetic Ising model on the Erdős-Rényi graph with mean degree $z_1=5$ (dashed line) and scale-free graphs with $\gamma =4$ and 3.5 (solid and dotted lines) at $T$ close to $T_c$, $\beta \overline{h}=0.04$.

Figure 22

Partition of vertices in a graph into two sets consisting of $S$ and $N-S$ vertices, and $K$ edges (solid lines) in the cut. Dotted lines show edges inside the sets.

Figure 23

Vertex cover of a graph. (a) Open circles form a minimum vertex cover of the graph. Every edge has at least one end point that belongs to the vertex cover. The closed circles form the maximum independent set of the graph. (b) The complement of the same graph (we add the missing edges and remove the already existing edges). Closed circles form the maximum clique.

Figure 24

Phase diagram of the antiferromagnetic Ising model Eq. (101) at $T=0$. $P$, $F$, and $M$ denote paramagnetic, ferromagnetic, and mixed (spin-glass) phases, respectively. At mean degree $z_1>e$, in the mixed phase, ferromagnetism and spin-glass order coexist.

Figure 25

Deterministic fully connected graph (121), which is equivalent to the asymmetric annealed network. The values of the Ising coupling are shown on the edges.

Figure 26

Magnetization profile for the ferromagnetic Ising model on the graph shown in Fig. 25. $i$ labels vertices starting from the “oldest” one, and $t$ is the network size. Curve 1 is valid both for $T<T_c$ with an arbitrary homogeneous applied field $H$ and for $T>T_c$, $H\ne 0$. Curve 2 describes the profile when an external field is applied to a single spin, while $T>T_c$. The arrow indicates the point of application of the local magnetic field. The mean magnetic moment of this vertex is distinct from others.

Figure 27

Magnetic moment $M$ vs $T$ for the ferromagnetic Potts model on an uncorrelated scale-free network with average degree $z_1=10$. Leftmost curves, $\gamma =4$; rightmost curves, $\gamma =3.5$. Numerical simulations and exact numerical solution (154) are shown by crosses and solid lines. Dotted lines, an approximate solution (134). Vertical lines, the lower-temperature boundary $T_P$ of the hysteresis region. From 154.

Figure 28

Schematic phase diagram and structure of solutions for coloring Erdős-Rényi graphs in $p$-colors vs the average degree $z_1$. (i) $z_1<c_{d,+}$, solutions form one large connected cluster without frozen variables (open circle). (ii) $c_{d,+}<z_1<c_d$, in addition to a large cluster, small disjoint clusters with frozen variables (black circles) appear. They include, however, an exponentially small fraction of solutions. (iii) $c_d<z_1<c_c$, solutions are arranged in exponentially many clusters of different sizes with and without frozen variables. Exponentially many clusters without frozen variables dominate. (iv) $c_c<z_1<c_r$, there are a finite number of statistically dominating large clusters. These clusters do not contain frozen variables. (v) $c_r<z_1<c_p$, dominating clusters contain frozen variables. Above $c_p$, a graph is $p$-uncolorable. $c_{d,+}$ coincides with the 2-core point of emergence. $c_d$, $c_c$, and $c_r$ correspond to so-called clustering, condensation, and rigidity (freezing) transitions, respectively. Adapted from 443.

Figure 29

$p\text{−}T$ phase diagram of the ferromagnetic $XY$ model on the Watts-Strogatz network. $p$ is the fraction of shortcuts. $D$ and $O$ denote the disordered and ordered phases, respectively. The inset shows that the critical temperature is well approximated by a function $0.41\ln p+2.89$. From 236.

Figure 30

Schematic view of phases in the Kuramoto model. (a) Incoherent phase. Unit length vectors representing individual states are randomly directed in the complex plane. (b) Coherent phase. The individual states condense around a direction $\psi$.

Figure 31

(Color online) Synchronization patterns of Erdős-Rényi (ER) and scale-free (SF) networks for several values of coupling $\lambda$ (or $J$ in our notations). From 184.

Figure 32

Ratio ${\lambda }_N∕{\lambda }_2$ vs the fraction of shortcuts $p$ for the Watts-Strogatz network generated from a ring. Adapted from 212.

Figure 33

Examples of graphs with optimal synchronizability: (a) a fully connected graph, (b) a directed star, and (c) a hierarchical directed random graph.

Figure 34

Order parameter $\rho$ vs the packet injection rate $\lambda$ for various $h$ using the model of 152. From 152.

Figure 35

Relative density of particles $B$ vs the total density of $A$ and $B$ particles in the reaction-diffusion model in scale-free networks at $\mu ∕\lambda =2$. Rightmost curves ($A$ particles are nondiffusing): stars, $N={10}^4$, $\gamma =3$; closed diamonds, $N={10}^4$, $\gamma =2.5$; open circles, $N={10}^5$, $\gamma =2.5$. Leftmost curves (both $A$ and $B$ particles are diffusing, $\gamma =2.5$): open squares, $N={10}^3$; closed squares, $N={10}^4$; open triangles, $N={10}^5$. Adapted from 116.