Chapter 5

Network Ensembles

In Chapters 2 and 4 we have already encountered various network models. All these
models have one feature in common: they are stochastic, i.e. they are based on some
degree of randomness. If we fix the parameters of a stochastic network model, all the
possible realizations (i.e. graphs) of the model itself define a so-called ensemble of
random graphs. Such ensemble is a collection1 G ¥ {G 1 , . . . ,G M } of M graphs (i.e.
adjacency matrices), where each graph G a is assigned a probability P(G a ) such that

X M
X
P(G) = P(G a ) = 1. (5.1)
G2G a=1

The number M is known as the cardinality of the ensemble G . Since, as we dis-

cussed in Chapter 1, any graph G is uniquely specified by its adjacency matrix, we
may think of G as an adjacency matrix with entries g i j . This notation applies to both
directed and undirected graphs, and generalizes the notation a i j and b i j introduced
in Eqs. (1.1) and 1.2, respectively, for these two classes of networks.
In this Chapter we study graph ensembles in more detail. Starting with some pre-
liminary observations about the Erdős-Rényi random graph and the Configuration
Model introduced in Chapters 2 and 4, respectively, we gradually arrive at the defini-
tion of so-called maximum-entropy ensembles of networks [8]. The importance of
maximum-entropy ensembles is the fact that, starting from local information, they
sample the space of graphs uniformly (under some constraint). This leads to un-
biased expectations for the higher-order properties of a network. This is property
if of crucial importance not only for the theoretical reason of redefining the Con-
figuration Model in order to allow for strongly heterogeneous degree sequences (as
we show in Section 5.3), but also for the practical problem of pattern detection in
real-world networks (as we will discuss in Chapter 10).

5.1 Equiprobability in the Erdős-Rényi model

To realize the importance of unbiasedness, we first highlight some important prop-
erties of the Erdős-Rényi (ER for short) model introduced in Chapter 2. Using the
adjacency matrix notation introduced in Chapter 1, we restate the model as follows.
1 Note that, for our purposes here, the symbol G denotes a different family of graphs than that denoted
in Chapter 2.

103
104 CHAPTER 5. NETWORK ENSEMBLES

Given a set of n vertices, each pair of vertices is connected by an undirected link with
probability p (independently of all other pairs). No self-loops are created. This im-
plies that, given p, the expected value of the entry g i j of the n £ n adjacency matrix
of a graph G generated by the model is
Ω
p i=
6 j
E(g i j ) ¥ hg i j i = (5.2)
0 i=j
P
where, here and in what follows, the expectation value x xP(X = x) of a (discrete)
random variable X is denoted by E(X ) or hX i. It therefore follows from Eq. (1.12) that
the expected number of undirected links is

n(n ° 1)
E(L u ) = p . (5.3)
2
So, once n is fixed, each given value of p produces a corresponding expected number
of links.
We might reverse the point of view and say that, if we would like the network to
have a given expected number of links E(L u ), then we should set the probability p to
the corresponding value
2E(L u )
p= . (5.4)
n(n ° 1)
This strategy is useful if, for instance, we want to compare the predictions of the ER
model with the observed properties of a real-world network G § having a given num-
ber n of vertices and a given number L §u of undirected links.2 In this perspective, the
empirical values n and L §u are treated as ‘constraints’, and the model is fitted to these
constraints by choosing for n the value observed in the real network and for p the
particular value
2L §u
p= . (5.5)
n(n ° 1)
Note that n will be necessarily finite, and we cannot use the results obtained for n !
1 in Chapter 2. However, large real-world networks imply that many asymptotic
results will hold at least approximately.
We already know, from the results of Chapter 1, that the comparison between
the real network and the ER model will be unsuccessful: the ER model is not able
to reproduce many properties of most real-world networks, in particular their broad
degree distribution and their large clustering coefficient. However, the ER model has
an important and desirable property: all the graphs with the same value of n and L u
are generated with the same probability, i.e. they are equiprobable. The proof of this
result is the goal of the following series of exercises.

Exercise 5.1 Write the cardinality M n of the ER ensemble, when n is the (fixed) num-
ber of vertices. Calculate the number M n (L u ) of simple and undirected graphs (with-
P
out self-loops) with n vertices and L u edges. Check that L u M n (L u ) = M n , where
2 Here and in what follows (especially in Chapter 10), we will often compare a particular real-world
network G § with an ensemble of model-generated graphs {G i }iM=1 . In such a situation, to avoid confusion
between empirical and model-generated (e.g. expected) properties, an asterisk will be used to denote the
particular value of the topological property X (G), when measured on the real-world network G § , i.e.
X § ¥ X (G § ). Note that, since the graph ensembles that we will consider have a fixed number of vertices,
there is no need to use an asterisk to denote the observed number n of vertices, as this number is constant
for both the real network and the model-generated ensemble.
5.2. EQUIPROBABILITY IN THE CONFIGURATION MODEL 105

