Random graphs can undergo structural phase transitions as a function of their model parameters. For example, in the well-known percolation transition, a network-spanning cluster of linked nodes abruptly appears at a critical value of the probability, c, for a link to exist between any pair of nodes. Recent research discovered a different structural phase transition in random graphs, this involving an sharp change in the statistical degree distribution within the graph, degree being the number of links attached to each node. Variation of a control parameter sees the degree distribution change discontinuously from a Poisson form to a distribution with a pronounced peak. As a result, the random graph has a more regular structure, with most nodes having roughly similar numbers of links.
Unsurprisingly. the degree statistics often exert a strong influence over the dynamics of processes operating on random graphs, including random walks, epidemic spreading or Ising and similar models of cooperative behaviour. In a new paper, LML External Fellows Isaac Pérez Castillo and Fernando Metz, working with Edgar Guzmán-González of the National Autonomous University of Mexico, explore two specific examples. They study the thermodynamic phase transition of the Ising model, as well as the eigenvalue distribution of the adjacency matrix, both for the simplest Erdös-Rényi model of random graphs. In the first case, they find that large deviations in the graph structure induce different thermodynamic phase transitions, which are otherwise absent in typical random graphs. The Ising model instead displays three additional first-order transitions – one between ferromagnetic phases, another between paramagnetic phases, and a third between ferromagnetic and paramagnetic phases. All three transitions coincide with the discontinuous change of the degree statistics. In a second example, the authors show that the eigenvalue statistics of the adjacency matrix of the random graphs also exhibits discontinuous behaviour across the condensation transition. In this case, the second moment of the eigenvalue distribution drops abruptly, indicating a concentration of eigenvalues around zero.
As the authors note, this condensation transition is a statistically rare event, induced by deliberate tuning of the statistical ensemble. Nevertheless, they expect the reported results may help in understanding the macroscopic behaviour of some real systems modelled using random graphs under conditions in which constraints force nodes to have similar degrees. In particular, the effects of condensation of degrees may arise in natural settings including synchronization phenomena or diffusion processes on graphs or in the dynamics of network formation. It may also be relevant to studies of the linear stability of sparse interacting systems.
The paper is available at https://arxiv.org/pdf/1909.10564.pdf
Leave a Reply