Ensemble inequivalence and phase transitions in unlabeled networks

Abstract

We discover a first-order phase transition in the canonical ensemble of random unlabeled networks with a prescribed average number of links. The transition is caused by the nonconcavity of microcanonical entropy. Above the critical point coinciding with the graph symmetry phase transition, the canonical and microcanonical ensembles are equivalent and have a well-behaved thermodynamic limit. Below the critical point, the ensemble equivalence is broken, and the canonical ensemble is a mixture of phases: empty networks and networks with average degrees diverging logarithmically with the network size. As a consequence, networks with bounded average degrees do not survive in the thermodynamic limit, decaying into the empty phase. The celebrated percolation transition in labeled networks is thus absent in unlabeled networks. In view of these differences between labeled and unlabeled ensembles, the question of which one should be used as a null model of different real-world networks cannot be ignored.

v2: version accepted for publication

References in corpus (28)

• The statistical mechanics of networks
• Network Analysis of Particles and Grains
• Solution of the 2-star model of a network
• Classification of phase transitions and ensemble inequivalence, in systems with long range interactions
• Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
• Solution for the properties of a clustered network
• Discontinuous Percolation Transitions in Epidemic Processes, Surface Depinning in Random Media and Hamiltonian Random Graphs
• Breaking of ensemble equivalence in networks
• Gibbs entropy of networks ensembles by cavity methods
• Phase transitions in a complex network
• The phases of large networks with edge and triangle constraints
• Continuous phase transitions with a convex dip in the microcanonical entropy
• Combinatorial Quantum Gravity: Geometry from Random Bits
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Ollivier-Ricci curvature convergence in random geometric graphs
• Reducing Degeneracy in Maximum Entropy Models of Networks
• Impact of physicality on network structure
• Thermodynamic instability and first-order phase transition in an ideal Bose gas
• Physical networks as network-of-networks
• Analysis of the convergence of the degree distribution of contracting random networks towards a Poisson distribution using the relative entropy
• Convergence towards an Erd{\H o}s-Rényi graph structure in network contraction processes
• Statistical mechanics of graph models and their implications for emergent spacetime manifolds
• The birth of geometry in exponential random graphs
• Entropy of labeled versus unlabeled networks
• Random-Graph Models and Characterization of Granular Networks
• Entropy of microcanonical finite-graph ensembles
• Asymptotic equivalence of probability measures and stochastic processes
• A Gaussian integral that counts regular graphs