Ensemble nonequivalence in random graphs with modular structure
arXiv:1603.08759 · doi:10.1088/1751-8113/50/1/015001
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 (36)
- Community detection in graphs
- Random graphs with arbitrary degree distributions and their applications
- The structure and dynamics of multilayer networks
- Temporal Networks
- Stochastic blockmodels and community structure in networks
- Statistical mechanics and dynamics of solvable models with long-range interactions
- The statistical mechanics of networks
- Entropy measures for complex networks: Toward an information theory of complex topologies
- Statistical Mechanics of Multiplex Ensembles: Entropy and Overlap
- Growing multiplex networks
- Negative Specific Heat in Astronomy, Physics and Chemistry
- Cut-offs and finite size effects in scale-free networks
- Inequivalence of ensembles in a system with long range interactions
- Estimating and understanding exponential random graph models
- Negative heat capacity in the critical region of nuclear fragmentation: an experimental evidence of the liquid-gas phase transition
- Analytical maximum-likelihood method to detect patterns in real networks
- Maximum likelihood: extracting unbiased information from complex networks
- Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and measure levels
- Entropy of stochastic blockmodel ensembles
- An Introduction to the Thermodynamic and Macrostate Levels of Nonequivalent Ensembles
- Enhanced reconstruction of weighted networks from strengths and degrees
- Gravitational instability of isothermal and polytropic spheres
- Breaking of ensemble equivalence in networks
- Gibbs entropy of networks ensembles by cavity methods
- Thermodynamic versus statistical nonequivalence of ensembles for the mean-field Blume-Emery-Griffiths model
- Entropies of complex networks with hierarchically constrained topologies
- Phase transitions in a complex network
- Unbiased sampling of network ensembles
- The weighted random graph model
- Phase transitions in exponential random graphs
- Multiplexity versus correlation: the role of local constraints in real multiplexes
- Singularities in the entropy of asymptotically large simple graphs
- Exponential random graph models for networks with community structure
- Ensemble inequivalence in random graphs
- Low-temperature behaviour of social and economic networks
- 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