How to calculate the main characteristics of random uncorrelated networks

In random graph models, the degree distribution of an individual node should be distinguished from the (empirical) degree distribution of the graph that records the fractions of nodes with given degree. We introduce a general framework to explore when these two degree distributions coincide asymptotically in large homogeneous random networks. The discussion is carried under three basic statistical assumptions on the degree sequences: (i) a weak form of distributional homogene...

We propose a consistent approach to the statistics of the shortest paths in random graphs with a given degree distribution. This approach goes further than a usual tree ansatz and rigorously accounts for loops in a network. We calculate the distribution of shortest-path lengths (intervertex distances) in these networks and a number of related characteristics for the networks with various degree distributions. We show that in the large network limit this extremely narrow inter...

We offer a solution to a long-standing problem in the physics of networks, the creation of a plausible, solvable model of a network that displays clustering or transitivity -- the propensity for two neighbors of a network node also to be neighbors of one another. We show how standard random graph models can be generalized to incorporate clustering and give exact solutions for various properties of the resulting networks, including sizes of network components, size of the gian...

The classical result of Erdos and Renyi shows that the random graph G(n,p) experiences sharp phase transition around p=1/n - for any \epsilon>0 and p=(1-\epsilon)/n, all connected components of G(n,p) are typically of size O(log n), while for p=(1+\epsilon)/n, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime p=(1+\epsilon)/n, the random gr...

We introduce a very general model of an inhomogenous random graph with independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p=c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied. We show that under one very weak assumption (that the expected number o...

The weak component generalizes the idea of connected components to directed graphs. In this paper, an exact criterion for existence of the giant weak component is derived for directed graphs with arbitrary bivariate degree distributions. In addition we consider a random process for evolving directed graphs with bounded degrees. The bounds are not the same for different vertices but satisfy a pre-defined distribution. The analytic expression obtained for the evolving degree di...

The exponential family of random graphs represents an important and challenging class of network models. Despite their flexibility, conventionally used exponential random graphs have one shortcoming. They cannot directly model weighted networks as the underlying probability space consists of simple graphs only. Since many substantively important networks are weighted, this limitation is especially problematic. We extend the existing exponential framework by proposing a generi...

Statistical properties of evolving random graphs are analyzed using kinetic theory. Treating the linking process dynamically, structural characteristics such as links, paths, cycles, and components are obtained analytically using the rate equation approach. Scaling laws for finite systems are derived using extreme statistics and scaling arguments.

We propose a general approach to the description of spectra of complex networks. For the spectra of networks with uncorrelated vertices (and a local tree-like structure), exact equations are derived. These equations are generalized to the case of networks with correlations between neighboring vertices. The tail of the density of eigenvalues $\rho(\lambda)$ at large $|\lambda|$ is related to the behavior of the vertex degree distribution $P(k)$ at large $k$. In particular, as ...

A network is said to have the properties of a small world if a suitably defined average distance between any two nodes is proportional to the logarithm of the number of nodes, $N$. In this paper, we present a novel derivation of the small-world property for Gilbert-Erd\"os-Renyi random networks. We employ a mean field approximation that permits the analytic derivation of the distribution of shortest paths that exhibits logarithmic scaling away from the phase transition, infer...