A Sequential Algorithm for Generating Random Graphs

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d(i))(i=1)(n) with maximum degree d(max) = O(m(1/4-iota)), our algorithm generates almost uniform random graphs with that degree sequence in time O(md(max)) where m = 1/2 Sigma(i) d(i) is the number of edges in the graph and iota is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms 11(1): 52-67, 1990) has a running time of O(m(2)d(max)(2)). Our method also gives an independent proof of McKay's estimate (McKay in Ars Combinatoria A 19: 15-25, 1985) for the number of such graphs. We also use sequential importance sampling to derive fully Polynomial-time Randomized Approximation Schemes (FPRAS) for counting and uniformly generating random graphs for the same range of d(max) = O (n(1/4-iota)). Moreover, we show that for d = O(n(1/2-iota)), our algorithm can generate an asymptotically uniform d-regular graph. Our results improve the previous bound of d = O (n(1/3-iota)) due to Kim and Vu (Adv. Math. 188: 444-469, 2004) for regular graphs.