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

Abstract

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.

arXiv comment8 pages, 6 figures

References in corpus (26)

• Critical phenomena in complex networks
• The large deviation approach to statistical mechanics
• Connectivity of Growing Random Networks
• Bose-Einstein condensation in complex networks
• The statistical mechanics of networks
• Nonequilibrium Statistical Mechanics of the Zero-Range Process and Related Models
• Full dynamical solution for a spherical spin-glass model
• Solution of the 2-star model of a network
• Solution for the properties of a clustered network
• Network Transitivity and Matrix Models
• Interaction driven real-space condensation
• Principles of statistical mechanics of random networks
• Statistical mechanics of topological phase transitions in networks
• Distribution of diameters for Erdös-Rényi random graphs
• Large deviation function for the number of eigenvalues of sparse random graphs inside an interval
• Entropy distribution and condensation in random networks with a given degree distribution
• Condensation of Fluctuations in and out of Equilibrium
• Condensation transition in joint large deviations of linear statistics
• Perturbing General Uncorrelated Networks
• Organization of complex networks without multiple connections
• Large deviations, condensation, and giant response in a statistical system
• Large deviation theory for diluted Wishart random matrices
• The two-star model: exact solution in the sparse regime and condensation transition
• Probability distributions with singularities
• Theory for the conditioned spectral density of non-invariant random matrices
• Phase diagram and metastability of the Ising model on two coupled networks

Cited by in corpus (4)

• Generalized optimal paths and weight distributions revealed through the large deviations of random walks on networks
• Analytic solution of the two-star model with correlated degrees
• Phase transitions in atypical systems induced by a condensation transition on graphs
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks