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

• In Event: 425 - Regular Session. Mathematical Sociology

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 often quite difficult in the presence of dependence, generally 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. In many cases, worst-case complexity of the sampling process is no worse than the worst-case complexity of an exact sampler for independent, inhomogeneous binary variables (i.e., order $N$, where $N$ is the number of variables). 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.

Author

• Carter T. Butts, University of California-Irvine