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

被引：168

作者：

Blitzstein, Joseph ^{[1
]}

Diaconis, Persi ^{[2
]}

机构：

[1] Harvard Univ, Dept Stat, Cambridge, MA 02138 USA

[2] Stanford Univ, Dept Math & Stat, Stanford, CA 94305 USA

来源：

INTERNET MATHEMATICS | 2011年 / 6卷 / 04期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1080/15427951.2010.557277

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Random graphs with given degrees are a natural next step in complexity beyond the Erdos-Renyi model, yet the degree constraint greatly complicates simulation and estimation. We use an extension of a combinatorial 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 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.

引用

页码：489 / 522

页数：34

共 63 条

[1]

Admiraal R., 2008, J STAT SOFTW, V24, p[8, 1]

[2] A p* primer:: logit models for social networks [J].