the sum runs over all the possible values of L u in the set of graphs with n vertices.
Calculate the probability P(G) to generate a particular graph with binary adjacency
matrix G as a function of p in the ER model (write your answer explicitly in terms
of the entries {g i j } of the matrix G). Show that P(G) depends on G only through
P
L u (G) ¥ i < j g i j (note that this expression coincides with Eq. (1.12) adapted to the
notation used here). Write the resulting expression for P(G) as a function of p, n and
L u (G) explicitly. ‰

Homework 5.1 The above Exercise allows you to conclude that, in the ER model, all
graphs with the same value of n and L u are generated with equal probability. Use
this result to write the probability of generating any graph with n vertices and L u
undirected links. ‰

Another important property of the ER model is that its natural implementation

(connecting each pair of initially disconnected vertices with probability p, or equiv-
alently disconnecting each pair of initially connected vertices with probability 1° p)
is always feasible, i.e. it is possible to define computational algorithms that do not
‘get stuck’ and always lead to a realization of the model (see Chapter 3).

5.2 Equiprobability in the Configuration Model

With this section we move to the Configuration Model [15, 1, 2] (CM) discussed
also in Chapters 4 and 6. We show that both the equiprobability and the feasibility
property are violated in the simplest implementations of the model. This limitation,
which is further illustrated in Chapter 6, calls for a more sophisticated implemen-
tation of the CM. This will be provided in Section 5.3 in the context of maximum-
entropy ensembles of graphs.
As a preliminary observation, we notice that, in its abstract formulation, the CM
can be regarded as a generalization of the ER model in the following sense. The
ensemble of networks generated by the ER model is completely random except for
the (expected) number of links it generates, and this number is specified by fixing
the value of the connection probability p. In a similar manner, the ensemble of
networks generated by the CM model is completely random except for the degree
sequence it generates, and this degree sequence is specified from the beginning.
In other words, while in the ER model the only constraint (besides the number n
of vertices) is given by the number of links L u , in the CM model the constraint is the
entire degree sequence ~ k. However, it makes a big difference whether the constraint
is soft, i.e. enforced only as an average over all realizations (as in the ER) or sharp, i.e.
enforced on each individual realization separately (as in the implementations of the
CM model discussed in Chapter 4 and 6). In the first case one speaks of canonical
ensembles, while in the second case one speaks of microcanonical ensembles.
In the so-called ‘link stub reconnection’ implementation of the CM (more details
about this scheme are discussed in Chapter 6), the actual values of the number of
links and of the vertex degrees are fixed, not simply their expected values as in the
ER model (see Chapter 2). This implementation of the CM is therefore microcanon-
ical. A problem with the above implementation of the CM is that it typically gives
rise to undesired self-loops and multiple links between two vertices (more details
about this issue can be found in Chapter 6). This limitation makes the link stub re-
connection method unsatisfactory when an empirical degree sequence ~ k § is taken
as input.
106 CHAPTER 5. NETWORK ENSEMBLES

By contrast, the local rewiring algorithm (more details about this implementa-
tion can be found in Chapter 6) deliberately avoids the occurrence of multiple links
and self-loops in the randomized networks. This ensemble is also microcanonical,
like the link stub reconnection method. However, the two ensembles are different,
since double links and self-loops are absent here, while they might be present in the
link stub reconnection method. The local rewiring algorithm is biased, i.e. it does not
explore the space of graphs compatible with the degree constraints uniformly. The
currently proposed solutions to this problem (still within a microcanonical frame-
work) are computationally demanding and unpractical [3, 4].
Microcanonical ensembles are difficult to deal with mathematically. Indeed, in
the implementations of the CM discussed so far, it is very challenging (and currently
an open problem in general) to write down an exact for the probability of occurrence
of a given graph G in the ensemble, or equivalently the probability that two vertices
are connected, given the degree sequence. Moreover, microcanonical ensembles
suffer from the problems of bias discussed above. In what follows, we are going to
see whether these problems can be solved within a canonical formulation of the
Configuration Model.

5.2.1 The Chung-Lu model

Chung and Lu [14] proposed a variant of the CM where the graph ensemble is turned
from microcanonical into canonical. The main aim of their approach is that of ob-
taining an explicit mathematical expression for the probability that two vertices are
connected in the ensemble. Since imposing a fixed number of links seriously com-
plicates the analytical calculations in the microcanonical approach, Chung and Lu
reinterpreted the configuration model in a canonical form, as a natural extension
of the ER model. In this extension, not only the expected number of links, but the
whole expected degree sequence is specified.
In the undirected version of the Chung-Lu model, a link between two vertices i
and j is drawn with probability

k i§ k §j
pi j = if i 6= j , (5.6)
2L §u

and p i j = 0 if i = j . In Eq. (5.6), L §u is the observed number of links and k i§ , k §j are

