State-Dependent Kernel Selection for Conditional Sampling of Graphs

Abstract

This article introduces new efficient algorithms for two problems: sampling conditional on vertex degrees in unweighted graphs, and conditional on vertex strengths in weighted graphs. The resulting conditional distributions provide the basis for exact tests on social networks and two-way contingency tables. The algorithms are able to sample conditional on the presence or absence of an arbitrary set of edges. Existing samplers based on MCMC or sequential importance sampling are generally not scalable; their efficiency can degrade in large graphs with complex patterns of known edges. MCMC methods usually require explicit computation of a Markov basis to navigate the state space; this is computationally intensive even for small graphs. Our samplers do not require a Markov basis, and are efficient both in sparse and dense settings. The key idea is to carefully select a Markov kernel on the basis of the current state of the chain. We demonstrate the utility of our methods on a real network and contingency table. Supplementary materials for this article are available online.

Keywords:

• Contingency table
• Degree sequence
• Exact test
• Markov chain Monte Carlo
• Random network

Acknowledgments

The authors thank the editor, associate editor, and two anonymous referees for their comments that have substantially improved the article.

Additional information

Funding

The work of the first author was supported by an EPSRC Research Studentship.