Defining statistical ensembles of random graphs

A thorough discussion of the statistical ensemble of scale-free connected random tree graphs is presented. Methods borrowed from field theory are used to define the ensemble and to study analytically its properties. The ensemble is characterized by two global parameters, the fractal and the spectral dimensions, which are explicitly calculated. It is discussed in detail how the geometry of the graphs varies when the weights of the nodes are modified. The stability of the scale...

We discuss various aspects of the statistical formulation of the theory of random graphs, with emphasis on results obtained in a series of our recent publications.

We define a statistical ensemble of non-degenerate graphs, i.e. graphs without multiple- and self-connections between nodes. The node degree distribution is arbitrary, but the nodes are assumed to be uncorrelated. This completes our earlier publication \cite{bck}, where trees and degenerate graphs were considered. An efficient algorithm generating non-degenerate graphs is constructed. The corresponding computer code is available on request. Finite-size effects in scale-free g...

We introduce and study a class of exchangeable random graph ensembles. They can be used as statistical null models for empirical networks, and as a tool for theoretical investigations. We provide general theorems that carachterize the degree distribution of the ensemble graphs, together with some features that are important for applications, such as subgraph distributions and kernel of the adjacency matrix. These results are used to compare to other models of simple and compl...

We study the tailoring of structured random graph ensembles to real networks, with the objective of generating precise and practical mathematical tools for quantifying and comparing network topologies macroscopically, beyond the level of degree statistics. Our family of ensembles can produce graphs with any prescribed degree distribution and any degree-degree correlation function, its control parameters can be calculated fully analytically, and as a result we can calculate (a...

We develop a statistical mechanics approach for random networks with uncorrelated vertices. We construct equilibrium statistical ensembles of such networks and obtain their partition functions and main characteristics. We find simple dynamical construction procedures that produce equilibrium uncorrelated random graphs with an arbitrary degree distribution. In particular, we show that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting...

In statistical mechanical investigations on complex networks, it is useful to employ random graphs ensembles as null models, to compare with experimental realizations. Motivated by transcription networks, we present here a simple way to generate an ensemble of random directed graphs with, asymptotically, scale-free outdegree and compact indegree. Entries in each row of the adjacency matrix are set to be zero or one according to the toss of a biased coin, with a chosen probabi...

We present a statistical mechanics approach for the description of complex networks. We first define an energy and an entropy associated to a degree distribution which have a geometrical interpretation. Next we evaluate the distribution which extremize the free energy of the network. We find two important limiting cases: a scale-free degree distribution and a finite-scale degree distribution. The size of the space of allowed simple networks given these distribution is evaluat...

In this article we give an in depth overview of the recent advances in the field of equilibrium networks. After outlining this topic, we provide a novel way of defining equilibrium graph (network) ensembles. We illustrate this concept on the classical random graph model and then survey a large variety of recently studied network models. Next, we analyze the structural properties of the graphs in these ensembles in terms of both local and global characteristics, such as degree...

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 th...