A Sequential Algorithm for Generating Random Graphs

Abstract

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-\tau })$, our algorithm generates almost uniform random graphs with that degree sequence in time $O(m{d}_{\max })$ where $m=\f{1}{2}\sum_id_i$ is the number of edges in the graph and $\tau$ is any positive constant. The fastest known algorithm for uniform generation of these graphs McKay Wormald (1990) has a running time of $O(m^2{d}_{\max }^2)$. Our method also gives an independent proof of McKay's estimate McKay (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(m^{1/4-\tau })$. Moreover, we show that for $d=O(n^{1/2-\tau })$, our algorithm can generate an asymptotically uniform $d$-regular graph. Our results improve the previous bound of $d=O(n^{1/3-\tau })$ due to Kim and Vu (2004) for regular graphs.

39 pages

References in corpus (1)

• Efficient importance sampling for binary contingency tables

Cited by in corpus (9)

• Metrics for Graph Comparison: A Practitioner's Guide
• Cost-efficient vaccination protocols for network epidemiology
• Dimensionality of social networks using motifs and eigenvalues
• Measuring and Modeling Behavioral Decision Dynamics in Collective Evacuation
• Approximation Algorithm for Fault-Tolerant Virtual Backbone in Wireless Sensor Networks
• Reticula: A temporal network and hypergraph analysis software package
• Fixation properties of multiple cooperator configurations on regular graphs
• The behavior of rich-club coefficient in scale-free networks
• Disease Transmission on Random Graphs Using Edge-Based Percolation