Phase transitions in a complex network

Abstract

We study a mean field model of a complex network, focusing on edge and triangle densities. Our first result is the derivation of a variational characterization of the entropy density, compatible with the infinite node limit. We then determine the optimizing graphs for small triangle density and a range of edge density, though we can only prove they are local, not global, maxima of the entropy density. With this assumption we then prove that the resulting entropy density must lose its analyticity in various regimes. In particular this implies the existence of a phase transition between distinct heterogeneous multipartite phases at low triangle density, and a phase transition between these phases and the disordered phase at high triangle density.

Title of previous version was `A mean field analysis of the fluid/solid phase transition'

References in corpus (4)

• An Introduction to the Thermodynamic and Macrostate Levels of Nonequivalent Ensembles
• Solution for the properties of a clustered network
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Minimum Number of k-Cliques in Graphs with Bounded Independence Number

Cited by in corpus (35)

• Breaking of ensemble equivalence in networks
• The Asymptotics of Large Constrained Graphs
• The phases of large networks with edge and triangle constraints
• Asymptotic Structure of Graphs with the Minimum Number of Triangles
• Singularities in the entropy of asymptotically large simple graphs
• Phase transitions in social networks inspired by the Schelling model
• Ensemble nonequivalence in random graphs with modular structure
• On the lower tail variational problem for random graphs
• The ambiguity of nestedness under soft and hard constraints
• Interacting Thermofield Doubles and Critical Behavior in Random Regular Graphs
• Asymptotic structure and singularities in constrained directed graphs
• Asymptotic quantization of exponential random graphs
• On the asymptotics of constrained exponential random graphs
• Asymptotics for Sparse Exponential Random Graph Models
• Reciprocity in directed networks
• The birth of geometry in exponential random graphs
• Elusive extremal graphs
• A detailed investigation into near degenerate exponential random graphs
• Ensemble nonequivalence and Bose-Einstein condensation in weighted networks
• Asymptotic Structure of Constrained Exponential Random Graph Models
• Large deviations and exact asymptotics for constrained exponential random graphs
• Phase transitions in edge-weighted exponential random graphs
• Simple evolving random graphs
• Description length of canonical and microcanonical models
• Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality
• Ensemble inequivalence and absence of quasi-stationary states in long-range random networks
• Ensemble inequivalence and phase transitions in unlabeled networks
• Finite-size effects in exponential random graphs and cluster evaporation
• Regular graphs with linearly many triangles
• Surface effects in dense random graphs with sharp edge constraint
• Nucleation during phase transitions in random networks
• On the Number of Graphs with a Given Histogram
• Ground States for Exponential Random Graphs
• Lattice Gas Models with Long Range Interactions
• Extremal Behavior in Exponential Random Graphs