Sampling for Conditional Inference on Network Data

• 成果类型: Article
• 署名作者: Zhang, Jingfei; Chen, Yuguo
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459
• DOI: 10.1080/01621459.2012.758587
• 发表日期: 2013
• 页码: 1295-1307
• 关键词: Complex networks; social networks; 0-1 matrices; graphs; distributions; enumeration; models; motifs

摘要

Random graphs with given vertex degrees have been widely used as a model for many real-world complex networks. However, both statistical inference and analytic study of such networks present great challenges. In this article, we propose a new sequential importance sampling method for sampling networks with a given degree sequence. These samples can be used to approximate closely the null distributions of a number of test statistics involved in such networks and provide an accurate estimate of the total number of networks with given vertex degrees. We study the asymptotic behavior of the proposed algorithm and prove that the importance weight remains bounded as the size of the graph grows. This property guarantees that the proposed sampling algorithm can still work efficiently even for large sparse graphs. We apply our method to a range of examples to demonstrate its efficiency in real problems.