The degree sequence of a random graph. I. The models

Brendan D. McKay, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

15 Citations (Scopus)

Abstract

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and 1/2m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X1,..., Xn)|∑ X1 = m}, where X1,..., Xn are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p = p(n), the distribution of the degree sequence can be approximated by {(X1,..., Xn)|∑ X1 is even}, where X1,..., Xn are independent random variables each having the distribution Binom (n - 1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n-k for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t = t(n) as n → ∞.

Original languageEnglish
Pages (from-to)97-117
Number of pages21
JournalRandom Structures & Algorithms
Volume11
Issue number2
DOIs
Publication statusPublished - 1997
Externally publishedYes

Cite this