A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
MetadataShow full item record
CitationBlitzstein, Joseph K., and Persi Diaconis. 2006. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Unpublished paper.
AbstractRandom 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.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:2757225
- FAS Scholarly Articles