Condensation of degrees emerging through a first-order phase transition in classical random graphs

Due to their conceptual and mathematical simplicity, Erdös-Rényi or classical random graphs remain as a fundamental paradigm to model complex interacting systems in several areas. Although condensation phenomena have been widely considered in complex network theory, the condensation of degrees has hitherto eluded a careful study. Here we show that the degree statistics of the classical random graph model undergoes a first-order phase transition between a Poisson-like distribution and a condensed phase, the latter characterized by a large fraction of nodes having degrees in a limited sector of their configuration space. The mechanism underlying the first-order transition is discussed in light of standard concepts in statistical physics. We uncover the phase diagram characterizing the ensemble space of the model, and we evaluate the rate function governing the probability to observe a condensed state, which shows that condensation of degrees is a rare statistical event akin to similar condensation phenomena recently observed in several other systems. Monte Carlo simulations confirm the exactness of our theoretical results.

Figure 1

The quantity ${\mathcal{F}}_{[a,b]}\left(\mu \right|y)$ as a function of the order parameter $\mu$ for average degree $c=13, a=1, b=3$, and increasing values of $y$. The global maximum of ${\mathcal{F}}_{[a,b]}\left(\mu \right|y)$ with respect to $\mu$ provides the cumulant generating function [see Eqs. (14, 15, 16)]. The behavior of ${\mathcal{F}}_{[a,b]}\left(\mu \right|y)$ characterizes the emergence of a first-order transition: for $y$ approximately in the range (3.48,3.99), the function ${\mathcal{F}}_{[a,b]}\left(\mu \right|y)$ exhibits two maxima, which have the same height only at the critical value $y_{\mathrm{FT}}\simeq 3.70$. The function ${\mathcal{F}}_{[a,b]}\left(\mu \right|y)$ has a single maximum for $y\lesssim 3.48$ and $y\gtrsim 3.99$.

Figure 2

The quantity ${\mathcal{F}}_{[a,b]}\left(\mu \right|y)$ as a function of the order parameter $\mu$ for $a=1, b=3$, and different values of the average degree $c$ along the upper critical line (see Fig. 5). The two maxima have the same height and thus contribute equally to the cumulant generating function, which features the coexistence of phases. The two maxima merge into a single maximum right at the critical point.

Figure 3

Fraction $f$ of degrees within the interval [1,3] as a function of $y$ for different values of the average degree $c$. For large values of $c, f$ has a discontinuous behavior at a critical value $y_{\mathrm{FT}}$, marking the first-order phase transition.

Figure 4

Average ${\langle k\rangle }_y$ (dashed line) and variance ${\sigma }_k^2$ (solid line) of the degree distribution $p_y\left(k\right)$ [see Eq. (11)] characterizing rare graph samples generated from Eq. (1), with $c=13$, and conditioned to have a certain fraction $f$ of degrees inside the interval [1,3]. The concurrent behavior of $f$ as a function of $y$ is presented in Fig. 3. The inset shows the typical profile of the degree distribution in each phase. The quantities ${\langle k\rangle }_y$ and ${\sigma }_k^2$ have a discontinuous behavior that features the abrupt change of the degree statistics along the first-order phase transition.

Figure 5

Phase diagram showing the fraction $f$ of degrees lying in [1,3] for each combination of parameters $(c,y)$. The values of $-log\left(f\right)$ are displayed in a density plot according to the color scale. The red dashed curves denote first-order critical lines. The black solid lines surrounding each critical line delimit the regions of the phase diagram where the saddle-point Eq. (17) has three fixed-point solutions. The solid yellow circles, located at the end of each critical line, represent critical points at which the two maxima of ${\mathcal{F}}_{[a,b]}\left(\mu \right|y)$ merge into a single one (see Fig. 2).

Figure 6

Rate function ${\mathrm{\Psi }}_{[a,b]}\left(f\right)$, characterizing the large deviation probability of Eq. (9), as a function of the fraction $f$ of nodes with degrees within the interval [1,3]. We show the rate function for different values of the average connectivity $c$. The function ${\mathrm{\Psi }}_{[a,b]}\left(f\right)$ has a minimum at the typical value $f=f_{\mathrm{typ}}$ [see Eq. (5)]. For the case $c=2$ (solid blue line with triangles), we also show the presence of two nonanalytic points (light red squares) at which the second derivatives of the rate function are discontinuous. By the construction of the Legendre-Fenchel transform [30], these points are connected by a straight line (solid red line with triangles). The dashed blue line is the rate function obtained from choosing the metastable solution for the order parameter $\mu$ when calculating the CGF. The different symbols (triangles, pentagons, and rhombuses) are simulation results obtained through a reweighting Monte Carlo method of graphs with a total of $N=100$ nodes (see Appendix pp2).