12th MSJ-SI,Fukuoka, Japan, 31/07–09/08, 2019.

Frank den Hollander
Mathematical Institute, Leiden University

II. Equivalence

STRUCTURE AND FUNCTIONALTYCOMPLEX NETWORKS:micro-canonical ensemble
canonical ensemble

The former fixes the energy of the system, the latter fixes
the average energy of the system, with temperature as thecontrol parameter.

I.
II.

Two important examples are:

Systems consisting of a very large number of interacting
particles can be described by statistical ensembles, i.e.,
probability distributions on spaces of configurations.

§ STATISTICAL PHYSICSThe canonical ensemble is easier to compute with thanthe micro-canonical ensemble, because the constraint is
soft rather than hard.

The two ensembles capture physically different microscopic
situations. For both the entropy is maximal subject to theconstraint.

GibbsThis assumption is certainly reasonable for systems withinteractions that are short-ranged. But, counterexamples
have been found for systems with interactions that arelong-ranged.

In textbooks of statistical physics the two ensembles areassumed (!) to be thermodynamically equivalent, i.e., tohave the same macroscopic behaviour. Here the idea isthat for large systems the energy is typically close to its
average value.

A realisation of a large random graphIn this talk we will be interested in large random graphs,i.e., the two ensembles live on the set SN of all simple
graphs with N vertices where N → ∞.

§ COMPLEX NETWORKS~~ ∗,
1/ΩC~ ∗ if C(G)=C0else,1~∗ ~e − θ · C(G),N (θ~∗)

where N (θ~∗) is the normalising constant and θ~∗ is to bePcan~~∗chosen such that G∈SN C(G)PN (G) = C .

can (G) =PN

