Sampling strategies for conditional inference on multigraphs

We propose two new methods for sampling undirected, loopless multigraphs with fixed degree. The first is a sequential importance sampling method, with the proposal based on an asymptotic approximation to the total number of multigraphs with fixed degree. The multigraphs and their associated importance weights can be used to approximate the null distribution of test statistics and additionally estimate the total number of multigraphs. The second is a Markov chain Monte Carlo method that samples multigraphs based on similar moves used to sample contingency tables with fixed margins. We apply both methods to a number of examples and demonstrate excellent performance.