Ensemble nonequivalence in random graphs with modular structure

DOI10.1088/1751-8113/50/1/015001zbMATH Open1358.82014arXiv1603.08759OpenAlexW2325137483WikidataQ61387113 ScholiaQ61387113MaRDI QIDQ2965327FDOQ2965327

Authors: Diego Garlaschelli, Andrea Roccaverde, F. den Hollander 

Publication date: 2 March 2017

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1603.08759

Recommendations

• Modularity in several random graph models
• Modularity of Erdős-Rényi random graphs
• Modularity of Erdős-Rényi random graphs
• Covariance structure behind breaking of ensemble equivalence in random graphs
• A spectral signature of breaking of ensemble equivalence for constrained random graphs
• An ensemble of random graphs with identical degree distribution
• Random graph ensembles with many short loops
• Entropies of tailored random graph ensembles: bipartite graphs, generalized degrees, and node neighbourhoods
• On the equivalence between random graph models
• Ensemble inequivalence and absence of quasi-stationary states in long-range random networks

zbMATH Keywords

random graphconstraintsmultiplex networkstochastic blockmodelcommunity structuremicrocanonical ensembleequivalence versus non-equivalence

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Statistical thermodynamics (82B30) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31)

Cites Work

• Random graphs and complex networks. Volume 1
• A critical point for random graphs with a given degree sequence
• Estimating and understanding exponential random graph models
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The average distances in random graphs with given expected degrees
• Scale-Free Networks
• Low-temperature behaviour of social and economic networks
• Physics of Long-Range Interacting Systems
• The asymptotic number of labeled graphs with given degree sequences
• Nonequivalent statistical equilibrium ensembles and refined stability theorems for most probable flows
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Singularities in the entropy of asymptotically large simple graphs
• Phase transitions in a complex network
• Phase transitions in exponential random graphs
• Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums
• Large deviation principles and complete equivalence and nonequivalence results for pure and mixed ensembles
• The asymptotic number of non-negative integer matrices with given row and column sums
• Equivalence and nonequivalence of ensembles: thermodynamic, macrostate, and measure levels
• Gravitational instability of isothermal and polytropic spheres
• Unbiased sampling of network ensembles
• Analytical maximum-likelihood method to detect patterns in real networks
• How likely is an LLD degree sequence to be graphical?
• Complex networks from a physical perspective

Cited In (8)

• Asymptotic equivalence of probability measures and stochastic processes
• Complex networks: structure and functionality
• Is breaking of ensemble equivalence monotone in the number of constraints?
• Ensemble equivalence for dense graphs
• Covariance structure behind breaking of ensemble equivalence in random graphs
• Ground states for exponential random graphs
• Breaking of ensemble equivalence for dense random graphs under a single constraint
• A spectral signature of breaking of ensemble equivalence for constrained random graphs

This page was built for publication: Ensemble nonequivalence in random graphs with modular structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965327)