Institute for Mathematical Behavioral Sciences

General random graphs (i.e., stochastic models for networks incorporating heterogeneity and/or dependence among edges) are increasingly widely used in the study of social and other networks, but few techniques other than simulation have been available for studying their behav ior. Random graphs with independent edges (i.e., the Bernoulli graphs), on the other hand, are well-studied, and a large literature exists regarding their properties. In this paper, we demonstrate a method for leveraging this knowledge by constructing families of Bernoulli graphs that bound the behavior of an arbitrary random graph in a well-de�ned sense. By studying the behavior of these Bernoulli graph bounds, one can thus constrain the properties of a given random graph. We illustrate the utility of this approach via application to several problems from the social network literature, including identifying degeneracy in Markov graph models, studying the potential impact of tie formation mechanisms on epidemic potential in sexual contact networks, and robustness testing of inhomogeneous Bernoulli models based on geographical covariates. Keywords: random graphs, discrete exponential families, Bernoulli graphs, graph theory, social networks