the observed degrees of vertices i , j . Note that the (deterministic) observed degrees
are given as input to the model; on the other hand, the output of the model is an
ensemble of random networks where the degress are random variables. The expres-
sion for p i j in Eq. (5.6) is (at least apparently) reasonable, because the ensemble
average E(k i ) of the degree of each node i equals the observed degree k i§ :
P
X j k §j
E(k i ) = p i j = k i§ = k i§ 8i . (5.7)
j 2L §u

Exercise 5.2 Equation (5.7) is not entirely correct and there is actually a hidden ap-
proximation. Find it out and write the corresponding exact expression. Discuss in
which limit the exact expression reduces to Eq. (5.7). Using your exact expression,
write the relationship between the observed number of links L §u and the expected
number of links hL u i generated by the Chung-Lu model. Rearrange this expression
to write the difference L §u ° hL u i as a function of only the first and second moments
5.2. EQUIPROBABILITY IN THE CONFIGURATION MODEL 107

of the empirical degree distribution P (k) of the real-world network (recall our remark
about empirical degree distributions in the footnote of Subsection 1.2.1). Discuss the
effects of the heterogeneity (i.e. the breadth) of the empirical degree distribution. Dis-
cuss these effects for a scale-free empirical degree distribution of the form P (k) / k °∞
with 2 < ∞ ∑ 3. ‰

The factorized form of p i j in Eq. (5.6) implies that no degree correlations are
introduced. Indeed, the expected average nearest-neighbour degree (see Chapter 1,
Eq. 1.21) can be obtained as the following (approximated) expression:
°P ¢ P P
E j 6=i gi j k j j p i j k §j j k §2
j
E(k inn ) º º = P , (5.8)
E (k i ) k i§ j k §j

which is independent of i and equals the constant value k §2 /k § expected for uncor-
related networks (see Section 1.2.2).

Homework 5.2 Equation (5.8) contains two approximations. The first one is the
approximation of the expected value of a ratio as the ratio of the expected values of
the numerator and denominator.3 The second one is similar to the approximation
made in Eq.(5.7). Write a more refined expression for E(k inn ) that keeps the first ap-
proximation while avoiding the second one. Write a similar, more refined expression
for the expected value E(C i ) of the clustering coefficient of vertex i (see definition in
Chapter 1, Section 1.2.3). ‰

The model can be formulated also for directed graphs, by establishing a directed
link from vertex i to vertex j with probability

k iout § k ij n§
pi j = , (5.9)
L§
P P
where L § = i k ii n§ = i k iout § is the observed number of directed links, and k iout § , k ij n§
are the observed out-degree of vertex i and the observed in-degree of vertex j , re-
spectively. This choice ensures that hk ii n i = k ii n§ and hk iout i = k iout § for all vertices,
generalizing Eq. (5.7). Note, however, that this is not entirely correct and subject to
the same limitation discussed in Homework 5.2.

Exercise 5.3 Use Eq. (5.9) to write the expected number E(L $ ) ¥ hL $ i of reciprocated
links (see Chapter 1), and use the result to approximate the expected reciprocity hr i in
the Chung-Lu model (using an argument similar to that discussed in the footnote
to Exercise 5.2). Compare this value with the reciprocity of a directed Erdős-Rényi
random graph with the same number of vertices and directed links. ‰

The Chung-Lu model avoids by construction the occurrence of multiple links

and self-loops, since each pair of (distinct) vertices is considered only once. How-
ever, to ensure (as we should) that 0 ∑ p i j ∑ 1 for all i , j in Eqs. (5.6) and (5.9), we are
3 This approximation can be justified as follows. The empirical value k § of the denominator of k nn
i i
is reproduced ‘on average’ by the model, according to Eq. (5.7). Therefore we can approximate E(k inn )
nn §
by fixing the denominator of k i to the constant value k i . Similarly, the random variable k j in the
numerator can also be approximated with the constant k §j . This implies that the only effectively random
variables are the g i j ’s in the numerator.
108 CHAPTER 5. NETWORK ENSEMBLES

forced to consider only those degree sequences satisfying the constraint

v
q u n
uX
max{k i§ } ∑ 2L u = t k § ,
§
j (5.10)
i j =1

p p
and similarly maxi {k ii n§ } ∑ L § and maxi {k iout § } ∑ L § for directed graphs. A con-
nection ‘probability’ p i j > 1 can be regarded as the establishment of multiple links
between i and j , and this possibility is avoided only by imposing the above con-
straint. Therefore, in the Chung-Lu model the problem of the occurrence of multiple
links is circumvented by restricting the possible degree sequences to those satisfying
Eq. (5.10).
Unfortunately, the constraint expressed by Eq. (5.10) is very strong and is vio-
lated by most empirical degree distributions where a few hubs with very large degree
are present. This limitation prevents us from using the Chung-Lu model for most
empirical degree sequences. Since, as we mentioned, the violation of Eq. (5.10) can
be thought of as leading to multiple links, the problem of the Chung-Lu method is in
some sense the canonical counterpart of the problem encountered in the link stub
reconnection method.
p
Exercise 5.4 Consider a ‘marginal’ empirical degree sequence where maxi {k i§ } = 2L §u .
Discuss whether this is enough to ensure that Eq. (5.7) is a good approximation to the
correct expression you found in Homework 5.2. ‰

