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.

We review the recent rapid progress in the statistical physics of evolving networks. Interest has focused mainly on the structural properties of complex networks in communications, biology, social sciences and economics. A number of giant artificial networks of this kind have recently been created, which opens a wide field for the study of their topology, evolution, and the complex processes which occur in them. Such networks possess a rich set of scaling properties. A number of them are scale-free and show striking resilience against random breakdowns. In spite of the large sizes of these networks, the distances between most of their vertices are short - a feature known as the 'small-world' effect. We discuss how growing networks self-organize into scale-free structures, and investigate the role of the mechanism of preferential linking. We consider the topological and structural properties of evolving networks, and percolation and disease spread on these networks. We present a number of models demonstrating the main features of evolving networks and discuss current approaches for their simulation and analytical study. Applications of the general results to particular networks in nature are discussed. We demonstrate the generic connections of the network growth processes with the general problems of non-equilibrium physics, econophysics, evolutionary biology, and so on.

The model of growing networks with the preferential attachment of new links is generalized to include initial attractiveness of sites. We find the exact form of the stationary distribution of the number of incoming links of sites in the limit of long times, $P\left(q\right)$, and the long-time limit of the average connectivity $\overline{q}(s,t)$ of a site $s$ at time $t$ (one site is added per unit of time). At long times, $P\left(q\right)\sim q^{-\gamma }$ at $q\to \infty$ and $\overline{q}(s,t)\sim (s/t{)}^{-\beta }$ at $s/t\to 0$, where the exponent $\gamma$ varies from $2$ to $\infty$ depending on the initial attractiveness of sites. We show that the relation $\beta (\gamma -1\mathrm{})=1\mathrm{}$ between the exponents is universal.

We analytically describe the architecture of randomly damaged uncorrelated networks as a set of successively enclosed substructures—$k$-cores. The $k$-core is the largest subgraph where vertices have at least $k$ interconnections. We find the structure of $k$-cores, their sizes, and their birthpoints—the bootstrap percolation thresholds. We show that in networks with a finite mean number $z_2$ of the second-nearest neighbors, the emergence of a $k$-core is a hybrid phase transition. In contrast, if $z_2$ diverges, the networks contain an infinite sequence of $k$-cores which are ultrarobust against random damage.

We find that scale-free random networks are excellently modeled by simple deterministic graphs. Our graph has a discrete degree distribution (degree is the number of connections of a vertex), which is characterized by a power law with exponent $\gamma =1+\ln 3/\ln 2.$ Properties of this compact structure are surprisingly close to those of growing random scale-free networks with γ in the most interesting region, between 2 and 3. We succeed to find exactly and numerically with high precision all main characteristics of the graph. In particular, we obtain the exact shortest-path-length distribution. For a large network $\left(\ln N\gg 1\right)$ the distribution tends to a Gaussian of width $\sim \sqrt{\ln N}$ centered at $\mathcal{l}¯\sim \ln N.\mathrm{}$ We show that the eigenvalue spectrum of the adjacency matrix of the graph has a power-law tail with exponent $2+\gamma .$

We reveal the nature of the avalanche collapse of the giant viable component in multiplex networks under perturbations such as random damage. Specifically, we identify latent critical clusters associated with the avalanches of random damage. Divergence of their mean size signals the approach to the hybrid phase transition from one side, while there are no critical precursors on the other side. We find that this discontinuous transition occurs in scale-free multiplex networks whenever the mean degree of at least one of the interdependent networks does not diverge.