text:
# Principles of statistical mechanics of random networks

## I Introduction

Quite recently, it has been realized that the study of the structure of networks, which was formerly “a private domain” of mathematical graph theory , is actually a field of statistical physics . Most achievements of physicists in the field of random networks  (structural and topological aspects) are empirical findings and simple ideas, which were demonstrated by using very particular models. One of main questions that arise is: What is the nature of complex, non-Poisson degree distributions, which were observed in many real networks? (Degree of a vertex is the total number of its connections.) However, few efforts were made to develop a general statistical theory of networks (see Refs. ). Without such a theory, the above question cannot be answered. Furthermore, the structure of the statistical theory of random networks can be related to a zero-dimensional field theory and to a mean-field description of simplicial gravity . A condensation phase transition, which occurs in equilibrium networks, is close to that which occurs in branched polymers .

In this paper we focus on equilibrium network ensembles, which are less studied. We construct statistical ensembles of random uncorrelated networks in a natural way and establish a one-to-one correspondence between them and known construction procedures. One of conclusions is that, in equilibrium networks, fat-tailed degree distributions (in particular, power-law ones) are possible only starting from some critical value of the average degree. Above this critical point, a finite fraction of edges are in a “condensed state”, i.e. are attached to an infinitely small fraction of vertices. This situation for equilibrium networks contrasts with that for growing ones, were fat-tailed degree distributions are realized over a wide range of a control parameter without any condensate.

The keystone of network science are construction procedures. Erdös and Rényi constructed ensembles of random graphs with a Poisson degree distribution by adding edges at random to a fixed number of vertices . When the total number of edges $`L`$ is fixed, this provides a canonical ensemble. When one fixes the probability that two vertices are connected, the procedure produces a grand canonical ensemble.

To obtain equilibrium random graphs with an arbitrary degree distribution $`\mathrm{\Pi }\left(q\right)`$, a different statistical ensemble was introduced  (see also Ref. ). Roughly speaking, these are graphs, maximally random under the restriction that their degree distribution is equal to a given $`\mathrm{\Pi }\left(q\right)`$ (see below). Here we demonstrate that this “static” construction produces a microcanonical ensemble, and construct equivalent (in the thermodynamic limit, i.e. $`N\mathrm{}`$) canonical and grand canonical ensembles as limiting equilibrium states of simple dynamical processes.

In statistical mechanics, equilibrium ensembles arise as infinite-time limiting distributions of some ergodic dynamics. Here we present naturally looking graph evolution models, using the generalization of the concept of “preferential linking”, which was introduced in . We consider two kinds of a random network evolving under the mechanism of preferential linking and displaying ergodic behavior. The latter means that an evolving ensemble finally becomes equilibrium, and final statistical weights for the complete set of graphs of the ensemble are independent of time and initial state. The specific rule of preferential linking that we use allows us to construct equilibrium statistical ensembles with an arbitrary $`\mathrm{\Pi }\left(q\right)`$.

The paper is organized as follows. In Section II we introduce the main notions of random graph theory. The next Section III is a key one: we establish a connection between ergodic evolution and statistical ensembles for undirected graphs. In Section IV these results are generalized to the case of directed graphs. Section V is devoted to networks with a fat-tailed degree distribution, decaying slower than exponential. The results are discussed in the last Section VI. Technical details are described in three Appendices.

## II Definitions and main notions

A graph $`g`$ is a set of $`N`$ vertices connected by $`L`$ edges, directed or undirected. It may be displayed as a set of points, with some pairs connected by one or more lines, with or without arrows. For analytic purposes, a graph is represented by an $`N\times N`$ adjacency matrix $`\widehat{g}`$, whose elements $`g_{ij}`$ are numbers of edges connecting vertices $`i`$ and $`j`$.

An undirected graph (with undirected edges), is represented by a symmetric adjacency matrix, $`g_{ij}=g_{ji}`$. In this case it is convenient to set diagonal elements $`g_{ii}`$ to be equal to twice the number of unit-length loops. Then, the adjacency matrix $`\widehat{g}^{(1)}`$ of an undirected graph $`G_1`$, obtained from a directed graph $`G`$ with an adjacency matrix $`\widehat{g}`$ by replacing all directed edges with undirected ones, is simply $`g_{ij}^{(1)}=g_{ij}+g_{ji}`$.

Mayer’s graphs are the ones without multiple connections and one-vertex loops. Their adjacency matrix elements satisfy the conditions: $`g_{ij}^2=g_{ij}`$, $`g_{ii}=0`$.

Vertex in-degree $`r_i`$ of a vertex $`i`$ in a directed graph is a number of incoming edges of the vertex $`i`$, $`r_i=_jg_{ij}`$. Similarly, out-degree $`s_i`$ is a number of edges, outgoing from the vertex $`i`$, $`s_i=_jg_{ji}`$. Vertex degree for undirected graph is $`q_i=_jg_{ij}=_jg_{ji}`$.

A statistical ensemble of graphs is defined by choosing of a set $`G`$ of graphs and a rule that associates some statistical weight (unnormalized measure) $`P(g)>0`$ with any graph $`gG`$. Then the ensemble average of any quantity $`A\left(g\right)`$ that depends on properties of a graph is $`A=Z^1_{gG}A\left(g\right)P\left(g\right)`$, where $`Z`$ is a partition function, $`Z_{gG}P\left(g\right)`$. For instance, let $`A\left(g\right)`$ be the total number of vertices of in-degree $`r`$ and out-degree $`s`$:

$$N(r,s;g)=\underset{i=1}{\overset{N}{}}\delta \left[r_i\left(g\right)r\right]\delta \left[s_i\left(g\right)s\right].$$
(1)
Here $`N`$ is the total number of vertices in the graph $`g`$ (we consider only ensembles with a fixed number of vertices). The probability that a randomly chosen vertex has in-degree $`r`$ and out-degree $`s`$ (a degree distribution) is

$$\mathrm{\Pi }(r,s)\frac{N(r,s)}{N}=\frac{1}{N}\underset{i=1}{\overset{N}{}}\delta \left[r_i\left(g\right)r\right]\delta \left[s_i\left(g\right)s\right].$$
(2)
For an undirected graph, one can define the number of vertices with a given degree $`q`$

$$N\left(q\right)=\underset{i=1}{\overset{N}{}}\delta \left[q_i\left(g\right)q\right],$$
(3)
and a degree distribution

$$\mathrm{\Pi }\left(q\right)=\frac{N\left(q\right)}{N}=\frac{1}{N}\underset{i=1}{\overset{N}{}}\delta \left[q_i\left(g\right)q\right].$$
(4)
In this paper we consider statistical ensembles with non-Mayer’s graphs allowed. The advantage of this assumption is that one can associate a statistical weight with a graph by using the same rules, as for the contribution of the corresponding Feynman diagram in an appropriately chosen zero-dimensional field theory (see ).

Note that we consider labeled graphs. That is, two graphs, $`g`$ and $`g^{}`$, which differ only by numeration of vertices, are treated as different ones.

## III Evolution of graphs and statistical ensembles: Undirected graphs

In this section we discuss how ensembles of undirected graphs arise as a result of the network evolution. For simplicity, we restrict ourselves to undirected graphs—generalization to the case of directed ones is presented in the next section. We define the statistical weights of the canonical and grand canonical ensembles of random networks as a limiting equilibrium distribution of a process, during which one graph $`gG`$ of the ensemble transforms to another graph $`g^{}G`$ with probability $`W(g^{},g)dt`$. The statistical weights $`P(g,t)`$ evolve according to the master equation