Homework 5.3 Assume G § is a regular network with n vertices where k i§ = z 8i

and check whether the condition (5.10) holds. Discuss what you obtain if you use
Eq. (5.6) to generate the graph ensemble in this case. Use your result in Homework 5.2
to write the expression for the difference L §u ° hL u i in this case. Then assume G § is a
star graph with n vertices, where a central vertex is connected to all the other vertices
(and these vertices are not directly connected to each other), and check whether the
condition (5.10) holds. Discuss what you obtain if you use Eq. (5.6) to generate the
graph ensemble in this case. ‰

5.2.2 The Park-Newman model

The limitation of the Chung-Lu model led Park and Newman [68] to modify the
canonical approach in such a way that no restriction on the desired degree sequence
is imposed, and at the same time no multiple links are generated. Park and Newman
started from the general problem of finding the form of the connection probability
p i j that generates a canonical ensemble of graphs with no multiple links and such
that two graphs with the same degree sequence are equiprobable, in the general
spirit of the Configuration Model.
As for the Chung-Lu model, we want the connection probability to be a function
p i j = p(x i , x j ) of some quantities x i , x j controlling the expected degrees of vertices i
and j . The quantities {x i }ni=1 play a role similar to that of the ‘desired’ degrees {k i }ni=1
in the Chung-Lu model, even if they turn out to be in general very different from the
expected degrees {hk i i}ni=1 and are therefore denoted by a different symbol.
The starting point is to write the probability P(G) of occurrence of a given graph
G (with adjacency matrix entries {g i j }) in the ensemble as a product, over all pairs of
vertices, of either p i j (if the link is realized, i.e. p i j = 1), or (1 ° p i j ) (if the link is not
5.2. EQUIPROBABILITY IN THE CONFIGURATION MODEL 109

Figure 5.1: a) Two undirected graphs G 1 and G 2 that have the same degree sequence and
differ only for the presence of the two edges (A, B ) and (D,C ) in graph G 1 and the presence of
the two edges (A,C ) and (D, B ) in graph G 2 . b) The corresponding situation for two directed
graphs with the same in- and out-degree sequences.

realized, i.e. g i j = 0):

Y Y
P(G) = pi j (1 ° p i j ) (5.11)
i < j |g i j =1 i < j |g i j =0
Y Y pi j
= (1 ° p i j )
i<j i < j |g i j =1 1 ° p i j
Y pi j
= P0 ,
i < j |g i j =1 1 ° pi j
Q
where P 0 ¥ i < j (1 ° p i j ) is a product over all vertex pairs and is therefore indepen-
dent of the particular graph G.
The above expression can be used to find the form of p i j warranting that two
graphs G 1 and G 2 with the same degree sequence are equiprobable. Looking for in-
stance at Fig. 5.1a, the requirement that the two undirected graphs G 1 and G 2 occur
with the same probability P(G 1 ) = P(G 2 ) translates into the requirement
p AB p DC p AC p DB
= , (5.12)
1 ° p AB 1 ° p DC 1 ° p AC 1 ° p DB
since the two graphs are identical except for the subgraphs defined by the four ver-
tices A, B,C , D. For the above expression to hold for all quadruples A, B,C , D, the
form of p i j must be such that p i j /(1 ° p i j ) = f i f j , where f i is a quantity depending
on i alone. Recalling that p i j = p(x i , x j ), we see that f i = f (x i ). Rearranging for p i j ,
we have
f (x i ) f (x j )
p i j = p(x i , x j ) = . (5.13)
1 + f (x i ) f (x j )
Any form of f (x) is compatible with the requirement in Eq. (5.12). Since different
choices can be mapped to each other via a redefinition of x, we can choose the sim-
plest nontrivial4 function f (x) = x for later convenience. This yields
xi x j
p(x i , x j ) = . (5.14)
1 + xi x j
4 Note that the simplest choice f (x) = const would lead to the result p = const as in the ER random
ij
graph model, where we lose control over the expected degree sequence. This still ensures that any two
graphs with the same degree sequence are equiprobable, but in a trivial way, since in the ER model ac-
tually any two graphs with the same number of links are equiprobable (see Section 5.1). So the simplest
nontrival choice for the CM is f (x) = x.
110 CHAPTER 5. NETWORK ENSEMBLES

Equation (5.14) is of fundamental importance. It ensures that 0 ∑ p i j ∑ 1 with no

restriction on the degree sequence, thus overcoming the limitation of the Chung-Lu
approach. Moreover, it ensures that the desired property of unbiasedness, that we
proved for the ER model, is extended to the CM. In other words, the probability to
generate a graph G depends only on the degree sequence of G. This implies that
graphs with the same degree sequence are equiprobable, i.e. they are sampled uni-
formly. This nicely extends the properties we proved for the ER (see Homework 5.1
and Exercise 5.1) to the CM.

Homework 5.4 Show that the graph probability P(G) depends on G only through
P
{k i (G)} ¥ { j 6=i g i j }, implying that graphs with the same degree sequence are equiprob-
able. Show that this is not true if the probability p i j of the Chung-Lu model is used.
‰

We now come to an important result. The expected degrees read

X X xi x j
E(k i ) = pi j = 8i . (5.15)
j 6=i j 6=i 1 + xi x j

Let us compare the above expression to the corresponding Eq. (5.3) valid for the
Erdős-Rényi model. Both expressions provide the expected value of the natural
quantities (L u and ~
k, respectively) defining the two models. Just like its simpler
counterpart, Eq. 5.15 can be used to generate an ensemble of networks with degree
distribution determined by the (free) parameters {x i }. Alternatively, if one wants the
expected degree sequence to coincide with the observed degree sequence ~ k § of a
§
real-world network G , Eq. (5.15) can be turned into the following system of n non-
linear coupled equations, where ~k § are known quantities and ~ x are the unknowns:
X xi x j
k i§ = 8i . (5.16)
j 6=i 1 + xi x j

The solution to the above equation, denoted as ~ x § , produces an expected degree

~ §
sequence equal to the observed one k . We will exploit this possibility extensively
in Chapter 10. Equation (5.16) is therefore analogous to Eq. (5.5) for the Erdős-Rényi
model.
When the model is used to generate random networks once the value of ~ x is
given, Eq. (5.15) suggests that the expected degree of a vertex with a given value of
x can be written as a function of x, after summing over the variables for the other
vertices. This can be best appreciated by considering a continuous approximation
where the distribution of x over all vertices is assumed to be the continuous density
æ(x), and Eq. (5.15) is rewritten in integral form:
Z1
xy
Ex (k) ¥ hk(x)i = (n ° 1) dy æ(y). (5.17)
0 1+xy

The behaviour of hk(x)i is proportional to x for small values of x and then ‘saturates’
to the maximum value n ° 1 for large x, consistently with the requirement of no
multiple edges or self-loops.
Park and Newman [68] studied the model assuming a power-law distribution
æ(x) / x °ø with various values of the exponent ø (see Fig. 5.2). They found that
this assumption has two important consequences on the topology: firstly, the de-
gree distribution P (k) behaves as a power-law with the same exponent ø of æ(x) for
5.2. EQUIPROBABILITY IN THE CONFIGURATION MODEL 111

Figure 5.2: Average degree hk(x)i of vertices versus x corresponding to the choice æ(x) / x °ø
for three values of ø. The trend is initially linear and then saturates to the asymptotic value
k ! n ° 1 (atfer ref. [68]).

small values of x, but then diplays a cut-off ensuring k ∑ n ° 1 (see Fig. 5.3a). Sec-
ondly, the average nearest neighbour degree turns out to be a decreasing function
of the degree (see Fig. 5.3b). As expected, the absence of multiple links generates
an ‘effective repulsion’ between high-degree vertices, resulting in some ‘spurious’
disassortativity. Moreover, the studied mechanism generates a k nn (k) which is not
strictly a power-law, even if it approaches a power-law behaviour asymptotically (see
Fig. 5.3b). These results allowed Park and Newman to confirm that, as suggested by
Maslov et al. [15] by making use of the local rewiring algorithm (see Section 6.6.2),
part of the disassortativity displayed by the Internet can be accounted for by this
mechanism.
The Park-Newman model leads to a very interesting analogy with the statistical
physics of quantum particles, i.e. microscopic particles that obey quantum mechan-
ics and are therefore subject to some ‘discreteness’ constraint. The analogy relates
links of binary graphs to so-called Fermi particles or ‘fermions’. In quantum physics,
it is found that each microstate of a system can only be occupied by one fermion at
a time (this is known as the exclusion principle). In jargon, the ‘occupation number’
of a microstate in a system of fermions can be only 0 (no particles in that state) or
1 (one particle in that state). In this analogy, each pair of vertices i and j can be
regarded as a ‘microstate’ whose occupation number is g i j = 1 if a ‘particle’ (link) is
there, and g i j = 0 if not. The requirement of no multiple links (g i j ∑ 1) is equivalent
to the exclusion principle that there is at most one particle per state, and leads to
Eq. (5.12) which is the analogous of the so-called Fermi distribution.

Homework 5.5 Let us consider the ‘sparse graph limit’ where x i x j ø 1 8i , j . In this
regime, Eq. (5.14) can be approximated as

p(x i , x j ) º x i x j . (5.18)

Show that, with the above approximation,

p the system of equations (5.16) decouples
and the solution is x i§ = k i§ / 2L §u 8i . ‰
112 CHAPTER 5. NETWORK ENSEMBLES

Figure 5.3: a) Cumulative degree distribution P > (k) corresponding to the choice æ(x) / x °ø
for three values of ø. b) Average nearest neighbour degree k̄ nn (k) for the same three choices
of the exponent ø. Here isolated symbols correspond to numerical simulations, while solid
lines are the analytical predictions (after ref. [68]).

The above exercise implies that the model defined by Eq. (5.18) is equivalent to
the Chung-Lu model defined by Eq. (5.6). As already discussed in Section 5.2.1, in
this limit the expected degrees are approximately equal to the observed ones, and
no degree correlations are introduced. Therefore the spurious disassortativity dis-
appears in this limit. Curiously, in the above ‘quantum’ analogy this regime corre-
sponds to the ‘classical limit’ where the discreteness of the quantum world can be
neglected, and the Fermi distribution can be replaced by the Boltzmann distribu-
tion which (in a suitable representation) has the expression (5.18).

We finally briefly describe the directed case. Now the probability that a directed
link from i to j is there is a function p i j = p(x i , y j ) of two quantities x i and y j play-
ing a role analogous to that of the desired out- and in-degrees k iout , k ij n in the di-
rected version of the Chung-Lu model defined in Eq. (5.9). By looking at Fig. 5.1b
and requiring that graphs with the same in- and out-degree sequence are equiprob-
able, we are led to a condition analogous to Eq. (5.12). This implies that in this
case p i j /(1 ° p i j ) = f i g j where f i = f (x i ) and g j = g (y j ) are functions of x i and y j
alone respectively. Again, all nontrivial choices can be mapped onto the linear case
through a suitable redefinition of x and y. Therefore we have

xi y j
p i j = p(x i , y j ) = (5.19)
1 + xi y j

and in this case the sparse graph limit yields

p i j º xi y j , (5.20)

which is equivalent p to the directed version

p of the Chung-Lu model defined in Eq. (5.9),
with x i = k iout § / L § and y j = k ij n§ / L § .
5.3. MAXIMUM-ENTROPY ENSEMBLES 113

5.3 Maximum-entropy ensembles

All the examples in the previous section highlight that even a conceptually simple
idea, i.e. generating a random ensemble of networks with a specified degree se-
quence, can encounter big difficulties when naively implemented. The Park-Newman
approach solves the practical and conceptual problems of other implementations
of the CM by ensuring that the ensemble is properly sampled, so that any inference
about the higher-order properties (e.g. the assortativity) is unbiased, just like for the
ER model.
At this point, we might ask a natural question: if we consider a different con-
straint (other than the number of links or the degree sequence), how can we be sure
that we end up with an appropriate method to generate the ensemble? Is there some
constructive method to generate graph ensembles with given constraints?
In this section, we show that such a method exists and is based on the Maximum
Entropy Principle.

5.3.1 The Maximum Entropy Principle

In information theory, an important measure of the ‘uncertainty’, or ‘unpredictabil-
ity’ of a random process is provided by Shannon’s entropy. If P(G) is the probability
of the outcome G, Shannon’s entropy is defined (up to a proportionality constant
which is irrelevant for our later purposes) as
X
S ¥° P(G) ln P(G), (5.21)
G2G

where the sum runs over all the M possible outcomes of the process.
A deterministic (certain) process, i.e. one for which one outcome has probability
one while all other outcomes have probability zero, gives S = 0, which is the mini-
mum possible entropy. By contrast, a completely unpredictable (uniform) process,
i.e. one where all the outcomes have exactly the same probability P(G) = M °1 , gives
the maximum value S = ln M .
Another important property of the entropy is additivity: if the event G requires
the simultaneous occurrence (intersection) of two events G 1 and G 2 (i.e. G = G 1 \G 2 )
and if these events are independent, i.e. the joint probability P(G) = P(G 1 \ G 2 ) can
be factorized as P(G) = P1 (G 1 )P2 (G 2 ) where P1 and P2 are the marginal probabilities
P
for the individual events G 1 and G 2 , then S = S 1 +S 2 where S i = ° G i Pi (G i ) ln Pi (G i )
denotes the entropy of the individual event G i (i = 1, 2) and the sum runs over the
possible outcomes of such event.

Exercise 5.5 Prove the last statement. Use the result to calculate the entropy of the
ER model with n vertices as a function of the probability p. ‰

If we measure Shannon’s entropy on a graph ensemble, this will provide us with

