Defining statistical ensembles of random graphs

The Erdos-Renyi classical random graph is characterized by a fixed linking probability for all pairs of vertices. Here, this concept is generalized by drawing the linking probability from a certain distribution. Such a procedure is found to lead to a static complex network with an arbitrary connectivity distribution. In particular, a scale-free network with the hierarchical organization is constructed without assuming any knowledge about the global linking structure, in contr...

Understanding the subgraph distribution in random networks is important for modelling complex systems. In classic Erdos networks, which exhibit a Poissonian degree distribution, the number of appearances of a subgraph G with n nodes and g edges scales with network size as \mean{G} ~ N^{n-g}. However, many natural networks have a non-Poissonian degree distribution. Here we present approximate equations for the average number of subgraphs in an ensemble of random sparse directe...

Using a maximum entropy principle to assign a statistical weight to any graph, we introduce a model of random graphs with arbitrary degree distribution in the framework of standard statistical mechanics. We compute the free energy and the distribution of connected components. We determine the size of the percolation cluster above the percolation threshold. The conditional degree distribution on the percolation cluster is also given. We briefly present the analogous discussion...

We propose the following model of a random graph on n vertices. Let F be a distribution in R_+^{n(n-1)/2} with a coordinate for every pair i$ with 1 \le i,j \le n. Then G_{F,p} is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X_{ij} \le p. The standard Erd\H{o}s-R\'{e}nyi model is the special case when F is uniform on the 0-1 unit cube. We examine basic properties su...

Various important and useful quantities or measures that characterize the topological network structure are usually investigated for a network, then they are averaged over the samples. In this paper, we propose an explicit representation by the beforehand averaged adjacency matrix over samples of growing networks as a new general framework for investigating the characteristic quantities. It is applied to some network models, and shows a good approximation of degree distributi...

We study a recent model of random networks based on the presence of an intrinsic character of the vertices called fitness. The vertices fitnesses are drawn from a given probability distribution density. The edges between pair of vertices are drawn according to a linking probability function depending on the fitnesses of the two vertices involved. We study here different choices for the probability distribution densities and the linking functions. We find that, irrespective of...

Statistical ensembles of networks, i.e., probability spaces of all networks that are consistent with given aggregate statistics, have become instrumental in the analysis of complex networks. Their numerical and analytical study provides the foundation for the inference of topological patterns, the definition of network-analytic measures, as well as for model selection and statistical hypothesis testing. Contributing to the foundation of these data analysis techniques, in this...

We propose a simple random process inducing various types of random graphs and the scale free random graphs among others. The model is of a threshold nature and differs from the preferential attachment approach discussed in the literature before. The degree statistics of a random graph in our model is governed by the control parameter $\eta$ stirring the pure exponential statistics for the degree distribution (at $\eta=0,$ when a threshold is changed each time a new edge ad...

The science of complex networks is a new interdisciplinary branch of science which has arisen recently on the interface of physics, biology, social and computer sciences, and others. Its main goal is to discover general laws governing the creation and growth as well as processes taking place on networks, like e.g. the Internet, transportation or neural networks. It turned out that most real-world networks cannot be simply reduced to a compound of some individual components. F...

The extreme eigenvalues of connectivity matrices govern the influence of the network structure on a number of network dynamical processes. A fundamental open question is whether the eigenvalues of large networks are well represented by ensemble averages. Here we investigate this question explicitly and validate the concept of ensemble averageability in random scale-free networks by showing that the ensemble distributions of extreme eigenvalues converge to peaked distributions...