$$_tP(g,t)=\underset{g^{}G}{}\left[W(g,g^{})P(g^{},t)W(g^{},g)P(g,t)\right].$$
(5)
An equilibrium ensemble is a stationary one. $`P(g,t)=P(g)`$ is independent of $`t`$, where statistical weights are determined by the detailed balance condition (absence of “currents”):

$$W(g,g^{})P(g^{})=W(g^{},g)P(g).$$
(6)
This equilibrium ensemble exists if and only if the set of “hopping rates” $`W(g,g^{})`$ satisfies two conditions: (i) For any pair of graphs $`g,g^{}G`$, there exists a sequence of graphs $`g_1,g_2,\mathrm{}g_nG`$ such that

$$W(g^{},g_n)W(g_n,g_{n1})\mathrm{}W(g_2,g_1)W(g_1,g)0.$$
(7)
(ii) For any sequence of graphs $`g_1,g_2,\mathrm{}g_nG`$, the equality:

$$W(g_1,g_2)W(g_2,g_3)\mathrm{}W(g_{n1},g_n)W(g_n,g_1)=W(g_1,g_n)W(g_n,g_{n1})\mathrm{}W(g_3,g_2)W(g_2,g_1),$$
(8)
is valid.

These conditions ensure that (a) ascribing an arbitrary statistical weight to some graph, one can obtain statistical weights of all other graphs up to a constant multiple, and (b) this definition is unambiguous: the weights are independent of the ways connecting initial graph with all the other ones. To satisfy condition (ii), it is sufficient to assume the factorization:

$$W(g^{},g)=V_f(g^{})V_i(g).$$
(9)
Our dynamical constructions, which are presented below, satisfy this condition. We use simple natural assumptions about the evolution rates $`W(g^{},g)`$, but our choice is not unique (e.g., see a “Metropolis algorithm” from Refs. ).

We consider the following equilibrium statistical ensembles of graphs with a fixed total number of vertices $`N`$. A statistical ensemble is a set of graphs $`G`$ plus rules that determine statistical weighs $`P\left(g\right)`$ for all graphs $`gG`$.

1. A microcanonical ensemble .

* Let $`N\left(q\right)`$ be a sequence of non-negative integers such that $`0<_qN\left(q\right)=N<\mathrm{}`$. $`G_{MC}`$ is the set of all graphs of size $`N`$, for which number of vertices of degree $`q`$ is equal to $`N\left(q\right)`$.
* To each graph $`gG_{MC}`$ ascribe the weight

$$P_{MC}\left(g\right)=N^L\underset{i=1}{\overset{N}{}}\frac{q_i!}{g_{ii}!!}\underset{j<k=1}{\overset{N}{}}\frac{1}{g_{jk}!}.$$
(10)

This is a “static” construction. These statistical weights follow from pure combinatorics. They are just the number of possible ways to obtain a given graph $`gG_{MC}`$ by connecting together $`N`$ vertices with degrees $`q_1,q_2,\mathrm{}q_N`$ (see proof in Appendix A). The multiple $`N^L`$ is introduced to ensure the extensiveness of the “free energy”, $`\mathrm{ln}Z_{MC}`$. Eq. (10) implies, that edges in the graph are distinguishable. Note that if only Mayer graphs are allowed, all graphs in this ensemble have equal weights. In the thermodynamic limit , the microcanonical ensemble is described by a sequence of values $`\left\{\mathrm{\Pi }\left(q\right)\right\}`$ or, which is the same, $`\left\{N\left(q\right)\right\}`$ (in particular, this includes the mean degree $`\overline{q}2L/N`$).

To construct canonical and grand canonical ensembles we use the processes of rewiring  or of deletion/creation of edges , and the idea of preferential linking . We assume that the probability that an edge becomes attached to a vertex $`i`$ depends only on the degree $`q_i`$ of this vertex. This probability is determined by some preference function $`f\left(q\right)`$.

2. A canonical ensemble.

* The set $`G_C`$ consists of all graphs with $`N`$ vertices and $`L`$ edges.
* At each step of the evolution, one of the ends of a randomly chosen edge is rewired to a preferentially chosen vertex $`k`$. Let the rate of this process be $`f\left(q_k\right)`$ . The limiting stationary statistical weights give $`P_C\left(g\right)`$. In the thermodynamic limit, the canonical ensemble is described by $`\left\{f\left(q\right)\right\}`$ and $`\overline{q}2L/N`$. Note that the multiplication of $`f\left(q\right)`$ by a constant, $`f\left(q\right)Cf\left(q\right)`$, is simply the rescaling of time, $`tt/C`$. It does not influence equilibrium properties.

3. A grand canonical ensemble.

* The set $`G_{GC}`$ consists of all graphs with any number of edges and a fixed number of vertices, $`N`$.
* There are two parallel processes in this case: edges are deleted and emerge permanently. Randomly chosen edges are deleted at a rate $`\lambda N`$ ($`\lambda `$ is the inverse lifetime of an edge, $`\lambda `$ is fixed as $`N\mathrm{}`$, i.e., in the thermodynamic limit). Edges between vertices $`i`$ and $`j`$ emerge at a rate $`f\left(q_i\right)f\left(q_j\right)`$. To ensure the correspondence with the canonical ensemble, let the deletion rate of tadpoles be $`2\lambda N`$.

In the thermodynamic limit, the grand canonical ensemble is described by $`\left\{f\left(q\right)\right\}`$ and $`\lambda `$.

Let us obtain, for example, statistical weights for the canonical ensemble. Let an edge $`(i,j)`$ of a graph $`g`$ be rewired to $`(i,k)`$ in a graph $`g^{}`$. We have the following balance equation for the statistical weights of these two graphs:

$$g_{ik}^{}f\left(q_j^{}\right)P_C\left(g^{}\right)=g_{ij}f\left(q_k\right)P_C\left(g\right).$$
(11)
Here quantities with a prime mark are referred to the graph $`g^{}`$, $`q_j^{}=q_j1`$, $`g_{ik}^{}=g_{ik}+1+\delta _{ik}`$ (adding a tadpole increases $`g_{ii}`$ by two). The multiple $`g_{ij}`$ is present, because rewiring any of $`(i,j)`$ edges gives the same result. One can look for the solution in the form:

$$P_C\left(g\right)=N^L\underset{i=1}{\overset{N}{}}p\left(q_i\right)\chi _d\left(g_{ii}\right)\underset{j<k=1}{\overset{N}{}}\chi \left(g_{jk}\right),$$
(12)
where $`p`$, $`\chi `$ and $`\chi _d`$ are some functions of an integer argument. Substituting Eq. (12) into Eq. (11), we obtain at $`ij`$, $`ik`$: $`p\left(q+1\right)=f\left(q\right)p\left(q\right)`$, $`\chi \left(g+1\right)=\chi \left(g\right)/\left(g+1\right)`$. Setting $`i=j`$ or $`i=k`$, we get: $`\chi _d\left(g+2\right)=\chi _d\left(g\right)/\left(g+2\right)`$. The constant multiple $`N^L`$ is introduced to ensure the “free energy” to be extensive variable, $`\mathrm{ln}Z_CN`$. Thus we obtain:

$`p\left(q\right)`$ $`=`$ $`{\displaystyle \underset{r=0}{\overset{q1}{}}}f\left(r\right)\text{for}q>0,p\left(0\right)=1,`$ (13)
$`\chi \left(g\right)`$ $`=`$ $`{\displaystyle \frac{1}{g!}},\chi _d\left(g\right)={\displaystyle \frac{1}{g!!}}.`$ (14)
Then we have

$$P_C\left(g\right)=N^L\underset{i=1}{\overset{N}{}}\frac{p\left(q_i\right)}{g_{ii}!!}\underset{j<k=1}{\overset{N}{}}\frac{1}{g_{jk}!}.$$
(15)
Comparing Eq. (15) with Eq. (10), one can see that

