{'fraction_non_alphanumeric': 0.03504544202698981, 'fraction_numerical': 0.00936381162214266, 'mean_word_length': 4.356629172044993, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The entropy of network ensembles

In this paper we generalize the concept of random networks to describe networks with non trivial features by a statistical mechanics approach. This framework is able to describe ensembles of undirected, directed as well as weighted networks. These networks might have not trivial community structure or, in the case of networks embedded in a given space, non trivial distance dependence of the link probability. These ensembles are characterized by their entropy which evaluate the cardinality of networks in the ensemble. The general framework we present in this paper is able to describe microcanonical ensemble of networks as well as canonical or hidden variables network ensemble with significant implication for the formulation of network constructing algorithms. Moreover in the paper we define and and characterize in particular the"structural entropy", i.e. the entropy of the ensembles of undirected uncorrelated simple networks with given degree sequence. We discuss the apparent paradox that scale-free degree distribution are characterized by having small structural entropy but are so widely encountered in natural, social and technological complex systems. We give the proof that while scale-free networks ensembles have small structural entropy, they also correspond to the most likely degree distribution with the corresponding value of the structural entropy.


INTRODUCTION
The quantitative measure of the order present in complex systems and the possibility to extract information from the complex of interactions in cellular, technological and social networks is a topic of key interest in modern statistical mechanics. The field of complex networks [1,2] has having a rapid development and a large success in this respect due to the wide applicability of simple concepts coming from graph theory. The characterization of the structure of different networks has allowed the scientific community to compare systems of very different nature. Different statistical mechanics tools have been devised to describe the different level of organization of real networks. A description of the structure of a complex network is presently performed by measuring different quantities as (i) the density of the links, (ii) the degree sequence [3], (iii) the degree-degree correlations [4,5,6], (iv) the clustering coefficient [7,8], (v) the kcore structure [9,10,11], (vi) the community structure [2,12,13,14] and finally the nature of the embedding space [15,16,17]. Moreover, is the network is weighted, strength/degree correlations [18] and if the network is directed, in-degree/out-degree correlations [19] are significant characteristics of the network These phenomenological quantities describe the local or non-local topology of the network and do affect dynamical models defined of them [1].
While many different statistical mechanics models have been proposed [20,21,22,23,24,25,26,27] to describe how the power-law degree distribution can arise in complex networks, little work has been done on the problem of measuring the level of organization and "order" in the frame of theoretical statistical mechanics. Only recently, in the field of complex networks atten-tion has been addressed to the study of entropy measures [28,29,30,31,32,33] able to approach this problem. In [31] the entropy of a given ensemble as the normalized logarithm of the number of networks in the ensemble has been introduced. This quantity can be used to asses the role that a given structural characteristics have in shaping the network. In fact, given a real network, a subsequent series of randomized networks ensembles can be build each subsequent ensemble sharing one additional structural characteristic with the given network. The entropy of these subsequent networks ensembles would decreases as we proceed adding constraints and the difference between the entropies in two subsequent ensembles quantifies how restrictive is the introduced additional constraint. In the first part of this paper construct a general statistical mechanics framework for the construction of generalized random network ensembles which satisfy given structural constraints. We call these ensembles "microcanonical". We also describe how to construct "canonical" network ensembles or generalized hidden variable [22,23,24,25,26,27] models. Subsequently we make an account of most of the network ensembles that can be formulated: the ensemble of undirected networks with given number of links and nodes, the ensemble of undirected networks with given degree sequence, with given spatial embedding and community structure. Some of these network ensembles where already presented in [31] and we report their derivation here for completeness. This approach is further extended to weighted networks and directed networks. Finally we focus our attention on the structural entropy, i.e. the entropy of an ensemble of uncorrelated undirected simple networks of given degree sequence. The structural entropy of a power-law network with constant average degree is monotonically decreasing as the power-law ex-ponent γ → 2. This result could appear in contradiction with the wide occurrence of power-law degree distribution in complex networks. Here we show by a statistical mechanics model that scale-free degree distribution are the most likely degree distribution at given small value of structural entropy while Poisson degree distributions are the most likely degree distribution of networks with maximal structural entropy.
This result indicates that the scale-free degree distributions emerges naturally when considering networks ensembles with small structural entropy and therefore larger amount of order.
The appearance of the power-law degree distribution reflects the tendency of social, technological and especially biological networks toward "ordering". This tendency is at work regardless of the mechanism which is driving their evolution that can be either a preferential attachment mechanism [3], or a "hidden variables" mechanism [22,23,24,25,26,27] or some other statistical mechanics mechanism [20,21].

STATISTICAL MECHANICS OF NETWORK ENSEMBLES
A network of N labeled nodes i = 1, 2, . . . , N is uniquely defined by its adjacency matrix a of matrix elements a ij ≥ 0 with a ij > 0 if and only if there is a link between node i and node j. Simple networks are networks without tadpoles or double links, i.e. a ii = 0 and a ij = 0, 1. Weighted networks describe heterogeneous interactions between the nodes and the matrix elements a ij can take different null or positive values, while directed networks are described by non-symmetric adjacency matrices a = a T where we have indicated by a T the transpose of the matrix a.
A structural constraint on a network can always be formulated as a constraint on the adjacency matrix of the graph, i.e.
In order to describe "microcanonical" network ensembles with given structural constraints in [31] and in the following we will use a statistical mechanics perspective. Therefore we define a partition function Z of the ensemble in the following way where, for simplifying the problem , F (a) and a ij take only integer values, and δ[·] indicate the Kronecker delta and Θ(x) = 1 if x > 0 and Θ(x) = 0 if x = 0. Moreover, in (79), the auxiliary fields h ij have been introduced as in classical statistical mechanics. The entropy per node Σ of the network ensemble is defined as The marginal probability for a certain value of the element a ij of the adjacency matrix is given by The probability of a link p ij is given by In and ensemble of weighted network we can define also the average weight w ij of a link between node i and node j as equal to In a "microcanonical" network ensemble all the networks that satisfy a given structural constraint have equal probability. Therefore the probability of a network G, described by the adjacency matrix a, is given in the "microcanonical" ensemble by If we allow for "soft" structural constraints in network ensemble we can describe "canonical" network ensemble. In a "canonical" network ensemble each network a has a different probability given by expression that for ensemble of simple networks take the form If the link probabilities π ij (a ij ) are chosen equal to (4) and (5), then we have that the structural constraints F (a) = C are satisfied in average, i.e.
where the average · PC (a) indicates the average over the canonical ensembles (8). The statistical mechanics formulation of network ensemble is always well defined. For network structural constraints that do not correspond to feasible networks [34] the entropy of the network ensemble is nevertheless Σ = −∞. Although the definition of the statistical mechanics problem is always well defined, the calculation of the partition function by saddle point approximation can only be performed if the number of constraints F α with α = 1, . . . , M is at most extensive, i.e M = O(N ). In addition to that, in the paper we are going to consider only linear constraints on the adjacency matrix. Further developments on this statistical mechanics framework will involve pertubative approach to solve non linear structural constraints.

UNDIRECTED SIMPLE NETWORKS
In an undirected simple network the adjacency matrix elements are zero/ one (a ij = 0, 1) and the tadpoles are forbidden( a ii = 0 ∀i). We can consider for these networks different types of structural constraints. In the following we list few of them of particular interest.
• i) The ensemble G(N, L) of random networks with given number of nodes N and links L = i<j a ij (providing in this way a statistical mechanics formulation of the G(N, L) random ensemble). In this case we have the structural constraint • ii) The configuration model, i.e. the ensemble of networks with given degree sequence {k 1 , . . . , k N } with k i = j a ij . In this case the structural constraints are given by for α = 1, . . . , N .
• iii) The network with given degree sequence {k 1 , . . . , k N } and given average nearest neighbor connectivity k nn (k) = [ i,j δ(k i − k)a ij k j ]/(kN k ) of nodes of degree k (with N k indicating the number of nodes of degree k in the network). In this case the structural constraints are given by for α = 1, . . . , N and (14) for α = N + 1, . . . N + K. with K indicating the maximal connectivity of the network.
• iv) The network ensemble with given degree sequence and given community structure. For these network we assume that each node is assigned a feature {q 1 , . . . q N } and we fix the number of links between nodes of different features A(q, q ′ ) = i<j δ(q ij − q)δ(q ij − q ′ )a ij with q ij = min(q i , q j ) and q ij = max(q i , q j ). In this case the structural constraints are given by for α = 1, . . . , N and for α = N + 1, . . . N + Q(Q + 1)/2 with Q equal to the number of different features of the nodes. Here an in the following in order to have an extensive number of constraints we assume Q = O(N 1/2 ).
• v) The ensemble of networks with given degree sequence and dependence of the link probability on the distance of the nodes in an embedding geometrical space. In this ensemble we consider fixed spatial distribution of nodes in space { r 1 , . . . , r N } and we consider all the networks compatible with the given degree sequence and the number of links linking nodes in a given distance interval. Therefore we take Λ distance intervals . . , Λ, and we fix the number of links linking nodes in a given distance interval. The structural constraint involved therefore the vector is the distance between node i and j in the embedding space and the characteristic function χ ℓ (x) = 1 if x ∈ [d ℓ , d ℓ +(∆d) ℓ ] and χ d (x) = 0 otherwise. In this case the structural constraints can be expressed as for α = 1, . . . , N and for α = N + 1, . . . N + Λ.

