Exponential Random Graph Models (ERGMs)

Last update: 16 Dec 2024 13:14
First version: 4 April 2012 (or earlier?)

See exponential families and network data analysis, naturally.

Around 2011, I set out to show that maximum likelihood estimation is consistent for ERGMs, because they seemed like the best kind of network model available. Doing so radically changed my perspective on these models; for instance, I became convinced that maximum likelihood generally isn't consistent for them, because these models aren't even self-consistent about what happens as we see more data. But that story is a little long to tell here; see here, or just read the paper. (In retrospect, some of the same issues were pointed out by Snijders (2010), a paper I absolutely should have known about, but didn't.)

--- Although many of the relevant papers appear in the journal Social Networks, published by Elsevier, a company known to also publish advertising disguised as peer-reviewed scientific journals (e.g., The Australasian Journal of Bone and Joint Medicine), I know of no particular reason to believe that their findings are actually meretricious propaganda on behalf of a paying client. It would, however, be better if the community would shift to a journal whose publisher did not pollute the process of scientific communication whenever it was profitable to do so.

Peter J. Carrington, John Scott and Stanley Wasserman (eds.), Models and Methods in Social Network Analysis [Many, but not all, of the papers are based on using ERGMs.]
Steven M. Goodreau, James A. Kitts and Martina Morris, "Birds of a Feather, Or Friend of a Friend?: Using Exponential Random Graph Models to Investigate Adolescent Social Networks", Demography 46 (2009): 103--125 [In addition to the substantive findings, this is a great introduction to the approach.]
Mark S. Handcock, David R. Hunter, Carter T. Butts, Steven M. Goodreau, and Martina Morris (eds.), "Statistical Modeling of Social Networks with 'statnet'", special volume (24) of the Journal of Statistical Software (2008) [Introduction to a whole issue on the ERGM approach.]

Shankar Bhamidi, Guy Bresler and Allan Sly, "Mixing time of exponential random graphs", Annals of Applied Probability 21 (2011): 2146--2170, arxiv:0812.2265 [Extended abstract in FOCS 2008 conference proceedings]
Arun Chandrasekhar, Matthew O. Jackson, "Tractable and Consistent Random Graph Models", arxiv:1210.7375
Sourav Chatterjee and Persi Diaconis, "Estimating and Understanding Exponential Random Graph Models", arxiv:1102.2650 [Results on conditions under which the mean field approximation for ERGMs becomes exact, and they consequently grow indistinguishable from simple Erdos-Renyi models.]
Katherine Faust and John Skvoretz, "Comparing Networks Across Space and Time, Size and Species", Sociological Methodology 32 (2002): 267--299 [Though see my paper with Alessandro Rinaldo]
Stephen E. Fienberg, Alessandro Rinaldo and Yi Zhou, "On the Geometry of Discrete Exponential Families with Applications to Exponential Random Graph Models", arxiv:0901.0026
Diego Garlaschelli and Maria I. Loffredo, "Maximum likelihood: extracting unbiased information from complex networks", cond-mat/0609015 [This is a much-needed corrective to the physics literature, but it makes it sound as though exponential families of random graphs were invented in 2004, and they're the first ones to apply maximum likelihood to network analysis. No doubt these are inadvertent lapses. Definitely worth reading as a first glimpse of how to do parameter estimation correctly. Thanks to Dave Feldman for pointing it out to me.]
Krista Gile and Mark S. Handcock, "Model-based Assessment of the Impact of Missing Data on Inference for Networks" [Working Paper 66, Center for Statistics and the Social Sciences, University of Washington (2006). PDF preprint.]
Mark S. Handcock, "Assessing degeneracy in statistical models of social networks", CSSS working paper 39 (2003)
Mark S. Handcock and Krista J. Gile, "Modeling social networks from sampled data", Annals of Applied Statistics 4 (2010): 5--25, arxiv:1010.0891
Steve Hanneke and Eric Xing, "Discrete Temporal Models for Social Networks", in Airoldi et al. (eds.) above [Extending exponential-family random graph models to dynamic networks. Makes me extra proud to have taught Steve stochastic processes. PDF preprint]
Steve Hanneke, Wenjie Fu, and Eric P. Xing, "Discrete temporal models of social networks", Electronic Journal of Statistics 4 (2010): 585--605
David R. Hunter and Mark S. Handcock, "Inference in curved exponential family models for networks", Journal of Computational and Graphical Statistics 15 (2006): 565--583 [PDF reprint]
Andee Kaplan, Daniel Nordman, Stephen Vardeman, "On the instability and degeneracy of deep learning models", arxiv:1612.01159
Eric D. Kolaczyk and Pavel N. Krivitsky, "On the question of effective sample size in network modeling", arxiv:1112.0840
Pavel N. Krivitsky, "Exponential-Family Random Graph Models for Valued Networks", Electronic Journal of Statistics 6 (2012): 1100--1128, arxiv:1101.1359
Pavel N. Krivitsky, Mark S. Handcock and Martina Morris, "Adjusting for Network Size and Composition Effects in Exponential-Family Random Graph Models", Statistical Methodology 8 (2011): 319--339, arxiv:1004.5328
John Levi Martin, "Comment on 'Geodesic Cycle Length Distributions in Delusional and Other Social Networks' ", Journal of Social Structure 21 (2020): 77--93
Juyong Park and M. E. J. Newman
- "The Statistical Mechanics of Networks", Physical Review E 70 (2004): 066117, arxiv:cond-mat/0405566 [I particularly like the way diagrammatic perturbation theory is introduced]
- "Solution of the 2-star model of a network", Physical Review E 70 (2004): 066146, arxiv:cond-mat/0405457
- "Solution for the properties of a clustered network", Physical Review E 72 (2006): 026136, arxiv:cond-mat/0412579
Garry Robins, Tom Snijders, Peng Wang, Mark Handcock and Philippa Pattison, "Recent developments in exponential random graph (p*) models for social networks", Social Networks 29 (2007): 192--215 [PDF reprint via Prof. Snijders]
Michael Schweinberberg, "Instability, Sensitivity, and Degeneracy in Discrete Exponential Families", Journal of the American Statistical Association 106 (2011): 1361--1370
Tom A. B. Snijders, "Conditional Marginalization for Exponential Random Graph Models", Journal of Mathematical Sociology 34 (2010): 239--252 [Reprint]
Lin Yuan, Sergey Kirshner, Robert Givan, "Estimating Densities with Non-Parametric Exponential Families", arxiv:1206.5036

CRS and Alessandro Rinaldo, "Consistency under Sampling of Exponential Random Graph Models", Annals of Statistics 41 (2013): 508--535, arxiv:1111.3054 [More]

A. Caimo, N. Friel, "Bergm: Bayesian Exponential Random Graphs in R", arxiv:1201.2770
Ruth M. Hummel, David R. Hunter and Mark S. Handcock, "Improving Simulation-Based Algorithms for Fitting ERGMs", Journal of Computational and Graphical Statistics 21 (2012): 920--939
David R. Hunter, Pavel N. Krivitsky and Michael Schweinberger, "Computational Statistical Methods for Social Network Models", Journal of Computational and Graphical Statistics 21 (2012): 856--882
Michael Schweinberger, Pamela Luna, "hergm: Hierarchical Exponential-Family Random Graph Models", Journal of Statistical Software 85 (2018): 1
Nicolò Vallarano, Matteo Bruno, Emiliano Marchese, Giuseppe Trapani, Fabio Saracco, Giulio Cimini, Mario Zanon, Tiziano Squartini, "Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints", Scientific Reports 11 (2021): 15227, arxiv:2101.12625

Carter T. Butts, "Continuous Time Graph Processes with Known ERGM Equilibria: Contextual Review, Extensions, and Synthesis", Journal of Mathematical Sociology 48 (2024): 129--171, arxiv:2203.06948
Pavel N. Krivitsky and Mark S. Handcock, "A Separable Model for Dynamic Networks", arxiv:1011.1937
Michael Schweinberger, "Statistical modelling of network panel data: Goodness of fit", British Journal of Mathematical and Statistical Psychology 65 (2012): 263--281

David Aristoff, Charles Radin, "Emergent structures in large networks", arxiv:1110.1912
James Atwood, Don Towsley, Krista Gile, David Jensen, "Learning to Generate Networks", arxiv:1405.5868
Ginestra Bianconi, "Information theory of spatial network ensembles", arxiv:2206.05614
Arun G. Chandrasekhar, Matthew O. Jackson, "A Network Formation Model Based on Subgraphs", arxiv:1611.07658
Giulio Cimini, Tiziano Squartini, Fabio Saracco, Diego Garlaschelli, Andrea Gabrielli, Guido Caldarelli, "The Statistical Physics of Real-World Networks", arxiv:1810.05095
Frank den Hollander, Maarten Markering, "Breaking of ensemble equivalence for dense random graphs under a single constraint", arxiv:2107.04351
Scott W. Duxbury, "The Problem of Scaling in Exponential Random Graph Models", Sociological Methods and Research 52 (2023) 764--802
Alexander Engstrom, Patrik Noren, "Polytopes from Subgraph Statistics", arxiv:1011.3552
Richard G. Everitt, "Bayesian Parameter Estimation for Latent Markov Random Fields and Social Networks", Journal of Computational and Graphical Statistic 21 (2012): 940--960
Andreas Flache and Tobias Stark, "Preference or opportunity? Why do we find more friendship segregation in more heterogeneous schools?", arxiv:0901.2825
Agata Fronczak, "Exponential random graph models", arxiv:1210.7828
Shweta Gaonkar, Angelo Mele, "A model of inter-organizational network formation", arxiv:2105.00458
Neha Gondal, "The local and global structure of knowledge production in an emergent research field: An exponential random graph analysis", Social Networks forthcoming (2011)
Vishesh Karwa, Sonja Petrović, Denis Bajić, "DERGMs: Degeneracy-restricted exponential random graph models", arxiv:1612.03054
Dean Lusher, Johan Koskinen, and Garry Robins (eds.), Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications
Sumit Mukherjee, "Consistent estimation in the two star Exponential Random Graph Model", arxiv:1310.4526
Saisuke Okabayashi and Charles J. Geyer, "Long range search for maximum likelihood in exponential families", Electronic Journal of Statistics 6 (2012): 123--147
Philippa E. Pattison, Garry L. Robins, Tom A.B. Snijders, Peng Wang, "Conditional estimation of exponential random graph models from snowball sampling designs", Journal of Mathematical Psychology forthcoming (2013)
Tiago P. Peixoto, "The entropy of stochastic blockmodel ensembles", Physical Review E 85 (2012): 056122, arxiv:1112.6028
Wen Pu, Jaesik Choi, Yunseong Hwang and Eyal Amir, "A Deterministic Partition Function Approximation for Exponential Random Graph Models" [PDF]
Charles Radin, Mei Yin, "Phase transitions in exponential random graphs", arxiv:1108.0649
Gesine Reinert, Wenkai Xu, "SteinGen: Generating Fidelitous and Diverse Graph Samples", arxiv:2403.18578 <.i>Michael Schweinberger and Mark S. Handcock, "Local Dependence in Random Graph Models: Characterization, Properties and Statistical Inference", Journal of the Royal Statistical Society B 77 (2015): 647--676
Sean L. Simpson, Satoru Hayasaka, Paul J. Laurienti, "Selecting an exponential random graph model for complex brain networks", arxiv:1007.3230
Jeffrey A. Smith, "Macrostructure from Microstructure: Generating Whole Systems from Ego Networks", Sociological Methodology 42 (2012): 155--205
Jonathan R. Stewart, "Rates of convergence and normal approximations for estimators of local dependence random graph models", arxiv:2404.11464 [I like the phrase "statistical disclaimer", but I'm pretty sure it's just good old fashioned consistency/probably-approximately-correct.]
Thomas Suesse, "Marginalized Exponential Random Graph Models", Journal of Computational and Graphical Statistics 21 (2012): 883--900
George G. Vega Yon, Andrew Slaughter and Kayla de la Haye, "Exponential random graph models for little networks", Social Networks 64 (2021): 225--238 [Preliminary comments, pending a detailed reading]
Mei Yin, "Critical phenomena in exponential random graphs", arxiv:1208.2992