$$P_C\left(g\right)=P_{MC}\left(g\right)\underset{i=1}{\overset{N}{}}\frac{p\left(q_i\right)}{q_i!}.$$
(16)
Analogously, for the grand canonical ensemble we have

$$P_{GC}\left(g\right)=\left(\lambda N\right)^{L(g)}\underset{i=1}{\overset{N}{}}\frac{p\left(q_i\right)}{g_{ii}!!}\underset{j<k=1}{}\frac{1}{g_{jk}!}=\lambda ^{L\left(g\right)}P_C\left(g\right),$$
(17)
where $`p\left(q\right)`$ is again given by Eq. (14). Here $`L(g)`$ is the number of edges in a graph $`g`$.

One can present the statistical weights in a different form. For the canonical ensemble, one can write

$$P_C\left(g\right)=\underset{i=1}{\overset{N}{}}\frac{1}{g_{ii}!!}\underset{j<k=1}{}\frac{1}{g_{jk}!}\mathrm{exp}\left[\underset{q=0}{\overset{\mathrm{}}{}}N(q,g)\mathrm{ln}p\left(q\right)\right],$$
(18)
The corresponding form for the grand canonical ensemble includes the additional term $`L\left(g\right)\mathrm{ln}\left(\lambda N\right)`$ in the exponential:

$$P_{GC}\left(g\right)=\underset{i=1}{\overset{N}{}}\frac{1}{g_{ii}!!}\underset{j<k=1}{}\frac{1}{g_{jk}!}\mathrm{exp}\left[L\left(g\right)\mathrm{ln}\left(\lambda N\right)+\underset{q=0}{\overset{\mathrm{}}{}}N(q,g)\mathrm{ln}p\left(q\right)\right].$$
(19)
The above constructions are reasonable only if these ensembles are equivalent in the thermodynamic limit. Here we show that this is the case. One can see from Eq. (18) that statistical weights of graphs with the same sequences $`\left\{N(q,g),q=0,1,2,\mathrm{}\right\}`$ are equal. Then the canonical ensemble is equivalent to the microcanonical one with the same $`\mathrm{\Pi }(q)=N\left(q\right)/N`$ if fluctuations of $`N\left(q\right)`$ are negligibly small in the thermodynamic limit: $`\left[N^2\left(q\right)N\left(q\right)^2\right]/N\left(q\right)^20`$ as $`N\mathrm{}`$. To study these fluctuations, one may use the following standard relations:

$`{\displaystyle \frac{\delta \mathrm{ln}Z\left(\left\{p\left(\stackrel{~}{q}\right)\right\}\right)}{\delta \mathrm{ln}p\left(q\right)}}=N\left(q\right),`$ (20)
$`{\displaystyle \frac{\delta ^2\mathrm{ln}Z\left(\left\{p\left(\stackrel{~}{q}\right)\right\}\right)}{\delta \mathrm{ln}p\left(q\right)\delta \mathrm{ln}p\left(q^{}\right)}}=N\left(q\right)N\left(q^{}\right)N\left(q\right)N\left(q^{}\right),`$ (21)
which follows from Eq. (18) and the definition of the partition function. Equation (21) holds both for the canonical and the grand canonical ensembles.

Notice that the transition from a microcanonical ensemble to canonical one is basically the Legendre transform , where some thermodynamically conjugated fields are used. In our case, the microcanonical ensemble is characterized by a sequence of $`\left\{N\left(q\right)\right\}`$, and the conjugated fields are $`\left\{\mathrm{ln}p\left(q\right)\right\}`$. In the grand canonical ensemble, $`\mathrm{ln}\left(\lambda N\right)`$ is analogous to a standard chemical potential or, more precisely, to $`\mu /kT`$.

The partition function of the grand canonical ensemble is

$$Z_{GC}(N,\lambda ,\left\{p\left(q\right)\right\})=\underset{L=0}{\overset{\mathrm{}}{}}\lambda ^LZ_C(N,L,\left\{p\left(q\right)\right\}).$$
(22)
Let us introduce a zero-dimensional theory of real scalar field $`x`$ with the action

$$S\left(x\right)=\frac{\mathrm{\Lambda }}{2}x^2\varkappa \mathrm{\Phi }\left(x\right),$$
(23)
where

$$\mathrm{\Phi }\left(x\right)=\underset{q}{}\frac{p\left(q\right)}{q!}x^q.$$
(24)
Then the generating functional of this theory can be expanded in the series of all possible Feynman diagrams, whose contributions coincide with statistical weights:

$$Z(\mathrm{\Lambda },\varkappa ,\left\{p\left(q\right)\right\})=\sqrt{\frac{\mathrm{\Lambda }}{2\pi }}_{\mathrm{}}^+\mathrm{}𝑑x\mathrm{exp}S\left(x\right)=\underset{N=0}{\overset{\mathrm{}}{}}\frac{\left(\varkappa \right)^N}{N!}Z_{GC}(N,\mathrm{\Lambda }/N,\left\{p\left(q\right)\right\}).$$
(25)
Then we come to the expression

$$Z_{GC}(N,\lambda ,\left\{p\left(q\right)\right\})=\sqrt{\frac{N\lambda }{2\pi }}_{\mathrm{}}^+\mathrm{}𝑑x\mathrm{exp}\left(\frac{N\lambda }{2}x^2\right)\left[\mathrm{\Phi }\left(x\right)\right]^N.$$
(26)
From Eq. (22) it follows that

$$Z_C(N,L,\left\{p\left(q\right)\right\})=_C\frac{d\lambda }{2\pi i}\lambda ^{L1}Z_{GC}(N,\lambda ),$$
(27)
where the integration contour $`C`$ has no singularities outside of it. Substituting Eq. (26) into Eq. (27), changing the order of integration, and calculating the integral over $`\lambda `$, we have

$$Z_C(N,L,\left\{p\left(q\right)\right\})=N^L\left(2L1\right)!!_c\frac{dx}{2\pi i}x^{2L1}\left[\mathrm{\Phi }\left(x\right)\right]^N.$$
(28)
where the contour $`c`$ encircles the point $`x=0`$. This derivation is rather formal, because convergence of the integrals for the generating functional $`Z`$, Eq. (25), and for the grand canonical partition functions, Eq. (26), depends on the properties of $`\mathrm{\Phi }\left(x\right)`$. These integrals are well defined and converge if the diagrammatic series for the corresponding partition functions, or for the generating functional, converge. Note that the partition function of the grand canonical ensemble does not exist if either $`\mathrm{ln}\mathrm{\Phi }\left(x\right)`$ is growing faster than $`x^2`$ at $`x\mathrm{}`$, or $`\mathrm{\Phi }\left(x\right)`$ has singularities at the real axis (series (24) has a finite radius of convergence). But for the canonical ensemble, the partition function does exist for every $`\mathrm{\Phi }\left(x\right)`$, which is analytic at $`x=0`$. Indeed, for the canonical ensemble, the partition function is a sum over a finite set of graphs, while for the grand canonical ensemble, it is an infinite series, which may diverge. More detailed derivation of Eqs. (26) and (28) is presented in Appendix B. Note also that the expression (28) coincides with that for the partition function of the backgammon (“balls in boxes”) model .

As $`N\mathrm{}`$, one can use the saddle point expression:

$$Z_C(N,L,\left\{p\left(q\right)\right\})\left(\frac{\overline{q}}{ex_s^2}\right)^L\left[\mathrm{\Phi }\left(x_s\right)\right]^N,$$
(29)
where $`\overline{q}=2L/N`$ is the average vertex degree and the saddle point $`x_s`$ is given by the equation