The G(N,L) and the G(N,p) ensembles
The networks in the G(N, L) ensemble have given number of nodes N and links L. The entropy of this ensemble is given by the logarithm of the binomial (we always assume distinguishable nodes in the networks [29]). The probability p ij of a given link (i, j) is given by p (0) ij = L/(N (N − 1)/2) for every couple of nodes i, j. The ensemble G(N, p) is the "canonical" ensemble corresponding to the "microcanonical" G(N, L) ensemble.

The configuration ensemble
In the configuration ensemble we consider all the networks with given degree sequence. Using (2) (12) the partition function of the ensemble can be explicitly written as Expressing the delta's in the integral form with Lagrangian multipliers ω i for every i = 1, . . . N we get where Dω = i dω i /(2π). We solve this integral by saddle point equations accounting also for second order terms of the expansion. The entropy of this ensemble of networks can be approximated in the large network limit N ≫ 1 with with the Lagrangian multipliers ω i satisfying the saddle point equations and the coefficients α i defined as The probability of a link i, j in this ensemble is given by In particular in this ensemble p ij = f (ω i )f (ω j ), consequently the model retains some "natural" correlations [27] given by the degree sequence and the constraint that we consider only simple networks. In fact these are nothing else than the correlations of the configuration model [35]. The "canonical model" corresponding to the configuration model is then a "hidden variable" models where each node i is assigned a "hidden variable" ω i and the probability for each link follow (25). Similar expressions where already derived in different papers [22,25,27] but with a different interpretation. Here the "hidden variables" ω i are simply fixing the average degrees of each node. We note here that the derivation of [26] guarantees that in the "canonical" model the connectivity of each node is distributed according to a Poisson distribution with average j p ij .
The form of the probability p ij is such that when inferring the values of the "hidden variables" ω i for a "canonical" network in this ensemble by maximum likelihood methods, we obtain the ω ′ i = ω i in the large network limit [27].

Uncorrelated networks
The case in which there is a structural cutoff in the network k i < k N is of particular interest. In this case we can approximate Eq. (23) by e ω ⋆ i ≃ k i / k N , α i ≃ k i . In this limit the network is uncorrelated the probabilities of a link are given by p We call the entropy of these uncorrelated ensembles the structural entropy Σ S and we can evaluate it providing the explicit expression Expression (26) gives for the number of networks in the ensemble (27) From combinatorial arguments we can derive an expression N uncorr C for the number of uncorrelated networks with a given degree sequence which agrees with the above estimate (27) In fact by combinatorial arguments we can show that the number of networks with given degree sequence is given by the following expression in the large N limit, i.e.
N uncorr The factor (2L − 1)!! accounts for the total number of wiring's of the links. In fact if we want to construct a network, given a certain distribution of half-edges through the N nodes of the network, as a first step we take a halfedge and we match it with one of the 2L − 1 other halfedge of the network. Secondly we match a new half-edge with one of the 2L − 3 remaining half-edges. Repeating this procedure we get one out of (2L−1)!! possible wiring of the links. This number includes also the wiring of the links which gives rise to networks with double links. To estimate the number of such undesired wiring we assume that the network is random, i.e. that the probability that a node with k i half-edges connects to a node with k j halfedges is a Poisson variable with average k i k j /( k N ). In this hypothesis the probability Π that the network does not contain double links is equal to [36] Finally in the expression (29) for N c there is an additional term which takes into account the number of wiring of the links giving rise to equivalent networks without double links. This term is given by the number of possible permutation of the half-edges at each node, i.e. i k i !. We note here that a similar result was derived by mathematicians for the case in which the maximal connectivity K < N 1/3 [37] and an inequality was proved for the case K > N 1/3 [38]. Now we extend these results by statistical mechanics methods to uncorrelated networks with maximal connectivity K < k N .
The entropy of a network ensemble with fixed degree correlations We consider now network ensembles with given degree correlations and given average degree of neighboring nodes, satisfy the constraints defined in Eqs. (13) and (14). We can proceed to the evaluation of the probability of a link p (2) ij and the calculation of the entropy of the ensemble as in the configuration model. In this case we have to introduce the Lagrangian multipliers ω i fixing the degree of node i and the Lagrangian multipliers A k fixing the average degree of nodes of degree k.
The partition function of this ensemble can be evaluated at the saddle point giving for the entropy of the ensemble, in the thermodynamic limit value where ω ⋆ i and A star k satisfy the saddle point equations and where with α i , α k are approximately equal to the following expressions The probability p (2) ij of the link (i, j) in this ensemble is given by This formula generalize the "hidden variable" formula of the configuration model to networks with strong degreedegree correlations. In particular in order to build a "canonical" network with strong degree degree correlation we can consider nodes with "hidden variables" θ i and G θ and a probability p ij to have a link between a node i and a node j given by The entropy of network ensemble with given degree sequence and given community structure The partition function of network ensembles with given degree sequence (15) and given community structure (16) can be evaluated by saddle point approximation in the large network limit as long as Q = O(N 1/2 ).
Following the same steps as in the previous case we find that the entropy for such an ensemble is given by with the Lagrangian multipliers {ω star i }, {w star q,q ′ } satisfy-ing the saddle point equations and with α i , α q,q ′ that can be approximated by In this ensemble the probability for a link p (c) ij between a node i and a node j is equal to Assigning each node a "hidden variable" θ i and to each pair of communities the symmetric matrix V (q, q ′ ) we can construct the "hidden variable" or "canonical" ensemble by extracting each link with probability .
The entropy of a network ensemble with given distance between the nodes Finally we consider the ensemble of undirected networks living in a generic embedding space and with structural constraints described by (17) and (18). Following the same steps as in the previous cases we find that the entropy for such an ensemble in the large network limit is given by with the Lagrangian multipliers {ω i }, {g d } satisfying the saddle point equations and the variables α i , α q,q ′ approximated by the expressions The probability for a link between node i and j is equal to Therefore the "hidden variable" model associated to this ensemble correspond to a model where we fix the "hidden variables" θ i and W (d ℓ ) and we draw a link between node i and node j according to . (45)

