Correlated Random Networks

TLDR

Uncorrelated random networks, such as Erdős–Rényi graphs, represent the simplest cases. The study develops a statistical theory of networks and investigates interactions that generate correlations between adjacent vertices. Networks are defined by adjacency matrices and partition functions \(Z=\sum\exp(-\beta H(c))\), and the authors analyze interactions \(H(c)\) that produce correlations, especially in optimized networks as \(\beta\to\infty\). These correlations are argued to be a crucial signature of evolutionary design in biological networks.

Abstract

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= summation operator exp([-betaH(c)]. The simplest cases are uncorrelated random networks such as the well-known Erdös-Rényi graphs. Here we study more general interactions H(c) which lead to correlations, for example, between the connectivities of adjacent vertices. In particular, such correlations occur in optimized networks described by partition functions in the limit beta--> infinity. They are argued to be a crucial signature of evolutionary design in biological networks.