Exponential family random graph models explained
Exponential family random graph models (ERGMs) are a set of statistical models used to study the structure and patterns within networks, such as those in social, organizational, or scientific contexts.[1] [2] [3] They analyze how connections (edges) form between individuals or entities (nodes) by modeling the likelihood of network features, like clustering or centrality, across diverse examples including knowledge networks,[4] organizational networks,[5] colleague networks,[6] social media networks, networks of scientific collaboration,[7] and more. Part of the exponential family of distributions, ERGMs help researchers understand and predict network behavior in fields ranging from sociology to data science.
Background
Many metrics exist to describe the structural features of an observed network such as the density, centrality, or assortativity.[8] [9] However, these metrics describe the observed network which is only one instance of a large number of possible alternative networks.[10] This set of alternative networks may have similar or dissimilar structural features. To support statistical inference on the processes influencing the formation of network structure, a statistical model should consider the set of all possible alternative networks weighted on their similarity to an observed network. However, because network data is inherently relational, it violates the assumptions of independence and identical distribution of standard statistical models like linear regression.[11] [2] Alternative statistical models should reflect the uncertainty associated with a given observation, permit inference about the relative frequency about network substructures of theoretical interest, disambiguating the influence of confounding processes, efficiently representing complex structures, and linking local-level processes to global-level properties.[12] Degree-preserving randomization, for example, is a specific way in which an observed network could be considered in terms of multiple alternative networks.
Definition
The Exponential family is a broad family of models for covering many types of data, not just networks. An ERGM is a model from this family which describes networks.
consists of a set of
nodes and a collection of
tie variables
\{Yij:i=1,...,n;j=1,...,n\}
, indexed by pairs of nodes
, where
if the nodes
are connected by an edge and
otherwise. A pair of nodes
is called a dyad and a dyad is an
edge if
.
The basic assumption of these models is that the structure in an observed graph
can be explained by a given vector of
sufficient statistics
which are a function of the observed network and, in some cases, nodal attributes. This way, it is possible to describe any kind of dependence between the undyadic variables:
P(Y=y|\theta)=
| \exp(\thetaTs(y)) |
| c(\theta) |
, \forally\inl{Y}
where
is a vector of model parameters associated with
and
}\exp(\theta^ s(y')) is a normalising constant.
These models represent a probability distribution on each possible network on
nodes. However, the size of the set of possible networks for an undirected network (simple graph) of size
is
. Because the number of possible networks in the set vastly outnumbers the number of parameters which can constrain the model, the ideal probability distribution is the one which maximizes the Gibbs entropy.
[13] Example
Let
be a set of three nodes and let
be the set of all
undirected, loopless graphs on
.
Loopless implies that for all
it is
and
undirected implies that for all
it is
, so that there are three binary tie variables (
) and
different graphs in this example.
Define a two-dimensional vector of statistics by
, where
is defined to be the number of edges in the graph
and
is defined to be the number of closed triangles in
. Finally, let the parameter vector be defined by
\theta=(\theta1,\theta
2,ln3)T
, so that the probability of every graph
in this example is given by:
P(Y=y|\theta)=
| \exp(-ln2 ⋅ edges(y)+ln3 ⋅ triangles(y)) |
| c(\theta) |
We note that in this example, there are just four graph isomorphism classes: the graph with zero edges, three graphs with exactly one edge, three graphs with exactly two edges, and the graph with three edges. Since isomorphic graphs have the same number of edges and the same number of triangles, they also have the same probability in this example ERGM. For a representative
of each isomorphism class, we first compute the term
x(y)=\exp(-ln2 ⋅ edges(y)+ln3 ⋅ triangles(y))
, which is proportional to the probability of
(up to the normalizing constant
).
If
is the
graph with zero edges, then it is
and
, so that
x(y)=\exp(-ln2 ⋅ 0+ln3 ⋅ 0)=\exp(0)=1.
If
is a
graph with exactly one edge, then it is
and
, so that
x(y)=\exp(-ln2 ⋅ 1+ln3 ⋅ 0)=
.
If
is a
graph with exactly two edges, then it is
and
, so that
x(y)=\exp(-ln2 ⋅ 2+ln3 ⋅ 0)=
.
If
is the
graph with exactly three edges, then it is
and
, so that
x(y)=\exp(-ln2 ⋅ 3+ln3 ⋅ 1)=
.
The normalizing constant is computed by summing
over all eight different graphs
. This yields:
Finally, the probability of every graph
is given by
| P(Y=y|\theta)= | x(y) |
| c(\theta) |
. Explicitly, we get that the graph with zero edges has probability
, every graph with exactly one edge has probability
, every graph with exactly two edges has probability
, and the graph with exactly three edges has probability
in this example.
Intuitively, the structure of graph probabilities in this ERGM example are consistent with typical patterns of social or other networks. The negative parameter (
) associated with the number of edges implies that - all other things being equal - networks with fewer edges have a higher probability than networks with more edges. This is consistent with the
sparsity that is often found in empirical networks, namely that the empirical number of edges typically grows at a slower rate than the maximally possible number of edges. The positive parameter (
) associated with the number of closed triangles implies that - all other things being equal - networks with more triangles have a higher probability than networks with fewer triangles. This is consistent with a tendency for
triadic closure that is often found in certain types of social networks. Compare these patterns with the graph probabilities computed above. The addition of every edge divides the probability by two. However, when going from a graph with two edges to the graph with three edges, the number of triangles increases by one - which additionally multiplies the probability by three.
We note that the explicit calculation of all graph probabilities is only possible since there are so few different graphs in this example. Since the number of different graphs scales exponentially in the number of tie variables - which in turn scales quadratic in the number of nodes -, computing the normalizing constant is in general computationally intractable, already for a moderate number of nodes. Also for this reason, the possibility of adopting ERGM for the analysis of large networks is attracting increasing attention[14] [15]
Sampling from an ERGM
Exact sampling from a given ERGM is computationally intractable in general since computing the normalizing constant requires summation over all
. Efficient approximate sampling from an ERGM can be done via
Markov chains and is applied in current methods to approximate expected values and to estimate ERGM parameters.
[16] Informally, given an ERGM on a set of graphs
with probability mass function
P(Y=y|\theta)=
| \exp(\thetaTs(y)) |
| c(\theta) |
, one selects an initial graph
(which might be arbitrarily, or randomly, chosen or might represent an observed network) and implicitly defines transition probabilities (or jump probabilities)
\pi(y,y')=P(Y(t+1)=y'|Y(t)=y)
, which are the conditional probabilities that the Markov chain is on graph
after Step
, given that it is on graph
after Step
. The transition probabilities do not depend on the graphs in earlier steps (
), which is a defining property of
Markov chains, and they do not depend on
, that is, the Markov chain is time-homogeneous. The goal is to define the transition probabilities such that for all
it is
\limt\toinftyP(Y(t)=y)=
| \exp(\thetaTs(y)) |
| c(\theta) |
,
independent of the initial graph
. If this is achieved, one can run the Markov chain for a large number of steps and then returns the current graph as a random sample from the given ERGM. The probability to return a graph
after a finite but large number of update steps is approximately the probability defined by the ERGM.
Current methods for sampling from ERGMs with Markov chains usually define an update step by two sub-steps: first, randomly select a candidate
in a neighborhood of the current graph
and, second, to accept
with a probability that depends on the probability ratio of the current graph
and the candidate
. (If the candidate is not accepted, the Markov chain remains on the current graph
.) If the set of graphs
is unconstrained (i.e., contains any combination of values on the binary tie variables), a simple method for candidate selection is to choose one tie variable
uniformly at random and to define the candidate by flipping this single variable (i.e., to set
; all other variables take the same value as in
). A common way to define the acceptance probability is to accept
with the conditional probability
where the graph probabilities are defined by the ERGM. Crucially, the normalizing constant
cancels out in this fraction, so that the acceptance probabilities can be computed efficiently.
See also
Further reading
- Byshkin . M. . Stivala . A. . Mira . A. . Krause . R. . Robins . G.. Lomi . A. . Auxiliary parameter MCMC for exponential random graph models . Journal of Statistical Physics . 165 . 740β754 . 2016 . 10.1007/s10955-016-1509-4. 3 July 2025 .
- Borisenko . A. . Byshkin . M. . Lomi . A. . A simple algorithm for scalable Monte Carlo inference . 1901.00533 . 2019 . stat.CO .
- Caimo . A. . Friel . N . 2011 . Bayesian inference for exponential random graph models . Social Networks . 33 . 41β55 . 10.1016/j.socnet.2010.09.004 . 1007.5192 .
- ErdΕs . P. . RΓ©nyi . A . 1959 . On random graphs . Publicationes Mathematicae Debrecen. 6 . 3β4 . 290β297. 10.5486/PMD.1959.6.3-4.12 .
- Fienberg . S. E. . Wasserman . S. . 1981 . Discussion of An Exponential Family of Probability Distributions for Directed Graphs by Holland and Leinhardt . Journal of the American Statistical Association . 76 . 373 . 54β57. 10.1080/01621459.1981.10477600.
- Frank . O. . Strauss . D . 1986 . Markov Graphs . Journal of the American Statistical Association . 81 . 395 . 832β842 . 10.2307/2289017. 2289017 .
- Handcock . M. S. . Hunter . D. R. . Butts . C. T. . Goodreau . S. M. . Morris . M. . 2008 . statnet: Software Tools for the Representation, Visualization, Analysis and Simulation of Network Data . Journal of Statistical Software . 24 . 1 . 1β11 . 10.18637/jss.v024.i01 . 18618019 . 2447931 . free .
- Book: Harris, Jenine K . An introduction to exponential random graph modeling . 2014 . 978-1-4522-2080-2 . English . 870698788.
- Hunter . D. R. . Goodreau . S. M. . Handcock . M. S. . 2008 . Goodness of Fit of Social Network Models . Journal of the American Statistical Association . 103 . 481 . 248β258 . 10.1198/016214507000000446. 2008JASA..103..248H . 10.1.1.206.396 .
- Hunter . D. R . Handcock . M. S. . 2006 . Inference in curved exponential family models for networks . Journal of Computational and Graphical Statistics . 15 . 3 . 565β583 . 10.1198/106186006X133069. 10.1.1.205.9670 .
- Hunter . D. R. . Handcock . M. S. . Butts . C. T. . Goodreau . S. M. . Morris . M. . 2008 . ergm: A Package to Fit, Simulate and Diagnose Exponential-Family Models for Networks . Journal of Statistical Software . 24 . 3 . 1β29 . 10.18637/jss.v024.i03 . free . 19756229 . 2743438 .
- Jin . I.H. . Liang . F. . 2012 . Fitting social networks models using varying truncation stochastic approximation MCMC algorithm . Journal of Computational and Graphical Statistics . 10.1080/10618600.2012.680851 . 22 . 4 . 927β952.
- Koskinen . J. H. . Robins . G. L. . Pattison . P. E. . 2010 . Analysing exponential random graph (p-star) models with missing data using Bayesian data augmentation . Statistical Methodology . 7 . 3 . 366β384 . 10.1016/j.stamet.2009.09.007.
- Morris . M. . Handcock . M. S. . Hunter . D. R. . 2008 . Specification of Exponential-Family Random Graph Models: Terms and Computational Aspects . Journal of Statistical Software . 24 . 4 . 1548β7660 . 10.18637/jss.v024.i04 . 18650964 . 2481518 . free .
- Rinaldo . A. . Fienberg . S. E. . Zhou . Y. . 2009 . On the geometry of descrete exponential random families with application to exponential random graph models . Electronic Journal of Statistics . 3 . 446β484 . 10.1214/08-EJS350. 0901.0026 .
- Robins . G. . Snijders . T. . Wang . P. . Handcock . M. . Pattison . P . 2007 . Recent developments in exponential random graph (p*) models for social networks . Social Networks . 29 . 2 . 192β215 . 10.1016/j.socnet.2006.08.003. 11370/abee7276-394e-4051-a180-7b2ff57d42f5 . free .
- Schweinberger. Michael. Instability, sensitivity, and degeneracy of discrete exponential families. Journal of the American Statistical Association. 2011. 106. 496. 1361β1370. 10.1198/jasa.2011.tm10747. 22844170. 3405854.
- Schweinberger. Michael. Handcock. Mark. Local dependence in random graph models: characterization, properties and statistical inference. Journal of the Royal Statistical Society, Series B. 2015. 77. 3. 647β676. 10.1111/rssb.12081. 26560142. 4637985.
- Schweinberger . Michael . Stewart . Jonathan . Concentration and consistency results for canonical and curved exponential-family models of random graphs. The Annals of Statistics . 2020. 48. 1. 374β396. 10.1214/19-AOS1810. 1702.01812.
- Snijders . T. A. B. . 2002 . Markov chain Monte Carlo estimation of exponential random graph models . Journal of Social Structure . 3 .
- Snijders . T. A. B. . Pattison . P. E. . Robins . G. L. . Handcock . M. S. . 2006 . New specifications for exponential random graph models . Sociological Methodology . 36 . 99β153 . 10.1111/j.1467-9531.2006.00176.x. 10.1.1.62.7975 .
- Strauss . D . Ikeda . M . 1990 . Pseudolikelihood estimation for social networks . Journal of the American Statistical Association . 5 . 409 . 204β212 . 10.2307/2289546. 2289546 .
- van Duijn . M. A. . Snijders . T. A. B. . Zijlstra . B. H. . 2004. p2: a random effects model with covariates for directed graphs . Statistica Neerlandica . 58 . 2 . 234β254 . 10.1046/j.0039-0402.2003.00258.x.
- van Duijn . M. A. J. . Gile . K. J. . Krista Gile . Handcock . M. S. . 2009 . A framework for the comparison of maximum pseudo-likelihood and maximum likelihood estimation of exponential family random graph models . Social Networks . 31 . 1 . 52β62 . 10.1016/j.socnet.2008.10.003. 23170041 . 3500576 .
- Zappa . P. . Lomi . A. . The analysis of multilevel networks in organizations: Models and empirical tests . Organizational Research Methods . 18 . 3 . 542β569 . 2015 . 10.1177/1094428115579225 .
Notes and References
- Book: Lusher . Dean . Exponential Random Graph Models for Social Networks: Theory, Methods, and Applications (Structural Analysis in the Social Sciences) . Koskinen . Johan . Robins . Garry . 2012 . 978-0-521-14138-3 . English . 10.1017/CBO9780511894701 . 1120539699.
- Book: Harris, Jenine K . An introduction to exponential random graph modeling . 2014 . 978-1-4522-2080-2 . English . 870698788.
- Amati . Viviana . Lomi . Alessandro . Mira . Antonietta . 2018-03-07 . Social Network Modeling . Annual Review of Statistics and Its Application . en . 5 . 1 . 343β369 . 10.1146/annurev-statistics-031017-100746 . 2018AnRSA...5..343A . 2326-8298.
- Brennecke . Julia . Rank . Olaf . 2017-05-01 . The firm's knowledge network and the transfer of advice among corporate inventorsβA multilevel network study . Research Policy . 46 . 4 . 768β783 . 10.1016/j.respol.2017.02.002 . 0048-7333.
- Harris . Jenine K . 2013 . Communication Ties Across the National Network of Local Health Departments . American Journal of Preventive Medicine . English . 44 . 3 . 247β253 . 10.1016/j.amepre.2012.10.028 . 0749-3797 . 4937103196 . 23415121.
- Brennecke . Julia . 2019 . Dissonant Ties in Intraorganizational Networks: Why Individuals Seek Problem-Solving Assistance from Difficult Colleagues . AMJ Academy of Management Journal . English . 0001-4273 . 8163488129.
- Harris . Jenine K . Luke . Douglas A . Shelton . Sarah C . Zuckerman . Rachael B . 2009 . Forty Years of Secondhand Smoke Research. The Gap Between Discovery and Delivery . American Journal of Preventive Medicine . 36 . 6 . 538β548 . 10.1016/j.amepre.2009.01.039 . 0749-3797 . 6980180781 . 19372026.
- Book: Wasserman . Stanley . Stanley Wasserman . Faust . Katherine . Social Network Analysis: Methods and Applications . 1994 . Cambridge University Press . 978-0-521-38707-1.
- Newman . M.E.J. . The Structure and Function of Complex Networks . SIAM Review . 45 . 2 . 167β256 . 10.1137/S003614450342480. cond-mat/0303516 . 2003SIAMR..45..167N . 2003 .
- Cimini . Giulio . Squartini . Tiziano . Saracco . Fabio . Garlaschelli . Diego . Gabrielli . Andrea . Caldarelli. Guido. Guido Caldarelli . The Statistical Physics of Real-World Networks . Nature Reviews Physics. 1. 10.1038/s42254-018-0002-6 . 2018 . 58β71 . 1810.05095 .
- Contractor . Noshir . Wasserman . Stanley . Faust . Katherine . Testing Multitheoretical, Multilevel Hypotheses About Organizational Networks: An Analytic Framework and Empirical Example . Academy of Management Review . 31 . 3 . 681β703 . 10.5465/AMR.2006.21318925. 2006 . 10837327 . https://web.archive.org/web/20200225120025/https://pdfs.semanticscholar.org/aff3/68453aa6258c34d5aaeba0fd4a49a864b889.pdf . 2020-02-25 .
- Robins . G. . Pattison . P. . Kalish . Y. . Lusher . D.. 2007 . An introduction to exponential random graph models for social networks . Social Networks. 29 . 2 . 173β191 . 10.1016/j.socnet.2006.08.002. 1959.3/216571 . free .
- Book: Newman, M.E.J.. Networks. Other Network Models. 565β585 . 978-0-19-920665-0. 2010-03-25.
- Byshkin . Maksym . Stivala . Alex . Mira . Antonietta . Robins . Garry . Lomi . Alessandro . 2018-07-31 . Fast Maximum Likelihood Estimation via Equilibrium Expectation for Large Network Data . Scientific Reports . en . 8 . 1 . 11509 . 10.1038/s41598-018-29725-8 . 30065311 . 6068132 . 1802.10311 . 2018NatSR...811509B . 2045-2322.
- Stivala . Alex . Robins . Garry . Lomi . Alessandro . 2020-01-24 . Exponential random graph model parameter estimation for very large directed networks . PLOS ONE . en . 15 . 1 . e0227804 . 10.1371/journal.pone.0227804 . free . 1932-6203 . 6980401 . 31978150. 1904.08063 . 2020PLoSO..1527804S .
- Hunter . D. R . Handcock . M. S. . 2006 . Inference in curved exponential family models for networks . Journal of Computational and Graphical Statistics . 15 . 3 . 565β583 . 10.1198/106186006X133069. 10.1.1.205.9670 .