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 (36)

• Estimating and understanding exponential random graph models
• 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
• The ambiguity of nestedness under soft and hard constraints
• On the lower tail variational problem for random graphs
• Asymptotic structure and singularities in constrained directed graphs
• Interacting Thermofield Doubles and Critical Behavior in Random Regular 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
• A detailed investigation into near degenerate exponential random graphs
• Elusive extremal 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
• Description length of canonical and microcanonical models
• Simple evolving random graphs
• Phase Transitions in Edge-Weighted Exponential Random Graphs: Near-Degeneracy and Universality
• Phase transitions in edge-weighted exponential random graphs
• Ensemble inequivalence and absence of quasi-stationary states in long-range random networks
• Finite-size effects in exponential random graphs and cluster evaporation
• Regular graphs with linearly many triangles
• Ensemble inequivalence and phase transitions in unlabeled networks
• Surface effects in dense random graphs with sharp edge constraint
• Nucleation during phase transitions in random networks
• Extremal Behavior in Exponential Random Graphs
• Lattice Gas Models with Long Range Interactions
• Ground States for Exponential Random Graphs
• On the Number of Graphs with a Given Histogram