$$\overline{q}=x_s\frac{\mathrm{\Phi }^{}\left(x_s\right)}{\mathrm{\Phi }\left(x_s\right)}.$$
(30)
We omitted a preexponential saddle-point multiple in Eq. (29) as insignificant in the thermodynamic limit. For grand canonical ensemble we have:

$$Z_{GC}(N,\lambda ,\left\{p\left(q\right)\right\})=\mathrm{exp}\left(\frac{N\lambda }{2}x_s^2\right)\left[\mathrm{\Phi }\left(x_s\right)\right]^N,$$
(31)
$$\lambda x_s=\frac{\mathrm{\Phi }^{}\left(x_s\right)}{\mathrm{\Phi }\left(x_s\right)}.$$
(32)
From the fact that the logarithm of the partition function of the canonical ensemble is extensive, $`\mathrm{ln}Z_{GC}N`$ (see Eqs. (21) and (29)), it follows that $`N\left(q\right)N\left(q^{}\right)N\left(q\right)N\left(q^{}\right)=𝒪\left(N\right)`$, so that the canonical ensemble is indeed equivalent to the microcanonical one. Analogously, using the relations

$`L={\displaystyle \frac{\mathrm{ln}Z_{GC}}{\mathrm{ln}\lambda }},`$ (33)
$`L^2L^2={\displaystyle \frac{^2\mathrm{ln}Z_{GC}}{(\mathrm{ln}\lambda )^2}}=𝒪\left(N\right),`$ (34)
one finds that the fluctuations of the number of edges $`L`$ in the grand canonical ensemble disappear in the thermodynamic limit. This demonstrates the equivalence of the grand canonical and canonical ensembles, if $`f\left(q\right)`$ grows not very fast with $`q`$, which allows the existence of the grand canonical ensemble. Their parameters are related as: $`\lambda =Lx_s^2/N=\overline{q}x_s^2`$.

From Eqs. (21), (24) and (29)–(32), one sees that

$$\mathrm{\Pi }\left(q\right)=\frac{N\left(q\right)}{N}=\frac{p\left(q\right)x_s^q}{q!\mathrm{\Phi }\left(x_s\right)}.$$
(35)
This is valid for both the canonical and grand canonical ensembles. Note that Eq. (35) may be also derived directly from the evolution equation for the degree distribution (see Appendix C). Equations (30) or (32), and (35) fix the one-to-one correspondence between the degree distribution $`\mathrm{\Pi }\left(q\right)`$, which determines the microcanonical ensemble, and the set of parameters $`(\overline{q},\left\{f\left(q\right)\right\})`$ or, equivalently, $`(\overline{q},\left\{p\left(q\right)\right\})`$ (see Eq. (14)). From Eqs. (14) and (35), it follows $`\mathrm{\Pi }\left(q+1\right)/\mathrm{\Pi }\left(q\right)=f\left(q\right)x_s/\left(q+1\right)`$. Then one can correspond the microcanonical ensemble which is described by a degree distribution $`\mathrm{\Pi }\left(q\right)`$ with the canonical and grand canonical ensembles characterized by (i)

$$f\left(q\right)=\left(q+1\right)\frac{\mathrm{\Pi }\left(q+1\right)}{\mathrm{\Pi }\left(q\right)},$$
(36)
($`f\left(q\right)`$ is defined up to an arbitrary multiple), and (ii) by $`\overline{q}=_qq\mathrm{\Pi }\left(q\right)`$ for the canonical ensemble, or $`\lambda =\overline{q}`$ for the grand canonical one.

## IV Generalization to the case of directed graphs

A microcanonical ensemble of directed graphs is characterized by a distribution function $`\mathrm{\Pi }(r,s)`$, which is the probability that a randomly chosen vertex has in-degree $`r`$ and out-degree $`s`$. More precisely, one must define non-negative integers $`N_n(r,s)`$ with the following properties: $`0<N_n=_{r,s}N_n(r,s)<\mathrm{}`$, $`N_n\mathrm{}`$ and $`N_n(r,s)/N_n\mathrm{\Pi }(r,s)`$ as $`n\mathrm{}`$. For a directed graph, we also must require, that total in- and out-degrees are equal: $`_{r,s}\left(rs\right)N_n(r,s)=0`$. Then for each $`n`$, we introduce the ensemble of directed graphs with $`N_n(r,s)`$ vertices of in-degree $`r`$ and out-degree $`s`$, $`N_n`$ vertices in total, connected in all possible ways. To each this graph $`g`$, we ascribe for a statistical weight equal to the number of possible ways to construct the graph $`g`$:

$$P_{MC}\left(g\right)=\underset{i=1}{\overset{N}{}}r_i!s_i!\underset{j,k=1}{\overset{N}{}}\frac{1}{g_{jk}!}.$$
(37)
The limit of such a sequence at $`n\mathrm{}`$ would be the microcanonical ensemble with a given degree distribution $`\mathrm{\Pi }(r,s)`$.

Canonical and grand canonical ensembles may be introduced quite analogously to what it had been done for undirected graphs. For example, the canonical ensemble may be introduced by using the process of rewiring one end of an edge. There are two differences from the undirected graph constructions: (i) we introduce two generalized preferential attachment functions, $`f_1`$ for rewiring the outgoing end of an edge, and $`f_2`$ for rewiring the incoming end, and (ii) in general, these function depend on both the in- and out-degrees of the destination vertex. Applying detailed balance conditions for transitions between graphs $`g_1`$ and $`g_2`$ (edge $`ij`$ rewires to $`ik`$), and between graphs $`g_3`$ and $`g_4`$ (edge $`ij`$ rewires to $`ik`$), we obtain the relations:

$`g_{ik}^{(2)}f_1(r_j^{(2)},s_j^{(2)})P_C\left(g_2\right)=g_{ij}^{(1)}f_1(r_k^{(1)},s_k^{(1)})P_C\left(g_1\right),`$ (38)
$`g_{ij}^{(2)}=g_{ij}^{(1)}1,g_{ik}^{(2)}=g_{ik}^{(1)}+1,r_j^{(2)}=r_j^{(1)}1,s_j^{(2)}=s_j^{(1)},r_k^{(2)}=r_k^{(1)}+1,s_k^{(2)}=s_k^{(1)};`$ (39)
$`g_{ki}^{(4)}f_2(r_j^{(4)},s_j^{(4)})P_C\left(g_4\right)=g_{ji}^{(3)}f_2(r_k^{(3)},s_k^{(3)})P_C\left(g_3\right),`$ (40)
$`g_{ki}^{(4)}=g_{ki}^{(3)}+1,g_{ji}^{(4)}=g_{ji}^{(3)}1,r_j^{(4)}=r_j^{(3)},s_j^{(4)}=s_j^{(3)}1,r_k^{(4)}=r_k^{(3)},s_k^{(2)}=s_k^{(1)}+1.`$ (41)
One can look for the solution of the above equations in the form:

$$P_C\left(g\right)=\underset{i=1}{\overset{N}{}}p(r_i,s_i)\underset{j,k=1}{\overset{N}{}}\chi \left(g_{jk}\right).$$
(42)
Then we have:

$`p(r+1,s)`$ $`=`$ $`f_1(r,s)p(r,s),p(r,s+1)=f_2(r,s)p(r,s);`$ (43)
$`\chi \left(g+1\right)`$ $`=`$ $`{\displaystyle \frac{\chi \left(g\right)}{g+1}}.`$ (44)
Applying subsequently Eqs. (43) in different order, we have:

$`p(r+1,s+1)=f_1(r,s+1)f_2(r,s)p(r,s)=f_2(r+1,s)f_1(r,s)p(r,s).`$

