Joint Vertex Degrees in an Inhomogeneous Random Graph Model

Abstract

In a random graph, counts for the number of vertices with given degrees will typically be dependent. We show via a multivariate normal and a Poisson process approximation that, for graphs which have independent edges, with a possibly inhomogeneous distribution, only when the degrees are large can we reasonably approximate the joint counts as independent. The proofs are based on Stein's method and the Stein-Chen method with a new size-biased coupling for such inhomogeneous random graphs, and hence bounds on distributional distance are obtained. Finally we illustrate that apparent (pseudo-) power-law type behaviour can arise in such inhomogeneous networks despite not actually following a power-law degree distribution.

30 pages, 9 figures