II. The canonical ensemble is defined by~~ ∗}|.
=C
where ΩC~ ∗ = |{G ∈ SN : C(G)mic (G) =PN(

I. The micro-canonical ensemble is defined by~ on SN , and a specific
Given are a vector-valued function C~ ∗ called the constraint.
vector CDEFINITIONSWhich of the two should be used to model a real-world
network depends on the a priori knowledge that is available
about the network.

can models a random graph of which no information• PN
is available other than the average constraint.

mic models a random graph of which no information• PN
is available other than the constraint.

INTERPRETATION

Touchette 2015

N

1 X
mic (G) log
PN=N G∈Stends to zero as N → ∞.

mic | P cansN PNN

mic (G)PN
can (G)PN!

mic and P can are said to be equivalent when their relativePNN
entropy per vertex defined byENSEMBLE EQUIVALENCE



1=log
N

mic (G∗ )PN
can (G∗ )PN!

~ ∗) = C~ ∗. This greatly simplifies
for any G∗ such that C(Gthe computation, since we need not carry out the sum overSN and only need to compute with a single graph G∗.

mic | P cansN PNN~~∗
Because in both ensembles all G ∈ SN such that C(G)=C
have the same probability, we get the simpler formulaDiego Garlaschelli
Michel Mandjes
Andrea Roccaverde
Tiziano Squartini
Nicos Starreveld(Leiden & Lucca)(Amsterdam)(Leiden)(Lucca)(Amsterdam)

What follows is joint work withIn the remainder of the lecture we illustrate breakingof ensemble equivalence via a number of examples.

Example with N = 6 and d~N = (1, 3, 1, 3, 2, 4)

Each vertex gets a prescribed number of half-edges, which
are paired off randomly to form edges.

§ CONSTRAINT ON THE DEGREE SEQUENCE

1≤i≤N

Suppose that the degrees are moderate, corresponding towhat is called the sparse regime:√∗
N → ∞.
max di = o( N ),~ ∗ = d~ ∗ = (d∗ , . . . , d∗ ) ∈ NN .
C10N
NConsider a graph G = (V, E) with vertex set V = {1, . . . , N }and edge set E such that all the vertices have prescribeddegrees. In other words, consider the constraintg(k)k ∈ N0 .

k∼12 log kk→∞k!
g(k) = log k −k ,k e

N1 XfN =δd∗ = empirical degree distribution.
N i=1 iDefine

Let

N →∞

lim kfN − f k`1(g) = 0
= kf k`1(g).

There is breaking of ensemble equivalence for all f 6= δ0.

Interpretation: Each vertex with degree k contributes anamount g(k) to the relative entropy.

mic | P cans∞ = lim sN PN
NN →∞



for some limiting degree distribution f . ThenSuppose thatTHEOREM 1:

• Canonical ensemble:
vertices have a random degree.

• Micro-canonical ensemble:
vertices have a fixed degree.

It turns out that g(k) is the relative entropy of Dirac(k)with respect to Poisson(k). What this says is that, in thelimit as N → ∞,The proof is based on graph counting (micro-canonical)
and percolation theory (canonical).

√

For k-regular graphs:

5-regular graphs∞ = g(k) > 0.

fN = δk with k = o( N ).

Example 1:s∞ ≈graph with hubs

1+1log(2π) > 0.
22(τ − 1)

For scale-free graphs:

with kcutoff (N ) = o( N ) and τ ∈ (1, ∞) a tail exponent.

√fN (k) = CN k−τ , 1 ≤ k ≤ kcutoff (N ),Example 2:

N2, T2∗

N3!!

,T1∗, T2∗ ∈ [0, 1].

1log
2
N →∞ N

where we scale by N 2 instead of N .

s∞ = limmic (G∗ )PN
can (G∗ )PN!

,This corresponds to the so-called dense regime, in which
the number of edges per vertex is of order N . The quantityof interest is now

= T1∗

!

~ ∗ = (number of edges, number of triangles)
CInteresting behaviour shows up when we pick

§ CONSTRAINT ON THE TOTAL NUMBER
OF EDGES AND TRIANGLES

( 12 , 0)edge density T1∗∗2

T2∗ = T1 3

T2∗ = T1∗3(1,0)

T2∗ = T1∗ (2T1∗ − 1)

(1,1)

s∞ = ?

s∞ > 0s∞ = 0s∞ > 0Radin and Sadun 2015

Between the blue curves the edge-triangle densities are admissible.

(0,0)(0, 18 )(0,1)

THEOREM 2:

triangle density T2∗

Chatterjee and Varadhan 2011

We derive a variational formula for s∞ with the help of thelarge deviation principle for graphons associated with theErdős-Rényi random graph.

Borgs, Chayes, Lovász ≥ 2008

The proof is based on the theory of graphons, which arecontinuum limits of adjacency matrices of graphs.

Breaking of ensemble equivalenceoccurs when (T1∗, T2∗) is frustrated.

where C +, C − are computable functions of T1∗ that are,however, not so easy to identify.

↓0lim −2/3 s∞(T1∗, T1∗3−) = C − ∈ (0, ∞),↓0lim −1 s∞(T1∗, T1∗3+) = C + ∈ (0, ∞),For T1∗ ∈ (0, 1),THEOREM 3:

What happens close the line T2∗ = T1∗3? It turns out thatanomalous behaviour shows up:

Breaking occurs when the number of constraints isextensive or when the constraints are frustrated.

We have obtained a complete classification of breaking of
ensemble equivalence in random graphs with constraints
on the degree sequence, respectively, the total number ofedges and triangles.

§ CONCLUSION

F. den Hollander, M. Mandjes, A. Roccaverde, N.J. Starreveld,Random Struct. Alg. 2019.

D. Garlaschelli, F. den Hollander, A. Roccaverde,J. Stat. Phys. 2018.

F. den Hollander, M. Mandjes, A. Roccaverde, N.J. Starreveld,
Electronic J. Prob. 2018.

D. Garlaschelli, F. den Hollander, A. Roccaverde,J. Phys. A: Math. Theor. 50 (2017) 015001.

D. Garlaschelli, F. den Hollander, A. Roccaverde,
Nieuw Archief voor Wiskunde 5/16 (2015) 207–209.

D. Garlaschelli, F. den Hollander, J. de Mol, T. Squartini,
Phys. Rev. Lett. 115 (2015) 268701.

§ LITERATURE