This means that the preferential linking functions $`f_1`$ and $`f_2`$ cannot be chosen arbitrary but must satisfy the condition

$$f_1(r,s)f_2(r,s+1)=f_1(r+1,s)f_2(r,s),$$
(45)
which is actually a consequence of the detailed balance condition (8).

The solution of Eqs. (43) is constructed in the following way. Let us consider a 2D square lattice. We associate $`f_1(r,s)`$ with each horizontal bond connecting sites $`(r,s)`$ and $`(r+1,s)`$, and associate $`f_2(r,s)`$ with the vertical bond, connecting sites $`(r,s)`$ and $`(r,s+1)`$. Let $``$ be some path connecting points $`(0,0)`$ with $`(r,s)`$. Then,

$$p(r,s)=p(0,0)\underset{}{}f_\alpha ^d(\rho ,\sigma ).$$
(46)
Here $`(\rho ,\sigma )`$ are coordinates of points along the path $``$, $`\alpha =1\left(2\right)`$ for the horizontal (vertical) direction, and $`d=+1\left(1\right)`$ if the bond is passed in its positive (negative) direction. The condition (45) ensures the independence of the product in Eq. (46) of the path $``$. In fact, this is the condition of the potentiality (zero vorticity) of the vector field $`\mathrm{ln}f_\alpha `$ defined on the square lattice. Then $`\mathrm{ln}p`$ is a potential for this field, that is $`\mathrm{ln}f_\alpha `$ is a lattice gradient of $`\mathrm{ln}p`$ (see Eq. (43)). The arbitrary multiple $`p(0,0)`$ may be set, e.g., to $`1`$. Solution of Eq. (44) is simple:

$$\chi \left(g\right)=\frac{1}{g!}.$$
(47)
The grand canonical ensemble may be constructed quite analogously to what it had been done for undirected graphs. Two opposite processes are introduced: one is of edge creation, at a rate $`f_2(r_i,s_i)f_1(r_j,s_j)`$ for the edge, going from the vertex $`i`$ to $`j`$, the other is of the edge removal, at a rate $`\lambda N`$. Again, $`f_1`$ and $`f_2`$ must satisfy the condition (45) to ensure the equilibrium character of a stationary state. The statistical weight of a graph is given by the expression

$$P_{GC}\left(g\right)=e^{\lambda L\left(g\right)}\underset{i=1}{\overset{N}{}}p(r_i,s_i)\underset{j,k=1}{\overset{N}{}}\frac{1}{g_{jk}!}.$$
(48)
The derivation of the integral representation of the partition function is quite similar to that for undirected graphs, but Feynman’s diagrams with directed lines now are generated by complex fields. We introduce a complex scalar field $`x`$, and write the action:

$`S(x,x^{})`$ $`=`$ $`\mathrm{\Lambda }\left|x\right|^2\varkappa \mathrm{\Phi }(x,x^{}),`$ (49)
$`\mathrm{\Phi }(x,x^{})`$ $`=`$ $`{\displaystyle \underset{r,s=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{p(r,s)}{r!s!}}x^r\left(x^{}\right)^s.`$ (50)
Then the following generating functional of this field theory will produce all possible graphs with any number of vertices as its Feynman diagrams. Their contributions are the same as statistical weights of graphs in the grand canonical ensemble (48) with $`\lambda =\mathrm{\Lambda }/N`$, except the additional multiples $`\left(\varkappa \right)^N/N!`$. Therefore, one can write:

$$Z(\varkappa ,\mathrm{\Lambda },\left\{p(r,s)\right\})=\frac{\mathrm{\Lambda }}{\pi }𝑑x𝑑x^{}\mathrm{exp}S(x,x^{})=\underset{N=0}{\overset{\mathrm{}}{}}\frac{\left(\varkappa \right)^N}{N!}Z_{GC}(N,\mathrm{\Lambda }/N,\left\{p(r,s)\right\}),$$
(51)
where the integration is over the entire complex plane (compare with Eq. (25)). Therefore,

$$Z_{GC}(N,\lambda ,\left\{p(r,s)\right\})=\frac{N\lambda }{\pi }𝑑x𝑑x^{}\mathrm{exp}\left(N\lambda \left|x\right|^2\right)\left[\mathrm{\Phi }(x,x^{})\right]^N.$$
(52)
In Eqs. (51), (52) one should treat $`x`$ and $`x^{}`$ as independent integration variables when actually calculating the integrals. The partition function of the canonical ensemble is given by

$$Z_C(N,L,\left\{p(r,s)\right\})=\frac{L!}{N^L}_{C_1}\frac{dx}{2\pi i}_{C_2}\frac{dy}{2\pi i}\left(xy\right)^{L1}\left[\mathrm{\Phi }(x,y)\right]^N,$$
(53)
where the integration contours $`C_{1,2}`$ encircle points $`x=0`$, $`y=0`$, respectively. The derivation of Eq. (53) is quite similar to that of Eq. (28) for undirected graphs.

Again, in the thermodynamic limit, $`N\mathrm{}`$, $`L\mathrm{}`$, $`2L/N\overline{q}`$, one can use a saddle point approximation, which gives

$$Z_C(N,L,\left\{p(r,s)\right\})\left(\frac{\overline{q}}{ex_sy_s}\right)^L\left[\mathrm{\Phi }(x_s,y_s)\right]^N,$$
(54)
where $`x_s`$ and $`y_s`$ are defined from the stationary point equations:

$$\overline{q}=x_s\frac{\mathrm{ln}\mathrm{\Phi }(x_s,y_s)}{x_s}=y_s\frac{\mathrm{ln}\mathrm{\Phi }(x_s,y_s)}{y_s}.$$
(55)
For the grand canonical ensemble, we have

$$Z_{GC}(N,\lambda ,\left\{p(r,s)\right\})\mathrm{exp}\left(N\lambda x_sy_s\right)\left[\mathrm{\Phi }(x_s,y_s)\right]^N,$$
(56)
where the saddle point coordinates $`x_s`$ and $`y_s`$ are determined from the equations:

$$\lambda y_s=\frac{\mathrm{ln}\mathrm{\Phi }(x_s,y_s)}{x_s},\lambda x_s=\frac{\mathrm{ln}\mathrm{\Phi }(x_s,y_s)}{y_s}.$$
(57)
The degree distribution both for the canonical and grand canonical ensembles is defined by

$$\mathrm{\Pi }(r,s)=\frac{N(r,s)}{N}=\frac{\delta \mathrm{ln}Z\left(\left\{p(u,v)\right\}\right)}{N\delta \mathrm{ln}p(r,s)}\frac{p(r,s)}{r!s!}x_s^ry_s^s,$$
(58)
where the last relation is valid in the thermodynamic limit. Eqs. (58), (55) and (46) establish correspondence between the microcanonical ensemble with the degree distribution $`\mathrm{\Pi }(r,s)`$ and the canonical one, characterized by the preferential linking functions $`f_{1,2}`$ and the mean vertex degree $`\overline{q}`$. The parameters of the canonical and grand canonical ensembles with the same degree distribution are related as

$$\overline{q}=\lambda x_sy_s.$$
(59)
This relation follows from Eqs. (55) and (57).

Again, as it was for undirected graphs, the canonical ensemble does exist for every $`p(r,s)`$, provided that power series (50) has finite radii of convergence on both $`x`$ and $`y`$. Conditions for the existence of the grand canonical ensemble are essentially more strict: the integral in Eq. (52) must be well defined and convergent.

## V Fat-tailed degree distributions

In this section we shall consider in detail properties of the canonical ensembles of graphs, which arise if a preference function $`f(q)`$ grows rapidly enough.

For brevity, we focus on the undirected graphs. The generalization to the ensembles of directed graphs is straightforward.

