September 10, 2020
For random systems subject to a constraint, the microcanonical ensemble requires the constraint to be met by every realisation ("hard constraint"), while the canonical ensemble requires the constraint to be met only on average ("soft constraint"). It is known that for random graphs subject to topological constraints breaking of ensemble equivalence may occur when the size of the graph tends to infinity, signalled by a non-vanishing specific relative entropy of the two ensembles. We investigate to what extent breaking of ensemble equivalence is manifested through the largest eigenvalue of the adjacency matrix of the graph. We consider two examples of constraints in the dense regime: (1) fix the degrees of the vertices (= the degree sequence); (2) fix the sum of the degrees of the vertices (= twice the number of edges). Example (1) imposes an extensive number of local constraints and is known to lead to breaking of ensemble equivalence. Example (2) imposes a single global constraint and is known to lead to ensemble equivalence. Our working hypothesis is that breaking of ensemble equivalence corresponds to a non-vanishing difference of the expected values of the largest eigenvalue under the two ensembles. We verify that, in the limit as the size of the graph tends to infinity, the difference between the expected values of the largest eigenvalue in the two ensembles does not vanish for (1) and vanishes for (2). A key tool in our analysis is a transfer method that uses relative entropy to determine whether probabilistic estimates can be carried over from the canonical ensemble to the microcanonical ensemble, and illustrates how breaking of ensemble equivalence may prevent this from being possible.
Similar papers 1
July 9, 2021
Two ensembles are often used to model random graphs subject to constraints: the microcanonical ensemble (= hard constraint) and the canonical ensemble (= soft constraint). It is said that breaking of ensemble equivalence (BEE) occurs when the specific relative entropy of the two ensembles does not vanish as the size of the graph tends to infinity. The latter means that it matters for the scaling properties of the graph whether the constraint is met for every single realisatio...
November 12, 2017
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 fo...
July 8, 2018
Breaking of ensemble equivalence between the microcanonical ensemble and the canonical ensemble may occur for random graphs whose size tends to infinity, and is signaled by a non-zero specific relative entropy of the two ensembles. In [3] and [4] it was shown that breaking occurs when the constraint is put on the degree sequence (configuration model). It is not known what is the effect on the relative entropy when the number of constraints is reduced, i.e., when only part of ...
March 23, 2017
In this paper we consider a random graph on which topological restrictions are imposed, such as constraints on the total number of edges, wedges, and triangles. We work in the dense regime, in which the number of edges per vertex scales proportionally to the number of vertices $n$. Our goal is to compare the micro-canonical ensemble (in which the constraints are satisfied for every realisation of the graph) with the canonical ensemble (in which the constraints are satisfied o...
January 2, 2015
It is generally believed that, 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 of systems for which the microcanonical and canonical ensembles are not equivalent have been identified. A complete theory of this intriguing phenomenon is still missing. Here we show that ensemble nonequivalence can manifest itself also in random graphs with topologic...
July 20, 2018
In [18] we analysed a simple undirected random graph subject to constraints on the total number of edges and the total number of triangles. We considered the dense regime in which the number of edges per vertex is proportional to the number of vertices. We showed that, as soon as the constraints are \emph{frustrated}, i.e., do not lie on the Erd\H{o}s-R\'enyi line, there is breaking of ensemble equivalence, in the sense that the specific relative entropy per edge of the \emph...
December 13, 2023
We analyse the largest eigenvalue of the adjacency matrix of the configuration model with large degrees, where the latter are treated as hard constraints. In particular, we compute the expectation of the largest eigenvalue for degrees that diverge as the number of vertices $n$ tends to infinity, uniformly on a scale between $1$ and $\sqrt{n}$, and show that a weak law of large numbers holds. We compare with what was derived in our earlier paper "Central limit theorem for the ...
March 29, 2016
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 th...
September 14, 2013
Generalised degrees provide a natural bridge between local and global topological properties of networks. We define the generalised degree to be the number of neighbours of a node within one and two steps respectively. Tailored random graph ensembles are used to quantify and compare topological properties of networks in a systematic and precise manner, using concepts from information theory. We calculate the Shannon entropy of random graph ensembles constrained with a specifi...
January 31, 2011
We generate new mathematical tools with which to quantify the macroscopic topological structure of large directed networks. This is achieved via a statistical mechanical analysis of constrained maximum entropy ensembles of directed random graphs with prescribed joint distributions for in- and outdegrees and prescribed degree-degree correlation functions. We calculate exact and explicit formulae for the leading orders in the system size of the Shannon entropies and complexitie...