WEIGHTED NETWORKS
Many networks not only have a non trivial topological structure but are also characterized by weighted links. We will assume in this paper that the weight of a link can assume only integer values and consequently a link between a node i and node j is characterized by an integer number a ij ≥ 1, this is not a very stringent constraints since we can assume to have always finite networks (studied in the thermodynamic limit). In a weighted network the degree and the strength s i of the node i are defined as where Θ(x) = 0 if x = 0 and Θ(x) = 1 is x > 0. It is possible to define series of weighted networks by considering networks with fixed total strength, with given strength sequence, with given strength and degree sequence and proceeding by adding additional features as in the unweighted case. Here an in the following we study the most relevant cases: • We first consider the network ensemble with given total strength S. The structural constraint in this case is equal to • ii) We consider the network with given strength sequence s 1 , . . . , s N . The structural constraints are for this ensemble given by for α = 1, . . . , N .
The entropy of weighted network ensembles with given total strength S The entropy of this ensemble is given by The average value of a the weight of the link from i to j is given by and the probability of a link between node i and j is equal to Therefore the simple networks with adjacency matrix ((A ij )) that can be constructed from the weighed networks with adjacency matrix ((a ij )) by putting A ij = Θ(a ij ) ∀i, j is uncorrelated. The canonical ensemble is given by Eq. (8) with and The entropy of weighted network ensembles with given strength sequence To calculate the entropy of undirected networks with a given strength sequence of degrees {s i } we proceed by the saddle point approximation as in previous cases We find that the entropy of this ensemble of networks is given by with the Lagrangian multipliers ω ⋆ i satisfying the saddle point equations and with λ i being the eigenvectors of the Jacobian of the function The average value of a the weight of the link from i to j is given by and the probability of a link between node i and j is equal to Therefore as it has been observed in [? ] only by rewiring the links of a network allowing for multilinks we get a network structure which is uncorrelated. The canonical ensemble (8) in this case can be constructed by assigning to every possible link (i, j) the weight a ij with the probability The entropy of weighted network ensembles with given strength /degree sequence The entropy of weighted networks with a given strength and degree sequence {s i , k i } in the large size network limit is given by with the Lagrangian multipliers satisfying the saddle point equations and with λ ℓ being the eigenvectors of the Jacobian of the function The average weight of the link (ij) is given by and the probability of a link between node i and j is equal to The canonical ensemble (8) in this case con be constructed by assigning to every possible link (i, j) the weight a ij with the probability