As one can see from Eq. (26), the grand canonical ensemble does not exist in two cases. In the first case the integral, representing the partition function, diverges, since the function $`\mathrm{\Phi }\left(x\right)`$ grows fast enough at $`x\pm \mathrm{}`$. In the second case, the integral is not determined, because $`\mathrm{\Phi }\left(x\right)`$ has a singularity on the real axis. In both the situations we have degree distributions, which decay relatively slowly as $`q\mathrm{}`$. Let us begin with the case, when $`\mathrm{\Phi }\left(x\right)`$ has no singularities, but $`\mathrm{ln}\mathrm{\Phi }\left(x\right)`$ grows faster than $`x^2`$ as $`\left|x\right|\mathrm{}`$.

Using Eqs. (24) and (35), one can write the following relation:

$$\frac{\mathrm{\Phi }\left(x\right)}{\mathrm{\Phi }\left(x_s\right)}=\underset{q=0}{\overset{\mathrm{}}{}}\mathrm{\Pi }\left(q\right)\left(\frac{x}{x_s}\right)^q,$$
(60)
that is $`\mathrm{\Phi }\left(x\right)`$ is expressed in terms of the $`Z`$-transform of $`\mathrm{\Pi }\left(q\right)`$. Using the formula for the inverse of $`Z`$-transform, we obtain

$$\mathrm{\Pi }\left(q\right)=\frac{dx}{2\pi ix}\left(\frac{x_s}{x}\right)^q\frac{\mathrm{\Phi }\left(x\right)}{\mathrm{\Phi }\left(x_s\right)}.$$
(61)
For finding the relation between the asymptotic behaviours of $`\mathrm{\Phi }\left(x\right)`$ and $`\mathrm{\Pi }\left(q\right)`$, let us use a saddle point approximation in Eq. (61). It is convenient to set $`\mathrm{\Phi }\left(x\right)=\mathrm{exp}\varphi \left(x\right)`$. The equation for the saddle point $`x_a`$ is $`q=x_a\varphi ^{}\left(x_a\right)`$. Then the asymptotic expression for $`\mathrm{\Pi }\left(q\right)`$ is

$$\mathrm{\Pi }\left(q\right)\left\{2\pi x_a\left[x_a\varphi ^{\prime \prime }\left(x_a\right)\varphi ^{}\left(x_a\right)\right]\right\}^{1/2}\left(\frac{x_s}{x_a}\right)^q\mathrm{exp}\left[\varphi \left(x_a\right)\varphi \left(x_s\right)\right]$$
(62)
The integral for the grand canonical partition function in Eq. (26) is divergent, if $`\varphi \left(x\right)`$ grows as $`x^2`$ or faster at $`x\mathrm{}`$. Assume that $`\varphi \left(x\right)Ax^\mu `$ as $`x\mathrm{}`$. Then the saddle point equation is $`q=A\mu x^\mu `$, and $`x_a\left(q/A\mu \right)^{1/\mu }`$. Omitting irrelevant multiples, we have from Eq. (62):

$$\mathrm{\Pi }\left(q\right)\left(2\pi q\right)^{1/2}\left(\frac{\overline{q}}{q}e\right)^{q/\mu }\left[\mathrm{\Gamma }\left(q\right)\right]^{1/\mu }.$$
(63)
Thus, if the degree distribution $`\mathrm{\Pi }\left(q\right)`$ decays slower than $`\left[\mathrm{\Gamma }\left(q\right)\right]^{1/2}`$ as $`q\mathrm{}`$, then the partition function of the corresponding grand canonical ensemble diverges.

The reason for this divergence is that we have admitted the existence of non-Mayer’s graphs. Indeed, let us choose some pair of vertices in a graph. Let us add more and more edges connecting this pair. The statistical weight of the graph with $`\nu `$ edges between this pair contains multiple $`p\left(q_i\right)p\left(q_j\right)/\nu _{ij}!`$, where $`q_i=\nu _{ij}+\mathrm{const}`$, $`q_j=\nu _{ij}+\mathrm{const}`$. One can easily conclude that the statistical weights approach $`0`$ as $`\nu \mathrm{}`$ only if $`p^2\left(q\right)/q!0`$, or $`\sqrt{q!}\mathrm{\Pi }\left(q\right)0`$. The same result may be attained if we consider a sequence of graphs obtained by subsequent addition of closed loops to a chosen vertex. This result may also be presented in the different way: if the preference function $`f\left(q\right)=p\left(q+1\right)/p\left(q\right)`$ grows faster than $`\sqrt{q}`$ at large $`q`$, then the partition function of the grand canonical ensemble diverges.

The radius of convergence of the series expansion (24) is

$$R_c=\underset{q\mathrm{}}{lim}\frac{\left(q+1\right)p\left(q\right)}{p\left(q+1\right)}=\underset{q\mathrm{}}{lim}\frac{q+1}{f\left(q\right)}.$$
(64)
If $`f\left(q\right)`$ grows as $`q\mathrm{}`$ slower than a linear function, then $`R_c=\mathrm{}`$. In this case $`\mathrm{\Phi }\left(x\right)`$ has no singularities at all. This means that (i) the partition function of the canonical ensemble may be expressed in the form (28), and (ii) in the thermodynamic limit, one can use for this function its saddle point expression, Eqs. (29) and (30). If $`f\left(q\right)`$ grows faster than a linear function, then $`R_c=0`$. This means that although the canonical ensemble exists (the canonical ensemble always exists, because it is represented by a finite set of graphs at any finite $`N`$ and $`L`$), its partition function can not be written in the form of the integral representation (28). Actually, this means the absence of any meaningful thermodynamic limit.

The interesting case is $`0<R_c<\mathrm{}`$. In this case, the partition function of the canonical ensemble can be expressed as an integral, but the saddle point expression for this integral may not be longer valid. The saddle point expression is not valid at a large enough number of edges in the network, when the saddle point approaches the position of singularity. We show that in this situation, “fat-tailed” degree distributions, i.e. ones decreasing slower than an exponent, may arise.

Without any lack of generality, one can set $`R_c=1`$ in this case. This is equivalent to $`f\left(q\right)=q+o\left(q\right)`$ as $`q\mathrm{}`$. In Eq. (30) its right hand side is a monotonously increasing function of $`x_s`$. This means that as $`\overline{q}=2L/N`$ grows, $`x_s`$ grows too. As $`x_s<R_c=1`$, the degree distribution contains exponentially decaying multiple $`x_s^q`$. There are two possibilities depending on the character of the singularity of $`\mathrm{\Phi }\left(x\right)`$ at $`x=1`$: either $`\mathrm{\Phi }^{}\left(x_s\right)\mathrm{}`$, or it approaches some finite value as $`x_s\mathrm{}`$. In the former case, again there are two possibilities: either $`lim_{x1}\mathrm{\Phi }\left(x\right)`$ is finite, or this limit is infinite. If $`\mathrm{\Phi }\left(1\right)`$ is finite (but $`\mathrm{\Phi }^{}\left(1\right)`$ is infinite), then the degree distribution approaches some limiting form as $`\overline{q}\mathrm{}`$, and the first moment of this limiting distribution diverges. This means that such a degree distribution can not be realized in any canonical ensemble with a finite number of edges per vertex. To construct networks with such a distribution, one has to change the conditions of the thermodynamic limit transition in the canonical ensemble, assuming $`N\mathrm{}`$, $`L\mathrm{}`$ and $`\overline{q}=2L/N\mathrm{}`$, instead of keeping $`\overline{q}`$ fixed. Another way is to use a microcanonical ensemble. If $`\mathrm{\Phi }\left(1\right)`$ is infinite, no normalizable degree distribution without an exponential cut-off is possible.

