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

When steam condenses from vapour into liquid, the water molecules move closely together and the system, from a mathematical point of view, comes to reside in an extremely small portion of the conceptually available phase space. By analogy, the term “condensation” has come to refer to any similar phenomenon in which a system with many degrees of freedom exists in a state involving only a few degrees of freedom. Important examples include Bose Einstein condensation in cold atomic gases, or condensation of wealth in economic models, where a finite number of individuals come to possess a significant fraction of all wealth. These examples reflect the surprising typical behaviour of dynamical systems of many interacting parts under certain conditions.
Condensation can also happen in another way, as a purely mathematical phenomenon in statistical ensembles tuned to skew their character toward more extreme outcomes, an effect called “condensation of fluctuations.” In a new paper, LML External Fellows Fernando Metz and Isaac Pèrez Castillo explore this effect in the context of a standard model for random graphs. As normally considered, this ensemble of graphs does not show any condensation phenomena, but Metz and Castillo study how the typical behaviour of the ensemble changes as they vary a parameter which biases the ensemble. It plays the role of a fictitious temperature, allowing the exploration of rare regions of the ensemble space. Metz and Castillo derive an exact solution for the fraction of nodes having degrees within an interval [a; b], b > a > 0, and show that the ensemble of random graphs undergoes a first-order phase transition between a Poisson-like phase, where the degree distribution is closer to its typical behaviour, and a condensed phase, where the degree distribution exhibits a prominent peak.
The authors go on to derive a phase diagram for this mathematical transition in the ensemble
parameter space. As they demonstrate, it exhibits two critical lines, each surrounded by a metastable region and terminating at a critical point. The critical lines define the set of points in the parameter space at which the degree distribution changes abruptly. In the condensed phase, the degrees of nodes become concentrated in a limited part of their range, and sample random graphs take on a homogeneous structure similar to regular random graphs. Due to their conceptual and mathematical simplicity, random graphs provide useful models in the study of disordered quantum and classical magnetic systems, optimization problems, as well as complex networks of many kinds. The researchers believe this mathematical recipe for producing graph with unusually homogeneous structure should prove useful in many such settings.
A pre-print of the paper is available at https://arxiv.org/abs/1904.09457

Leave a Reply

Your email address will not be published. Required fields are marked *