Ensemble nonequivalence in random graphs with modular structure

Abstract

Breaking of equivalence between the microcanonical ensemble and the canonical ensemble, describing a large system subject to hard and soft constraints, respectively, was recently shown to occur in large random graphs. Hard constraints must be met by every graph, soft constraints must be met only on average, subject to maximal entropy. In Squartini et al. (2015) it was shown that ensembles of random graphs are non-equivalent when the degrees of the nodes are constrained, in the sense of a non-zero limiting specific relative entropy as the number of nodes diverges. In that paper, the nodes were placed either on a single layer (uni-partite graphs) or on two layers (bi-partite graphs). In the present paper we consider an arbitrary number of intra-connected and inter-connected layers, thus allowing for modular graphs with a multi-partite, multiplex, block-model or community structure. We give a full classification of ensemble equivalence, proving that breakdown occurs if and only if the number of local constraints (i.e., the number of constrained degrees) is extensive in the number of nodes, irrespective of the layer structure. In addition, we derive a formula for the specific relative entropy and provide an interpretation of this formula in terms of Poissonisation of the degrees.

References in corpus (12)

• The structure and dynamics of multilayer networks
• Stochastic blockmodels and community structure in networks
• Statistical mechanics and dynamics of solvable models with long-range interactions
• Maximum likelihood: extracting unbiased information from complex networks
• Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
• An Introduction to the Thermodynamic and Macrostate Levels of Nonequivalent Ensembles
• Breaking of ensemble equivalence in networks
• Thermodynamic versus statistical nonequivalence of ensembles for the mean-field Blume-Emery-Griffiths model
• Entropies of complex networks with hierarchically constrained topologies
• Unbiased sampling of network ensembles
• Ensemble inequivalence in random graphs
• How likely is an i.i.d. degree sequence to be graphical?

Cited by in corpus (13)

• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Bayesian stochastic blockmodeling
• Reconstructing networks with unknown and heterogeneous errors
• Irreducible network backbones: unbiased graph filtering via maximum entropy
• Strong ensemble nonequivalence in systems with local constraints
• Fluctuating ecological networks: a synthesis of maximum-entropy approaches for pattern detection and process inference
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• Covariance structure behind breaking of ensemble equivalence in random graphs
• Entropy of labeled versus unlabeled networks
• Ensemble nonequivalence and Bose-Einstein condensation in weighted networks
• Asymptotic equivalence of probability measures and stochastic processes
• Description length of canonical and microcanonical models
• Ground States for Exponential Random Graphs