Correlated random networks

We develop a statistical theory of networks. A network is a set of vertices and links given by its adjacency matrix $\c$, and the relevant statistical ensembles are defined in terms of a partition function $Z=\sum_{\c} \exp {[}-\beta \H(\c) {]}$. The simplest cases are uncorrelated random networks such as the well-known Erd\"os-R\'eny graphs. Here we study more general interactions $\H(\c)$ which lead to {\em correlations}, for example, between the connectivities of adjacent vertices. In particular, such correlations occur in {\em optimized} networks described by partition functions in the limit $\beta \to \infty$. They are argued to be a crucial signature of evolutionary design in biological networks.

Networks describe structures as diverse as the interaction links between proteins in a cell, the wiring of the brain, or the connections of the internet. Recent theoretical work [1,2] has focused on communication networks, and a wealth of quantitative data is now becoming available on networks in molecular biology. Examples include control networks in gene transcription [3], the interaction map of proteins [4], and the pathways of cell metabolism [5]. All these systems consist of many different kinds of molecules linked by complex interactions. Network models are a simplified description, which neglects quantitative aspects of these interactions and focuses solely on their pathways.
A network is a set of vertices i = 1, . . . , N connected by links. It is uniquely defined by the adjacency matrix c, whose entries are c ij = 1 if there is a link from i to j and c ij = 0 otherwise. We consider here networks with undirected links, where c is symmetric. The connectivity or degree of a vertex is then defined as the total number of links connected to it, k i ≡ j c ij . The distance d ij between two vertices i and j is the number of links along the shortest path connecting them [6]. We assume the vertices are labeled (for example, by their biochemical identity), so that the correspondence between adjacency matrix c and its graph is one-to-one [7].
Networks with an irregular wiring naturally lend themselves to a statistical description [6]. We discuss here the equilibrium statistics of networks. The partition function Z can be defined as a sum over all graphs with a fixed number N of vertices and a fixed number Averages over this ensemble are denoted by . . . . Alternatively one can define Z with an arbitrary number of links adjusted by a suitable chemical potential. The ensembles of relevance here have a finite average connectivity κ ≡ 2M/N . For fixed κ, the distribution of connectivities, becomes asymptotically independent of N , implying that typical adjacency matrices c become sparse for large N . This is the case of interest for applications. A satisfactory mathematical theory exists to date only for what we call uncorrelated random networks [8,9]. In this case, the Hamiltonian depends only on single-point connectivities, leading to p(k) ∼ exp[−βf (k)−µk]/k! where the constant of proportionality is fixed by normalization and µ is adjusted to give the correct average connectivity. Since all graphs with the same connectivities k 1 , . . . , k N have the same statistical weight, this ensemble ensures the maximally random wiring compatible with the distribution p(k). The simplest example is the well-known Erdös-Rény graphs, where βH = 0 and p(k) is a Poissonian. Many natural networks are, however, not of this type. The simplest kind of correlations occur if the joint distribution of connectivities for neighboring vertices, differs from its form for uncorrelated random networks, q 0 (k, k ′ ) = (kk ′ /κ 2 )p(k)p(k ′ ). Higher correlations can be defined in a similar way [10]. Connectivity correlations have been found in growth models of communication networks [11,12] as well as in data of genetic and protein networks [13,14].
These observations call for a statistical theory of more general ensembles called correlated random networks, which is the subject of this Letter. The ensembles of interest are characterized by finite distributions p(k) and q(k, k ′ ) in the limit of large N . One then expects a universal logarithmic scaling of the average distance d ij between vertices, i,j d ij /N 2 Ω ∼ log N Ω , in any connected component Ω with N Ω nodes [15]. This is consistent with our numerical findings. Hence, correlated random networks maintain a sparse connectivity matrix and are locally tree-like. The 'inverse temperature' β in (1) measures the deviation from Erdös-Rény graphs. Quite remarkably, these structural properties are preserved in the limit β → ∞, where we obtain nontrivial optimized networks. Ensembles of this kind generically have strong correlations.
The simplest type of Hamiltonian producing correlations has nearest-neighbor connectivity interactions, where g(k, k ′ ) is some function of the connectivities. The resulting class of graph ensembles can be seen as a showcase for correlated random networks where analytic expressions can be derived. Higher order correlations are generated by Hamiltonians with next-nearest neighbor interactions etc. We also study a Hamiltonian often called the diameter of the graph. For λ > 0 and a suitable scaling λ ∼ 1/(N log N ), this Hamiltonian is found to generate compactified networks with finite p(k) and q(k, k ′ ), provided the extra term H 1 stabilizes the network against collapse to a star. Compactified networks occur in communication and transport [16], and may play a role in biology [17,18]. For example, distance-optimized networks obtained from (6) show an abundance of high-connectivity vertices (hubs) which are preferentially connected to peripheral vertices of low connectivity. A very similar structure (with even more pronounced hubs) can also be obtained from local interactions of the form (5). Typical graphs are shown in Fig 1. To establish these results, we first discuss the analytical treatment of local interactions, choosing a generic Hamiltonian of the form H = H 1 + H 2 given by (3) and (5). From the partition function (1), the free energy is derived by using an integral representation for the constraints due to the connectivity k i at each vertex and making a Hubbard-Stratonovich transformation. The resulting integral can be evaluated in a saddle-point approximation, yielding the reduced free energy per vertex in the thermodynamic limit, The 'order parameters' Q k and the chemical potential µ have to be determined self-consistently from the saddlepoint condition. This form is closely related to a fieldtheoretic approach [9,19,20], where networks appear as the Feynman diagrams of a Gaussian integral with a propagator matrix G kk ′ = exp[−βg(k, k ′ )] − 1 and interactions as specified by the last term in (7). Notice the super-extensive scaling of the entropy, (κ/2) log N , which reflects that unlike in a regular lattice, each vertex can be connected to all N − 1 other vertices. The last term in (7) is directly related to the degree distribution, where C is a normalization constant. For example, a power-law tail in p(k) may be generated by a suitable choice of the weights f (k) but it is not generic. A more detailed account of networks with generic local interactions will be published elsewhere [21]. Here we turn to the simplest Hamiltonian with local interactions producing nontrivial optimized networks, see Fig. 1. It has the form H L = H 1 + H 2 with H 1 (c) = −(1/2) i k 2 i + η i k 3 i and H 2 (c) = ζ i<j δ ki,1 c ij δ kj ,1 . The first term (1/2) i k 2 i = (1/2) ijk c ik c kj gives the number of paths of length two on the graph. It rewards the formation of hubs, i.e. highly connected vertices, which in turn lead to short distances. In fact this term has the maximally compact, starlike configuration as its ground state. The collapse to a star, where the connectivity of the central vertex scales with the size of the graph, however, is prevented by the regularization term η i k 3 i . The correlation term H 2 with ζ → ∞ suppresses single, isolated links connecting two vertices of connectivity 1. Without this term an extensive number of isolated links remains even in the limit β → ∞ leading to graphs with a large number of disconnected parts. A minimal connectivity of 1 of each vertex is enforced. For this Hamiltonian, the free energy (7) contains only one non-zero order parameter Q 1 given by p(1) = κ Q1 Q1−e −µ . The chemical potential µ is determined by k kp(k) = κ. Remarkably, the connectivity correlation can be obtained from H 2 and single-vertex quantities, The constant of proportionality is fixed by normalization and the t k are determined by the marginal distribution k ′ q(k, k ′ ) = kp(k)/κ, giving t 1 = κ/(T (κ − p(1))) and The properties of optimized networks resulting from the Hamiltonian H L are readily inferred from Eqs. (8) and (9). At finite values β one finds that the degree distribution (8) has an exponentially decaying tail. In order to analyze the limit β → ∞, we replace the sum over k in (7) by an integral. One finds that the vertices arrange themselves into hubs of connectivity (10) and peripheral vertices of connectivity 1. The peripheral vertices are connected only to hubs, while the hubs form an uncorrelated random network. A remarkably similar structure is found for compactified networks generated by the Hamiltonian with nonlocal interactions H = H 1 + λH d with H d given by (6) and H 1 = η i k 3 i . For λ > 0, the nonlocal part H d favors networks with short distances, while H 1 prevents the collapse to a star as before. Hence, by choosing λ = 2/(N log N ), one obtains a well-defined thermodynamic limit with the average distance between vertices scaling as log N . We have studied this ensemble, as well as the case of local interactions H L , by a Monte-Carlo link dynamics. Starting, for example, from an Erdös-Reny graph, randomly chosen links are moved to previously unlinked vertex pairs with probability p = min(1, exp[−β∆H]) where ∆H denotes the corresponding change in the Hamiltonian. The minimum degree of 1 is enforced throughout, self-links are excluded [7]. No dependence on the initial conditions has been found. For the local Hamiltonian we use a network with N = 200, κ = 2.4, η = 0.03, for the nonlocal Hamiltonian we use N = 100, κ = 2.4, η = 0.001. We averaged over 100 samples. Fig. 2 juxtaposes analytical and numerical results for local interactions on the left with numerical results for nonlocal interactions on the right. The connectivity distribution p(k) shows the formation of high-connectivity hubs in both cases. For local interactions the hub connectivity is given by (10), for non-local interaction the distribution remains broad even in the limit β → ∞ (Fig. 2(a)) [22]. Lowconnectivity vertices are preferentially attached to hubs as indicated by the peaks at q(1, k * ) for local interactions and the corresponding peaks of q(k, k ′ ) for nonlocal interactions (Fig. 2(b)). The deviation from uncorrelated random networks is measured by the relative entropy S(q|q 0 ) = k,k ′ q(k, k ′ ) log q(k,k ′ ) q0(k,k ′ ) . In a single network of size N , we obtain the estimate S(q|q 0 ) from the observed frequenciesq(k, k ′ ) andp(k), withq 0 (k, k ′ ) = (kk ′ /κ 2 )p(k)p(k ′ ). We then generate a sufficient number of uncorrelated random networks [24] with frequenciesq α (k, k ′ ) and sampling entropies S(q α |q 0 ); their average and standard deviation are denoted by S 0 (q 0 ) and ∆S 0 (q 0 ) respectively. Connectivity correlations in the original network are significant if S(q|q 0 ) − S 0 (q 0 ) ∆S 0 (q 0 ). This is typically the case above a certain optimization degree β on, as shown by the ensemble averages over 10 samples S(q|q 0 ) , S 0 (q 0 ) , and ∆S 0 (q 0 ) shown in figure 2c).
Both kinds of networks become more compactified with increasing β, as shown by the average inverse distance K ≡ (2/N (N − 1)) i<j d −1 ij (Fig. 2(d)) [23]. We also plot K for the equivalent uncorrelated random networks; no such compactification is seen. Hence, the one-point distribution p(k) may miss important functional properties. On the other hand, the nonlocally interacting networks and their equivalent locally interacting counterparts (constructed to have the same p(k) and q(k, k ′ )) have a very similar degree of compactification [24]. This illustrates how optimization induces correlations.
In summary, we have shown how interactions shape the structure of a network. Hamiltonians beyond the 'single-vertex' form (3) generate correlations such as a neighbor connectivity distribution q(k, k ′ ) which differs from that in uncorrelated networks. Higher correlations can be defined in a similar way [10]. These correlations provide a more detailed fingerprint of the interactions present than the single-point connectivity distribution p(k). This observation should carry over to the dynamical rules for non-equilibrium ensembles such as the wellknown growth models [1,11].
In transcription control networks, structural motifs have been identified that can be expressed in terms of connectivity correlations [13]. Such correlations have also been observed in protein networks [14]. In view of our findings for optimized networks, they appear to be a natural consequence of the underlying dynamics and functional optimization. We expect the data to give important information on the underlying design principles of networks and on the selective forces governing their evolution. Reverse engineering seems feasible, with the aim of inferring the relevant dynamics from the data. The nonequilibrium theory of correlated random networks will thus be an important avenue for future research.
k, l at random with uniform probability and rewire them as i, k and j, l. Repeating this procedure sufficiently many times leaves p(k) invariant but destroys all higher correlations. It has been used in ref. [14] for protein networks. Similarly, the equivalent locally correlated network is obtained by swapping only links with ki = k l and kj = k l , which leaves p(k) and q(k, k ′ ) invariant but destroys all higher correlations.