Sampling for Conditional Inference on Network Data

Abstract

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.

Keywords:

• Approximate counting
• Exact test
• Random graphs
• Random networks
• Sequential importance sampling

Acknowledgments

This work was supported in part by the National Science Foundation grants DMS-08-06175 and DMS-11-06796. The authors thank the editor, the associate editor, and two referees for valuable suggestions.