DIRECTED NETWORKS
An undirected network is determined by a symmetric adjacency matrix, while the matrix of a directed network is in general non-symmetric. Consequently the degrees of freedom of a directed network are more than the degrees of freedom of an undirected network. In the following we only consider the network ensemble with In this case the probability of a directed link is given by .
The entropy of directed network ensembles with given degree sequence To calculate the entropy of directed networks with a given degree sequence of in/out degrees {k out i , k in i } we just have to impose the constraints on the incoming and outgoing connectivity, Following the same approach as for the undirected case, we find that the entropy of this ensemble of networks is given by with the Lagrangian multipliers satisfying the saddle point equations The probability for a directed link from i to j is given by If the ω i +ω j < 0∀i, j = 1, . . . N the directed network becomes uncorrelated and we have p Given this solution the condition for having uncorrelated directed networks is that the maximal in-degree K (in) and the maximal out-degree K (out) should satisfy, K (in) K (out) / k in N < 1. The entropy of the directed uncorrelated network is then given by which has a clear combinatorial interpretation as it happens also for the undirected case.

NATURAL DEGREE DISTRIBUTION CORRESPONDING TO A GIVEN STRUCTURAL ENTROPY
For power-law networks with power-law exponent γ ∈ (2, 3) the entropy of the networks with fixed degree sequence Σ 1 given by Eq. (22) decreases with the value of the power-law exponent γ when we compare network ensemble with the same average degree [31]. Therefore scale-free networks have much smaller entropy than homogeneous networks. This fact seems to be in contrast with the fact that scale-free networks are the underlying structure of a large class of complex systems. The apparent paradox can be easily be resolved if we consider that many networks are the result of a non-equilibrium dynamics. Therefore they do not have to satisfy the maximum entropy principle. Nevertheless, in order to give more insight and comment on the universal occurrence of power-law networks in this section we derive the most likely degree distribution of given structural entropy when the total number of nodes and links are kept fixed. By structural entropy we define the entropy Σ S (26) of uncorrelated networks with fixed degree distribution. In order to do that we construct a statistical model very closely related to the urn or "ball in the box" models [21,39] We consider degree distributions {N k } = i δ(k − k i ) which arise from the random distribution of the 2L halfedges through the N nodes of the network. The number of ways N {N k } in which we can distribute the (2L) halfedges in order to have a {N k } degree distribution are We want to find the most likely degree distribution that corresponds to a given value of the structural entropy. Proceeding as in standard statistical mechanics, we define a normalized partition function Z as To enforce these conditions we introduce in (79) the delta functions in the integral form providing the expression where Assuming that the sum over all N k can be approximated by the sum over all L k = kN k = 1, 2, . . . ∞ we get ln G k (λ, µ, ν) = exp iλ + iµ/k − β k ln(k!) + iνk and where < k >= 2L/N indicates the average degree of the network. By evaluating (82) at the saddle point, deriving the argument of the exponential respect to λ and ν, we obtain These equations always have a solution for sparse networks with L = O(N ) provided that β > 1 and k > 1. The marginal probability that L k = kN k is given by with (87) and If we develop (86) for ℓ ≪ L and we use the Stirling approximation for factorials, we get that each variable L k is a Poisson variable with mean L k satisfying where we assume that the minimal connectivity of the network is k > 0. The average N k is a power-law distribution with a lower and upper effective cutoffs −iµ and 1/(iν) fixing the average degree k , with the Lagrangian parameter λ fixing the normalization constant and finally β fixing the structural entropy. The distribution of P (N k ) is finally In the limit β → ∞ (90) is extremely peaked around the average degree k ≃ k ⋆ = O( k ) of the network and the degree distribution N k decays at large value of N k as a Poisson distribution, i.e. P (N k ) ≃ 1 (kN k )! e kN k [−β ln(k ⋆ !)/k ⋆ +iλk ⋆ +iµ/k ⋆ +iνk ⋆ ] .
(91) . Therefore for β → ∞ the network is Poisson like. In the opposite limit of small structural entropy and β small the P (N k ) distribution (90) develops a fat tail decaying like a power-law (89) with an exponent γ = β+1. Therefore the natural distribution with a small value of the structural entropies are decaying as a power law and and smaller values of the power-law exponent correspond to a smaller value of the structural entropy. When the value of the entropy is minimal, β → 1 the degree distribution (91) has a large tail with an exponent γ → 2.

CONCLUSIONS
In conclusion we have shown that there is a wide set of network ensembles that can be naturally described by statistical mechanics methods. The statistical mechanics method provides the theoretical estimation of the entropy of these ensembles that quantify the cardinality of the network ensembles. We believe that the entropy of randomized ensembles constructed from a given real networks will be of great applicability for inference problems defined on technological social and biological networks. In this paper we have focused on some theoretical problems that can be approached with the use of this quantity. First we have formulated a series of "canonical" or "hidden variables" models that can be used for generating networks with community structure and spatial embedding. Secondly we have focused on the degree distribution of network. The degree distributions are not all equivalent. In fact the associated structural entropy depends strongly on the distribution. In particular the power-law degree distribution with exponent γ and fixed average degree are associated to a structural entropy that decreases with γ. Nevertheless we have shown that power-law degree distributions are the more likely distributions associated to small structural entropy. This shed light on the evidence that power-law networks constitute a large universality class in complex networks with a non trivial level of organization.
This work was supported by IST STREP GENNETEC contract No. 034952.