Transitions in random graphs of fixed degrees with many short cycles
Open Access
- 21 May 2021
- journal article
- research article
- Published by IOP Publishing in Journal of Physics: Complexity
- Vol. 2 (3) , 035010
Abstract
We analyze maximum entropy random graph ensembles with constrained degrees, drawn from arbitrary degree distributions, and a tuneable number of three-cycles (triangles). We find that such ensembles generally exhibit two transitions, a clustering and a shattering transition, separating three distinct regimes. At the clustering transition, the graphs change from typically having only isolated cycles to forming cycle clusters. At the shattering transition the graphs break up into many small cliques to achieve the desired three-cycle density. The locations of both transitions depend nontrivially on the system size. We derive a general formula for the three-cycle density in the regime of isolated cycles, for graphs with degree distributions that have finite first and second moments. For bounded degree distributions we present further analytical results on cycle densities and phase transition locations, which, while non-rigorous, are all validated via MCMC sampling simulations. We show that the shattering transition is of an entropic nature, occurring for all three-cycle density values, provided the system is large enough.Keywords
Funding Information
- Secretaría de Ciencia, Humanidades, Tecnología e Innovación
This publication has 38 references indexed in Scilit:
- Effects of Heterogeneous and Clustered Contact Patterns on Infectious Disease DynamicsPLOS Computational Biology, 2011
- Publisher's Note: Hierarchical self-assembly of asymmetric amphiphatic spherical colloidal particles [Phys. Rev. E80, 021404 (2009)]Physical Review E, 2009
- Solution for the properties of a clustered networkPhysical Review E, 2005
- Protein function prediction via graph kernelsBioinformatics, 2005
- How likely is an i.i.d. degree sequence to be graphical?The Annals of Applied Probability, 2005
- Network transitivity and matrix modelsPhysical Review E, 2004
- Vertex overload breakdown in evolving networksPhysical Review E, 2002
- The random triangle modelJournal of Applied Probability, 1999
- A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular GraphsEuropean Journal of Combinatorics, 1980
- Information Theory and Statistical MechanicsPhysical Review B, 1957