Defining statistical ensembles of random graphs

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

Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results...

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

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

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

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

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

In this work we introduce an energy function in order to study finite scale free graphs generated with different models. The energy distribution has a fractal pattern and presents log periodic oscillations for high energies. This oscillations are related to a discrete scale invariance of certain graphs, that is, there are preferred scaling ratios suggesting a hierarchical distribution of node degrees. On the other hand, small energies correspond to graphs with evenly distribu...