TY - JOUR
T1 - The degree sequence of a random graph. I. The models
AU - McKay, Brendan D.
AU - Wormald, Nicholas C.
PY - 1997
Y1 - 1997
N2 - 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 → ∞.
AB - 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 → ∞.
UR - http://www.scopus.com/inward/record.url?scp=0031475726&partnerID=8YFLogxK
U2 - 10.1002/(SICI)1098-2418(199709)11:2<97::AID-RSA1>3.0.CO;2-O
DO - 10.1002/(SICI)1098-2418(199709)11:2<97::AID-RSA1>3.0.CO;2-O
M3 - Article
AN - SCOPUS:0031475726
SN - 1042-9832
VL - 11
SP - 97
EP - 117
JO - Random Structures and Algorithms
JF - Random Structures and Algorithms
IS - 2
ER -