Sequential Importance Sampling for Bipartite Graphs With Applications to Likelihood-Based Inference

Tech Report Number



The ability to simulate graphs with given properties is important for the analysis of social networks. Sequential importance sampling has been shown to be particularly effective in estimating the number of graphs adhering to fixed marginals and in estimating the null distribution of test statistics. This paper builds on the work of Chen et al. (2005), providing an intuitive explanation of the sequential importance sampling algorithm as well as several examples to illustrate how the algorithm can be implemented for bipartite graphs. We examine the performance of sequential importance sampling for likelihood-based inference in comparison with Markov chain Monte Carlo, and find little empirical evidence to suggest that sequential importance sampling outperforms Markov chain Monte Carlo, even for sparse graphs or graphs with skewed marginals.

KEY WORDS: Sequential importance sampling; bipartite graph; Markov chain Monte Carlo; likelihood inference; graph counting;


tr502.pdf742.06 KB