Breaking of ensemble equivalence in networks

It is generally believed that, for physical systems in the thermodynamic limit, the microcanonical description as a function of energy coincides with the canonical description as a function of temperature. However, various examples have been identified for which the microcanonical and canonical ensembles are not equivalent. A complete theory of this intriguing phenomenon is still missing. Here we show that ensemble nonequivalence can manifest itself also in discrete enumeration problems. We show that, for discrete systems, ensemble equivalence reduces to equivalence of the large deviation properties of microcanonical and canonical probabilities of a single microstate. As specific examples, we consider ensembles of graphs with topological constraints. We find that, while graphs with a given number of links are ensemble-equivalent, graphs with a given degree sequence (including random regular graphs, sparse scale-free networks, and core-periphery networks) are not. This mathematical result provides a theoretical explanation for various `anomalies' that have recently been observed in networks, namely, the non-vanishing of canonical fluctuations in the configuration model and of the difference between microcanonical and canonical entropies of random regular graphs. While it is generally believed that ensemble nonequivalence is associated with long-range interactions, our findings show that it may naturally arise in systems with local constraints as well.