A Novel Simulation Method for Binary Discrete Exponential Families, With Application to Social Networks

Abstract

Stochastic models for finite binary vectors are widely used in sociology, with examples ranging from social influence models on dichotomous behaviors or attitudes to models for random graphs. Exact sampling for such models is difficult in the presence of dependence, leading to the use of Markov chain Monte Carlo (MCMC) as an approximation technique. While often effective, MCMC methods have variable execution time, and the quality of the resulting draws can be difficult to assess. Here, we present a novel alternative method for approximate sampling from binary discrete exponential families having fixed execution time and well-defined quality guarantees. We demonstrate the use of this sampling procedure in the context of random graph generation, with an application to the simulation of a large-scale social network using both geographical covariates and dyadic dependence mechanisms.

Keywords:

• discrete exponential families
• random graphs
• statistical simulation

Notes

¹It should be borne in mind that β is a random vector, unlike the fixed vectors of α and γ. However, each β_i depends only on the outcomes preceding it, and is bounded by α_i and γ_i regardless of those outcomes.

²Simulation was performed using the sna (Butts, 2008) and ergm (Hunter et al., 2008) libraries.

³All MCMC-based simulation and inference was performed using ergm (Hunter et al., 2008) and the statnet software suite (Handcock, Hunter, Butts, Goodreau, & Morris, 2008).

⁴Ceteris paribus, enhanced degree variance leads to clustering, since there are fewer ways to avoid creating triangles when edges are concentrated on a smaller set of nodes than when edges are evenly dispersed through the graph.