Now, let us consider the case $`\mathrm{\Phi }^{}\left(1\right)<\mathrm{}`$. The degree distribution becomes “fat-tailed” when $`x_s=1`$, which takes place when $`\overline{q}=\overline{q}_c=\mathrm{\Phi }^{}\left(1\right)/\mathrm{\Phi }\left(1\right)`$. If $`\overline{q}>q_c`$, the saddle point equation (30) has no solution $`0<x_s<1`$. In this case, in the thermodynamic limit, the partition function remains the same up to a preexponential factor as for $`\overline{q}=q_c`$. Indeed, let us rewrite Eq. (28) as

$$Z_C(N,L,\left\{p\left(q\right)\right\})=N^L\left(2L1\right)!!_c\frac{dx}{2\pi ix}\left[x^{\overline{q}}\mathrm{\Phi }\left(x\right)\right]^N.$$
(65)
To calculate a large $`N`$ asymptotics one has to deform the integration contour into the steepest descent one, intercepting the real axis at the point, where $`x^{\overline{q}}\mathrm{\Phi }\left(x\right)`$ is minimal within the interval $`(0,1)`$, and going along the line of the constant (i.e. zero) imaginary part. If $`\overline{q}<q_c`$, this is a usual saddle-point contour, crossing the real axis perpendicularly at some point $`x_s<1`$. If $`\overline{q}>q_c`$, this contour consists of two complex conjugate parts meeting always at $`x=1`$. As $`\overline{q}`$ grows, the point, where the integrand is maximal, $`x_s=1`$, does not move. The only change is that the two branches of the contour become closer and closer to the real axis in the vicinity of $`x=1`$ at $`x>1`$. But it is $`x_s`$ and $`\mathrm{\Phi }\left(x_s\right)`$ that determine the value of the main (extensive) contribution to the logarithm of the partition function: $`\mathrm{ln}Z_C=L\mathrm{ln}\left(\overline{q}x_s\right)+N\mathrm{ln}\mathrm{\Phi }\left(x_s\right)+o\left(N\right)`$. The extensive part of the “free energy” $`\mathrm{ln}Z`$ does not depend on $`\overline{q}`$ as $`\overline{q}>q_c`$. So, the degree distribution $`N^1\delta \mathrm{ln}Z/\delta \mathrm{ln}p\left(q\right)`$ (see Eqs. (4) and (21)) remains equal to its critical point value $`\mathrm{\Pi }_c\left(q\right)`$. Consequently, the finite fraction of edges, $`\overline{q}/\overline{q}_c1`$, is attached to an infinitely small fraction of vertices, forming a “condensate”, quite analogous to the one in the backgammon model .

A specific form of the degree distribution at the critical point depends on the behaviour of this difference $`f\left(q\right)q=o\left(q\right)`$ as $`q\mathrm{}`$. For example, for the so called “scale-free” distributions, $`\mathrm{\Pi }\left(q\right)q^\gamma `$ as $`q\mathrm{}`$ ($`\gamma >2`$), we obtain from Eq. (36):

$$f\left(q\right)=q+1\gamma +𝒪\left(q^1\right)$$
(66)
at the critical point. For the same $`f\left(q\right)`$ but for lower average degrees $`\overline{q}<\overline{q}_c`$, we have $`\mathrm{\Pi }\left(q\right)x_s^qq^\gamma `$ at large $`q`$. So, the state with a power-law degree distribution is marginal for the phase without the condensate of edges . (A “scale-free” state as a line between “generic” and “crumpled” phases on the phase diagram of trees was found in Ref. , see also the condensation transition in the backgammon model .) Our analysis has shown that the condensation takes place above $`\overline{q}_c`$ . Furthermore, the fat-tailed degree distribution is present also in the condensed phase. The problem of the condensed phase is more complex for the ensembles of Mayer’s graphs, that is the ones without tadpoles and melons. The nature of condensation transition in such ensembles will be discussed elsewhere.

## VI Conclusions

Thus, we have developed the consistent description of random networks in the framework of classical statistical mechanics. Using the traditional formalism of statistical mechanics, we have constructed a set of equilibrium statistical ensembles of uncorrelated random networks and have found their partition functions and main characteristics. We have proposed a set of natural dynamical procedures, which generate equilibrium networks as a limiting state of the evolution, and have established a one-to-one correspondence between rules of these ergodic procedures and equilibrium ensembles of networks. This program has been realized both for directed and undirected networks.

We have shown that a “scale-free” state (and fat-tailed degree distributions) in equilibrium uncorrelated networks without condensation of edges on vertices may exist only in a single marginal point. So, it is rather an exception . This differs crucially from the situation for growing networks. The latter, while growing, may self-organize into scale-free structures in a wide range of parameters without any condensation. In summary, we have developed a statistical physics approach to equilibrium random networks.

S.N.D. thanks PRAXIS XXI (Portugal) for a research grant PRAXIS XXI/BCC/16418/98. S.N.D. and J.F.F.M. were partially supported by the project POCTI/99/FIS/33141. A.N.S. acknowledges the NATO program OUTREACH for support. We also thank V.V. Bryksin, A.V. Goltsev, A. Krzywicki, and F. Slanina for useful discussions.

## A Statistical weights for the microcanonical ensemble

Initially, we have $`N`$ vertices (“hedgehogs”) with $`q_i`$ edges (“halves” of edges, speaking more precisely) protruding from an $`i`$-th one. Here we count the number of ways of connecting them in pairs to obtain a given graph with a given number of edges $`g_{ij}`$ between vertices $`i`$ and $`j`$. For vertices with unit-length loops (“tadpoles”) we set $`g_{ii}`$ to be equal to twice the number of such loops. The number of ways to choose $`g_{i1},g_{i2},\mathrm{}g_{iN}`$ edges from $`q_i=g_{i1}+g_{i2}+\mathrm{}+g_{iN}`$ ones, attached to the $`i`$-th vertex is

$$\frac{q_i!}{g_{i1}!g_{i2}!\mathrm{}g_{iN}!}.$$
(A1)
Then we have to connect in pairs $`g_{ij}`$ dangling edges, attached to the $`i`$-th vertex, and $`g_{ji}=g_{ij}`$ edges attached to the $`ji`$ vertex. This can be done by $`g_{ij}!`$ different ways. Also, the number of ways to join $`g_{ii}`$ dangling edges in pairs to form $`g_{ii}/2`$ closed loops is $`\left(g_{ii}1\right)\left(g_{ii}3\right)\mathrm{}1=\left(g_{ii}1\right)!!`$. Finally, combining together $`N`$ multiples (A1) for each vertex, $`N\left(N1\right)/2`$ multiples $`g_{ij}!`$ for each pair of vertices, multiples $`\left(g_{ii}1\right)!!`$ for each vertex, containing unit-length loops, and taking into account that $`\left(g_{ii}1\right)!!/g_{ii}!=1/g_{ii}!!`$, we arrive at Eq. (10).

## B Integral representation of the partition function for canonical ensemble

The partition function of the canonical ensemble is

$$Z_C(N,L)=N^L\underset{g\mathrm{\Omega }(N,L)}{}\underset{i=1}{\overset{N}{}}\frac{p\left(q_i\right)}{g_{ii}!!}\underset{j<k=1}{\overset{N}{}}\frac{1}{g_{jk}!},$$
(B1)
where the set $`\mathrm{\Omega }(N,L)`$ is a set of $`N^2`$ non-negative integers $`g_{ij}0`$ with the following properties: (i) $`g_{ii}`$ are even, (ii) $`g_{ij}=g_{ji}`$, and (iii)

