ABSTRACT
Generation of deviates from random graph models with nontrivial edge dependence is an increasingly important problem. Here, we introduce a method which allows perfect sampling from random graph models in exponential family form (“exponential family random graph” models), using a variant of Coupling From The Past. We illustrate the use of the method via an application to the Markov graphs, a family that has been the subject of considerable research. We also show how the method can be applied to a variant of the biased net models, which are not exponentially parameterized.
Acknowledgments
The author would like to thank Johan Koskinen, Mark Handcock, David Hunter, and John Skvoretz for their helpful input.
Funding
This research was supported by ONR award # N00014-08-1-1015 and NSF award IIS-1526736.
Notes
1 For simplicity, we take to be parameterized with respect to the counting measure on
. Where other reference measures are desired (e.g., Krivitsky et al.’s (2011) constant mean degree reference), this can be accomplished by folding them into
.
2 Note that we cannot simply take , since the coalescence point is not an independent draw from the equilibrium distribution of
. Fixing the sampling time in advance resolves this difficulty.
3 Skvoretz et al. (Citation2004) also considered higher order approximations, which may not suffer similar difficulties.
4 Such chains (based on approximate full conditionals with no well-formed joint distribution) are sometimes called pseudo-Gibbs samplers (Chen & Ip, 2014).