Publication: A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
Loading...
Open/View Files
Date
2009-03-27T18:05:03Z
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Blitzstein, Joseph K., and Persi Diaconis. 2006. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Unpublished paper.
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.
Description
Other Available Sources
Research Data
Keywords
random graphs, sequential importance sampling, exponential models, random networks, randomized generating algorithms, graphical degree sequences
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service