$$\frac{1}{2}\underset{i,j=1}{\overset{N}{}}g_{ij}=\underset{i=1}{\overset{N}{}}\frac{g_{ii}}{2}+\underset{i>j=1}{\overset{N}{}}g_{ij}=L.$$
(B2)
So, $`N\left(N+1\right)/2`$ variables $`g_{ij}`$, $`ij`$, are subjected to the restriction (B2). Introducing

$$\mathrm{\Phi }\left(x\right)=\underset{q=0}{\overset{\mathrm{}}{}}\frac{p\left(q\right)}{q!}x^q,$$
(B3)
one can write Eq. (B1) as

$`Z_C(N,L)`$ (B4)
$`=`$ $`N^L{\displaystyle \underset{\left\{g\right\}\mathrm{\Omega }(N,L)}{}}{\displaystyle \underset{i=1}{\overset{N}{}}}\left[\left({\displaystyle \frac{g_{ii}}{2}}\right)!2^{g_{ii}/2}\right]^1\left({\displaystyle \frac{^2}{x_i^2}}\right)^{g_{ii}/2}{\displaystyle \underset{j<k=1}{\overset{N}{}}}\left(g_{jk}!\right)^1{\displaystyle \frac{^2}{x_jx_k}}{\displaystyle \underset{l=1}{\overset{N}{}}}\mathrm{\Phi }\left(x_l\right)|_{x_1=\mathrm{}=x_N=0}`$ (B5)
$`=`$ $`{\displaystyle \frac{\left(2N\right)^L}{L!}}\left({\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle \frac{^2}{x_i^2}}+2{\displaystyle \underset{i>j=1}{\overset{N}{}}}{\displaystyle \frac{^2}{x_ix_j}}\right)^L{\displaystyle \underset{l=1}{\overset{N}{}}}\mathrm{\Phi }\left(x_l\right)|_{x_1=\mathrm{}=x_N=0}`$ (B6)
$`=`$ $`{\displaystyle \frac{\left(2N\right)^L}{L!}}\left({\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle \frac{}{x_i}}\right)^{2L}{\displaystyle \underset{l=1}{\overset{N}{}}}\mathrm{\Phi }\left(x_l\right)|_{x_1=\mathrm{}=x_N=0},`$ (B7)
where the relation (B2) was used. If we pass from $`x_1,\mathrm{},x_N`$ to a new set of variables: $`x=\left(x_1+\mathrm{}+x_N\right)/N`$, and difference variables $`y_i=x_ix_{i+1}`$, $`i=1,\mathrm{},N1`$, we have

$`{\displaystyle \frac{}{x}}={\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle \frac{x_i}{x}}{\displaystyle \frac{}{x_i}}={\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle \frac{}{x_i}}.`$

Then

$$Z_C(N,L)=\frac{\left(2N\right)^L}{L!}\frac{^{2L}}{x^{2L}}\left[\mathrm{\Phi }\left(x\right)\right]^N|_{x=0}.$$
(B8)
Finally, one can write

$$Z_C(N,L)=\frac{\left(2N\right)^L}{L!}\left(2L\right)!_c\frac{dx}{2\pi i}x^{2L1}\left[\mathrm{\Phi }\left(x\right)\right]^N,$$
(B9)
which is exactly Eq. (28). The contour $`c`$ encircles the point $`x=0`$.

## C Evolution equation for the degree distribution

Here we present a simplified derivation of the evolution equation for the degree distribution $`\mathrm{\Pi }(q,t)`$. For example, we consider a network with the rewiring of edges according to the rules formulated in Section III for the canonical ensemble (for the grand canonical ensemble, the procedure is essentially the same). The total number of vertices, $`N`$, and of edges, $`L`$, are fixed. With some probability $`n`$ per unit time, a randomly chosen end of a randomly chosen edge is rewired to some vertex of the graph. This vertex is chosen from vertices of the graph with probability proportional to a given function $`f\left(q_i\right)`$ of the degree $`q_i`$ of the vertex.

Then, the probability that a vertex $`i`$ receives a new edge per time $`dt`$ is

$$\frac{f\left(q_i\right)ndt}{_jf\left(q_j\right)}\frac{nf\left(q_i\right)}{N\overline{f\left(q\right)}}.$$
(C1)
In Eq. (C1) its left-hand side may be replaced with the right-hand side in the thermodynamic limit $`N\mathrm{}`$ (self-averaging) if the fluctuations of $`N\left(q\right)`$ can be neglected. This is true for the equilibrium state (see Eq. (21)), and so here we restrict ourselves to the nonequilibrium states that fulfill this condition. Then, the infinitesimal change of the degree distribution due to the rewiring of edges to a chosen vertex is

$$\left[d\mathrm{\Pi }(q,t)\right]_{\mathrm{to}}=\frac{n}{N\overline{f\left(q\right)}}\left[f\left(q1\right)\mathrm{\Pi }(q1,t)f\left(q\right)\mathrm{\Pi }(q,t)\right]dt.$$
(C2)
Also, we must take into account that the vertex may loose one of its $`q_i`$ edges, which will be rewired to another vertex. The probability $`nq_idt/L`$ that one of these edges is chosen for rewiring per time $`dt`$, must be multiplied by $`1/2`$. This is the probability that of the two ends of the edge, the one attached to the $`i`$-th vertex, is chosen. Thus, the change of the degree distribution due to rewiring of edges from a vertex is

$$\left[d\mathrm{\Pi }(q,t)\right]_{\mathrm{from}}=\frac{n}{N\overline{q}}\left[\left(q+1\right)\mathrm{\Pi }(q+1,t)q\mathrm{\Pi }(q,t)\right],$$
(C3)
where $`\overline{q}=2L/N`$ is the average vertex degree. Combining Eqs. (C2) and (C3) we arrive at the evolution equation

$$\frac{N}{n}\frac{\mathrm{\Pi }(q,t)}{t}=\frac{1}{\overline{f\left(q\right)}}\left[f\left(q1\right)\mathrm{\Pi }(q1,t)f\left(q\right)\mathrm{\Pi }(q,t)\right]+\frac{1}{\overline{q}}\left[\left(q+1\right)\mathrm{\Pi }(q+1,t)q\mathrm{\Pi }(q,t)\right].$$
(C4)
Looking for the stationary solution of Eq. (C4), one can easily find its first integral:

$$\frac{q+1}{\overline{q}}\mathrm{\Pi }\left(q+1\right)\frac{f\left(q\right)}{\overline{f\left(q\right)}}\mathrm{\Pi }\left(q\right)=\mathrm{const}.$$
(C5)
One must set $`\mathrm{const}=0`$ in Eq. (C5), because $`\mathrm{\Pi }\left(q\right)=0`$ at $`q<0`$. Then we have

$$\mathrm{\Pi }\left(q+1\right)=x_s\frac{f\left(q\right)}{q+1}\mathrm{\Pi }\left(q\right),$$
(C6)
where we have introduced $`x_s=\overline{q}/\overline{f\left(q\right)}`$. The solution of Eq. (C6) is

$$\mathrm{\Pi }\left(q\right)=C\frac{p\left(q\right)}{q!}x_s^q.$$
(C7)
Here $`C`$ and $`x_s`$ must be determined from the normalization condition and from the equality of the mean degree to a given value $`\overline{q}=2L/N`$:

$$\underset{q=0}{\overset{\mathrm{}}{}}\mathrm{\Pi }\left(q\right)=1,\underset{q=0}{\overset{\mathrm{}}{}}q\mathrm{\Pi }\left(q\right)=\overline{q}.$$
(C8)
E-mail address: sdorogov@fc.up.pt
E-mail address: jfmendes@fis.ua.pt
E-mail address: samukhin@fc.up.pt