For a random graph subject to a topological constraint, the microcanonical ensemble requires the constraint to be met by every realisation of the graph (‘hard constraint’), while the canonical ensemble requires the constraint to be met only on average (‘soft constraint’). It is known that breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-zero specific relative entropy of the two ensembles. In this paper we analyse a formula for the relative entropy of generic discrete random structures recently put forward by Squartini and Garlaschelli. We consider the case of a random graph with a given degree sequence (configuration model), and show that in the dense regime this formula correctly predicts that the specific relative entropy is determined by the scaling of the determinant of the matrix of canonical covariances of the constraints. The formula also correctly predicts that an extra correction term is required in the sparse regime and in the ultra-dense regime. We further show that the different expressions correspond to the degrees in the canonical ensemble being asymptotically Gaussian in the dense regime and asymptotically Poisson in the sparse regime (the latter confirms what we found in earlier work), and the dual degrees in the canonical ensemble being asymptotically Poisson in the ultra-dense regime. In general, we show that the degrees follow a multivariate version of the Poisson–Binomial distribution in the canonical ensemble.

Covariance structure behind breaking of ensemble equivalence in random graphs

Garlaschelli D;
2018-01-01

Abstract

For a random graph subject to a topological constraint, the microcanonical ensemble requires the constraint to be met by every realisation of the graph (‘hard constraint’), while the canonical ensemble requires the constraint to be met only on average (‘soft constraint’). It is known that breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-zero specific relative entropy of the two ensembles. In this paper we analyse a formula for the relative entropy of generic discrete random structures recently put forward by Squartini and Garlaschelli. We consider the case of a random graph with a given degree sequence (configuration model), and show that in the dense regime this formula correctly predicts that the specific relative entropy is determined by the scaling of the determinant of the matrix of canonical covariances of the constraints. The formula also correctly predicts that an extra correction term is required in the sparse regime and in the ultra-dense regime. We further show that the different expressions correspond to the degrees in the canonical ensemble being asymptotically Gaussian in the dense regime and asymptotically Poisson in the sparse regime (the latter confirms what we found in earlier work), and the dual degrees in the canonical ensemble being asymptotically Poisson in the ultra-dense regime. In general, we show that the degrees follow a multivariate version of the Poisson–Binomial distribution in the canonical ensemble.
File in questo prodotto:
File Dimensione Formato  
2018_Covariance Structure Behind Breaking of Ensemble Equivalence in Random Graphs.pdf

accesso aperto

Tipologia: Versione Editoriale (PDF)
Licenza: Creative commons
Dimensione 576.18 kB
Formato Adobe PDF
576.18 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11771/4332
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
social impact