A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees

Abstract

Random graphs with a given degree sequence are a useful model capturing several features absent in the classical Erd˝os-R´enyi model, such as dependent edges and non-binomial degrees. In this paper, we use a characterization due to Erd˝os and Gallai to develop a sequential algorithm for generating a random labeled graph with a given degree sequence. The algorithm is easy to implement and allows surprisingly efficient sequential importance sampling. Applications are given, including simulating a biological network and estimating the number of graphs with a given degree sequence.