Tractable and Consistent Random Graph Models
We define a general class of network formation models, Statistical Exponential Random Graph Models (SERGMs), that nest standard exponential random graph models (ERGMs) as a special case. We provide the first general results on when these models' (including ERGMs) parameters estimated from the observation of a single network are consistent (i.e., become accurate as the number of nodes grows). Next, addressing the problem that standard techniques of estimating ERGMs have been shown to have exponentially slow mixing times for many specifications, we show that by reformulating network formation as a distribution over the space of sufficient statistics instead of the space of networks, the size of the space of estimation can be greatly reduced, making estimation practical and easy. We also develop a related, but distinct, class of models that we call subgraph generation models (SUGMs) that are useful for modeling sparse networks and whose parameter estimates are also directly and easily estimable, consistent, and asymptotically normally distributed. Finally, we show how choice-based (strategic) network formation models can be written as SERGMs and SUGMs, and apply our models and techniques to network data from rural Indian villages.
We thank Isaiah Andrews, Gabriel Carroll, Victor Chernozhukov, Esther Duflo, Marcel Fafchamps, Ben Golub, Bryan Graham, Bo Honore, Randall Lewis, Angelo Mele, Eduardo Morales, Stephen Nei, Elie Tamer, Juan Pablo Xandri and Yiqing Xing for helpful discussions and/or comments on earlier drafts, and especially Andres Drenik for valuable research assistance. We thank participants at the Simons Workshop at Berkeley on Unifying Theory and Experiments for Large-Scale Networks, the Princeton Econometrics Seminar, and the Second Economics of Networks Conference (Essex). Chandrasekhar is grateful for support from the NSF Graduate Research Fellowship Program and NSF grant SES-1156182. Jackson gratefully acknowledges financial support from the NSF under grants SES-0961481 and SES-1155302 and from grant FA9550-12-1-0411 from the AFOSR and DARPA, and ARO MURI award No. W911NF-12-1-0509. The views expressed herein are those of the authors and do not necessarily reflect the views of the National Bureau of Economic Research.