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 d _max?=O(m ^1/4?τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max?) where $m=frac{1}{2}sum_{i}d_{i}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 d _max=O(m ^1/4−τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max) where m=frac12?_id_im=frac{1}{2}sum_{i}d_{i} is the number of edges in the graph and τ 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 ² d _max²). 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.