Xiaoqing Zhu

Post date: Aug 31, 2013 4:04:36 AM

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

Random graphs with a given degree sequence are a useful model capturing several features absent in the classical Erdos-Renyi model, such as dependent edges and non-binomial degrees. In this paper, we use a characterization due to Erdos 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.