Premium
The degree sequence of a random graph. I. The models
Author(s) -
McKay Brendan D.,
Wormald Nicholas C.
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199709)11:2<97::aid-rsa1>3.0.co;2-o
Subject(s) - mathematics , combinatorics , joint probability distribution , random variable , degree (music) , binomial distribution , random graph , degree distribution , binomial (polynomial) , vertex (graph theory) , discrete mathematics , distribution (mathematics) , marginal distribution , statistics , graph , mathematical analysis , physics , acoustics , complex network
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 ½ m edges. For a wide range of values of m , this distribution is almost everywhere in close correspondence with the conditional distribution {( X 1 ,…, X n ) | ∑ X i = m }, where X 1 ,…, X n 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 {( X 1 ,…, X> n ) | ∑ X i is even}, where X 1 ,…, X n 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 t th largest degree for all functions t = t ( n ) as n →∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 97–117 (1997)