a measure of the degree of randomness that we are left with, once we enforce the
constraints that define the model itself [8]. If the constraints represent structural
properties taken from observations (like the number of links or the degree sequence
in the ER and CM respectively), Shannon’s entropy will quantify the residual uncer-
tainty that we are left with about the network, after we measure those properties.
An important application of Shannon’s entropy is the Maximum Entropy Princi-
ple, especially as developed by Jaynes [5]. According to this principle, whenever we
114 CHAPTER 5. NETWORK ENSEMBLES

have only partial information (summarized in the knowledge of a set of m observ-

ables {x Æ }m
Æ=1 ) about a system, then our least biased inference or ‘best guess’ about
the (unknown) rest of the system shoul be obtained by finding the probability P(G)
that maximizes S, subject to the known constraints. This reflects the fact that, ex-
cept for the known constraints, we are maximally ignorant about the system. The
constraints are expressed in the form
X
E(x Æ ) ¥ x Æ (G)P(G) = x Æ 8Æ, (5.22)
G2G

where x Æ is the observed (known) value of the Æ-th property. Note that the con-
straints are enforced canonically, i.e. as ensemble averages. An additional constraint
is given by the normalization of the probability, expressed by Eq.(5.1). Introducing
one Lagrange multiplier µÆ for each constraint x Æ (plus an additional multiplier for
the normalization constraint) and taking the functional derivative of S with respect
to P, one can show that the result of the constrained maximization of S is
~
e °H (G,µ)
P(G|~
µ) = , (5.23)
Z (~µ)

where
m
X
H (G, ~
µ) ¥ µÆ x Æ (G) (5.24)
Æ=1

is a linear combination of the constraints that, by analogy with (statistical) physics,

we will call energy or Hamiltonian, while
X ~
Z (~
µ) ¥ e °H (G,µ) (5.25)
G2G

is the so-called partition function, which is enforcing the normalization constraint

for the probability.
The above expressions coincide with those of traditional statistical physics. In-
deed, the beauty of the Maximum Entropy approach is that of showing that the en-
tirety of statistical physics can be reformulated exactly as an inference problem from
limited information. Indeed, from the knowledge of only a few macroscopic quanti-
ties (like the total energy) of a system, statistical physics looks for a least biased esti-
mate of the microscopic properties of the system, in terms of the probability P(G, ~ µ)
of the microscopic configurations. This consideration establishes a fascinating con-
nection between information theory and statistical physics [5].
In the context of networks, we are interested in doing the same operation. This
establishes another beautiful connection, this time to random graph theory. From
the knowledge of a few aggregate properties {x Æ }m Æ=1 (such as the degree sequence),
we want to construct completely random ensembles of graphs. Applying the Maxi-
mum Entropy principle to graph ensembles leads to the so-called Exponential Ran-
dom Graph (ERG) models, which were first introduced in social network analysis
[22, 8] to generate ensembles of graphs matching a given set of observed topological
properties. ERGs were then ‘rediscovered’ within an explicit statistical-mechanics
framework [19, 6, 7, 8] where it was showed that traditional tools borrowed from
statistical physics could successfully contribute to investigate and sometimes even
solve them explicitly [19]. For a comprehensive treatment of the Maximum-Entropy
approach to network modeling and related applications, see [8].
5.3. MAXIMUM-ENTROPY ENSEMBLES 115

Homework 5.6 Prove the following relation:

1 @Z (~µ) @≠(~µ)
E(x Æ ) = ° = , (5.26)
~
Z (µ) @µ Æ @µ Æ

where we have introduced the free energy

≠(~
µ) ¥ ° ln Z (~
µ). (5.27)

In the following, we consider specific examples of ERGs and we show that the
ER model and the Park-Newman implementation of the CM can be recovered as
particular cases of maximum-entropy ensembles. Moreover, we will show that the
general method allows to extend the approach to different constraints.

5.3.2 Simple undirected graphs

We start by considering the simple but quite general case when the Hamiltonian can
be expressed in the form [8]
X
H (G, ~
µ) = µi j g i j . (5.28)
i<j

Note that in this model the dimension of ~ µ equals the number n(n ° 1)/2 of pairs of
nodes and the total energy H (G, ~
µ) is the sum of the energies µi j of the links realized
in G. Each energy µi j can be regarded as the ‘cost’ of placing a link between i and j .
With this choice the partition function reads
X °H (G,~µ) X ° P µ g X Y °µ g
Z (~
µ) = e = e i<j i j i j = e ij ij (5.29)
{g i j } {g i j } {g i j } i < j
Y X Y Y
= e °µi j g i j = (1 + e °µi j ) = z(µi j ),
i < j g i j =0,1 i<j i<j

where we have introduced the vertex-pair partition function

z(µ) ¥ 1 + e °µ . (5.30)

Finally, the ‘free energy’ is

X X
≠(~
µ) = ° ln Z (~
µ) = ° ln z(µi j ) = !(µi j ) (5.31)
i<j i<j

where
!(µ) = ° ln z(µ). (5.32)
Equations (5.28-5.32) completely define the model. From the free energy it is pos-
sible to compute all the relevant quantities. For instance, the expected ‘occupation
number’ of the pair of vertices i , j , representing the probability that such vertices
are connected, is
@!(µi j ) 1
p i j = E(g i j ) = = (5.33)
@µi j 1 + e µi j
and the expected total number of links in the network is
≠X Æ X
E(L u ) = gi j = pi j . (5.34)
i<j i<j
116 CHAPTER 5. NETWORK ENSEMBLES

ER Random Graph

We now show that the ER random graph model can be recovered as particular cases
of the exponential model defined by the Hamiltonian (5.28). This is obtained when
all energies are equal [8]:
µi j = µ. (5.35)
With such a choice, the Hamiltonian reads
X
H (G, µ) = µ g i j = µL u (G). (5.36)
i<j

This corresponds to m = 1, x 1 = L u and µ1 = µ in Eq. (5.24), and we are therefore only

requiring that the expected number of links hL u i can be set to any desired value L u
by tuning the parameter µ. This requirement corresponds to the ER random graph
model. Looking at Eq. (5.33), we have

1
pi j = p = (5.37)
1 + eµ
and, as expected, we recover the constant form for the connection probability char-
acterizing the ER model.

Configuration Model

We now consider the additive case [8]

µ i j = µi + µ j , (5.38)

which results in
X X X
H (G, ~
µ) = (µi + µ j )g i j = µi g i j = µi k i (G). (5.39)
i<j i 6= j i

Note that in this case we are requiring to set the expected value of each degree hk i i
to any desired value k i by tuning the corresponding parameter µi . In other words,
we are fixing the desired degree sequence and we expect this case to be equivalent to
the version of the configuration model described in Section 5.2.2. Indeed, Eq. (5.33)
now reads
1
pi j = (5.40)
1 + e µi +µ j
and by introducing x i ¥ e °µi , it is easy to see that the above equation is the same as
Eq. (5.13), corresponding to the Park-Newman version of the Configuration Model.
This confirms that that version is unbiased, in accordance with the Maximum En-
tropy Principle. Other variants (such as the Chung-Lu one) cannot be derived from
a Maximum Entropy approach, thus showing their biasedness.

5.3.3 * Directed graphs

We now briefly consider the directed case. The Hamiltonian (5.28) becomes
X
H (G, ~
µ) = µi j g i j (5.41)
i 6= j
5.3. MAXIMUM-ENTROPY ENSEMBLES 117

and calculations analogous to those presented above allow to write the partition
function as Y Y
Z (~
µ) = z(µi j ) = (1 + e °µi j ) (5.42)
i 6= j i 6= j

and the free energy as

X X
≠(~
µ) = ° ln Z (~
µ) = ° ln z(µi j ) = !(µi j ). (5.43)
i 6= j i 6= j

The probability that a directed link from i to j is there is

@!(µi j ) 1
p i j = E(g i j ) = = , (5.44)
@µi j 1 + e µi j

and the expected number of directed links is

X
E(L) ¥ hLi = pi j . (5.45)
i 6= j

In the constant case µi j = µ, we recover a directed version of the ER random

graph model:
X 1
H (G, µ) = µ g i j = µL(G) ) pi j = p = . (5.46)
i 6= j 1 + eµ

In the more general additive case, we have µi j = Æi +Ø j , since for directed graphs
µi j can be asymmetric. These two parameters control the in- and the out-degree of
each vertex separately:
X X£ § 1
H (G, ~
µ) = (Æi +Ø j )g i j = Æi k iout (G)+Øi k ii n (G) ) pi j = . (5.47)
i 6= j i 1 + e Æi +Ø j

This choice is equivalent to the directed version of the configuration model defined
in Eq. (5.19), where x i ¥ e °Æi , y j ¥ e °Ø j [8].
Bibliography

[1] M.E.J. Newman, S.H. Strogatz and D.J. Watts, Phys. Rev. E 64, 026118 (2001).

[2] M. Molloy and B. Reed, Random Structures and Algorithms 6, 161 (1995).

[3] A.C.C Coolen, A. De Martino, A. Annibale, J. Stat. Phys. B 136, 1035–67 (2009).

[4] E.S. Roberts, A.C.C. Coolen, Phys. Rev. E 85, 046103 (2012).

[5] E. T. Jaynes, Physical review 106(4), 620 (1957).

[6] J. Berg and M. Lässig, Phys. Rev. Lett. 89, 228701 (2002).

[7] Z. Burda, J. Jurkiewicz and A. Krzywicki, Phys. Rev. E 69, 026106 (2004).

[8] D. Garlaschelli and T. Squartini, Maximum-Entropy Networks: pattern detec-

tion, network reconstruction, and graph combinatorics (Springer Briefs in Com-
plexity, Springer International Publishing, 2017).

118