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ⁿ with maximum degree dmax=O(m^1/4-τ), our algorithm generates almost uniform random graphs with that degree sequence in time O(mdmax) where m=½Σidi is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs has a running time of O(m ² dmax² ). Our method also gives an independent proof of McKay's estimate (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 dmax=O(m ^1/4-τ).