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

DSpace/Manakin Repository

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

Citable link to this page

 

 
Title: A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
Author: Blitzstein, Joseph; Diaconis, Persi

Note: Order does not necessarily reflect citation order of authors.

Citation: Blitzstein, Joseph K., and Persi Diaconis. 2006. A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Unpublished paper.
Full Text & Related Files:
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.
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2757225
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters