Internet Mathematics
- Internet Math.
- Volume 6, Number 4 (2010), 489-522.
A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees
Joseph Blitzstein and Persi Diaconis
Full-text: Open access
Abstract
Random graphs with given degrees are a natural next step in complexity beyond the Erdős–Rényi model, yet the degree constraint greatly complicates simulation and estimation. We use an extension of a combinatorial characterization due to Erdős 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 for surprisingly efficient sequential importance sampling. The resulting probabilities are easily computed on the fly, allowing the user to reweight estimators appropriately, in contrast to some ad hoc approaches that generate graphs with the desired degrees but with completely unknown probabilities. Applications are given, including simulating an ecological network and estimating the number of graphs with a given degree sequence.
Article information
Source
Internet Math. Volume 6, Number 4 (2010), 489-522.
Dates
First available in Project Euclid: 13 October 2011
Permanent link to this document
http://projecteuclid.org/euclid.im/1318514519
Mathematical Reviews number (MathSciNet)
MR2809836
Zentralblatt MATH identifier
06037365
Citation
Blitzstein, Joseph; Diaconis, Persi. A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees. Internet Math. 6 (2010), no. 4, 489--522. http://projecteuclid.org/euclid.im/1318514519.
A K Peters, Ltd.
- You have access to this content.
- You have partial access to this content.
- You do not have access to this content.
More like this
- The importance sampling technique for understanding rare events in Erdős–Rényi random graphs
Bhamidi, Shankar, Hannig, Jan, Lee, Chia Ying, and Nolen, James, Electronic Journal of Probability, 2015 - Random graphs with a given degree sequence
Chatterjee, Sourav, Diaconis, Persi, and Sly, Allan, The Annals of Applied Probability, 2011 - Discretized normal approximation by Stein’s method
Fang, Xiao, Bernoulli, 2014
- The importance sampling technique for understanding rare events in Erdős–Rényi random graphs
Bhamidi, Shankar, Hannig, Jan, Lee, Chia Ying, and Nolen, James, Electronic Journal of Probability, 2015 - Random graphs with a given degree sequence
Chatterjee, Sourav, Diaconis, Persi, and Sly, Allan, The Annals of Applied Probability, 2011 - Discretized normal approximation by Stein’s method
Fang, Xiao, Bernoulli, 2014 - Expansion and Lack Thereof in Randomly Perturbed Graphs
Flaxman, Abraham D., Internet Mathematics, 2007 - The densest subgraph problem in sparse random graphs
Anantharam, Venkat and Salez, Justin, The Annals of Applied Probability, 2016 - On the degree properties of generalized random graphs
Shi, Yi Y. and Qian, Hong, Communications in Mathematical Sciences, 2009 - Adaptive multinomial matrix completion
Klopp, Olga, Lafond, Jean, Moulines, Éric, and Salmon, Joseph, Electronic Journal of Statistics, 2015 - Exact thresholds for Ising–Gibbs samplers on general graphs
Mossel, Elchanan and Sly, Allan, The Annals of Probability, 2013 - A pseudo empirical likelihood approach for stratified samples with nonresponse
Fang, Fang, Hong, Quan, and Shao, Jun, The Annals of Statistics, 2009 - A Berry–Esseen bound with applications to vertex degree counts in the Erdős–Rényi random graph
Goldstein, Larry, The Annals of Applied Probability, 2013