ergmgp-package {ergmgp}

Tools for Modeling ERGM Generating Processes

Description

Tools for simulation and analysis of continuous time graph processes with equilibria that can be described in exponential family random graph (ERGM) form.

Details

A random graph G on support \mathcal{G} is said to be expressed in exponential family random graph (ERGM) form when its probability mass function (pmf) is written as

\Pr(G=g|\theta,X) = \frac{\exp\left(\theta^T w(g,X)\right) h(g)}{\sum_{g' \in \mathcal{G}} \exp\left(\theta^T w(g',X)\right) h(g')}

where \theta is a parameter vector, w is a vector of sufficient statistics, X is a covariate set, and h is a reference measure. This form is quite general; in particular, any pmf on finite support can be written in ERGM form (albeit not always elegantly), making it a natural language for expressing graph distributions.

Now, consider a continuous time process whose state space is \mathcal{G}. A process of this type having an equilibrium distribution that can be written in (known) ERGM form is said to be an ERGM generating process or EGP. Although there are many types of EGPs, perhaps the most natural are continuous time Markov chains (CTMCs) whose transitions involve the addition or removal of individual edges from the current graph state. The transition rates of such CTMCs have the topology of the Hamming adjacency on \mathcal{G}; this is only sensible when considering graphs on a fixed vertex set, which is the typical use case. We can think of this class of EGPs as continuous time analogs of the Markov chains used in ERGM simulation (see ergm), with equilibrium obtained in the limit of time rather than simulation steps. EGPs are potentially useful as dynamic interpretations of empirically obtained ERGMs, or as a priori models in their own right. Since many Markovian EGPs are identified by their equilibrium ERGM together with a pacing constant, they are also natural choices when dynamics must be inferred from limited data (e.g., a cross-sectional network observation together with pacing or duration information).

The ergmgp package supports a number of different EGPs, all of which are currently Markovian with support on graphs or digraphs of fixed order. The following EGPs are currently supported; all definitions and notation follow Butts (2023). Define q(g) = \theta^T w(g,X) + \ln h(g) to be the graph potential; in some cases, separate potentials (q_f and q_d) may be employed for the formation and dissolution of edges. For brevity, we define the normalizing factor of the equilibrium ERGM distribution by Z = \sum_{g' \in \mathcal{G}} q(g'), let w_e be the edge count statistic, and let \mathcal{H}(g) be the Hamming neighborhood of g (i.e., the set of graphs reachable by single edge changes, or “toggles”). All transition rates from graph a to b (denoted a \to b) zero for b \not\in \mathcal{H}(a). Processes not otherwise noted were introduced in Butts (2023).

Longitudinal ERGM (LERGM)

Description:

Introduced by Koskinen and Snijders (2007), this process was originally conceived of as a continuum analog to the Gibbs sampler, with transition rates that are increasing with differences in graph potential. Grazioli et al. (2019) subsequently showed that it can also be derived from a physical model with locally Arrhenius-like kinetics. This process has a maximum change rate (but no minimum), and may thus be plausible in settings for which changes can only be made when (exogenously determined) opportunities arise.

Event Rate (a \to b):

[1+\exp[q(a)-q(b)]]^{-1}

Equilibrium:

\exp[q(a)]/Z

Competing Rate Stochastic Actor-Oriented Model (CRSAOM)

Description:

Introduced as an EGP by Snijders (2001), this model was originally proposed as a behavioral process, where vertices represent actors controlling their outgoing edges, the rate at which actors make tie changes is a function of the attractiveness of the networks reachable by making such changes, and (given opportunity to act) edge changes are chosen by a multinomial logit with utility function q. Dynamics in this model are distinctive in being driven solely by the attractiveness of the target state, which can sometimes lead to rapid state switching when multiple high-potential states are Hamming-adjacent.

Event Rate (a \to b):

\exp[q(b)]

Equilibrium:

\exp[q(a)]/Z

Change Inhibition (CI)

Description:

In the same sense that the LERGM is analogous to a continuum Gibbs sampler, this process is loosely analogous to continuum Metropolis algorithm. Downhill transitions with respect to the graph potential occur with a rate that is decreasing with the potential difference; uphill transitions, however, occur at a fixed rate (irrespective of the potential difference). The process thus works by selectively inhibiting downhill moves, rather than by preferentially moving to graphs of highest local potential.

Event Rate (a \to b):

\min(1,\exp[q(b)-q(a)])

Equilibrium:

\exp[q(a)]/Z

Differential Statibility (DS)

Description:

Analogous to a “win-stay, lose-shift” process, transition targets in this EGP are chosen uniformly at random, with structure arising entirely from transition times. The time to exit a state g is proportional to \exp[q(g)], making high-potential states exponentially more persistent than low-potential states. Note that this process is in a sense the inverse of the CRSAOM, being dependent only on the potential of the source state (while the CRSAOM depends only on the potential of the target state). Since the transitions themselves from a random walk, it should be noted that this process can generate very large numbers of transition events involving low-potential states that, while taking little phenomenological time, nevertheless are expensive to compute.

Event Rate (a \to b):

|\mathcal{H}(a)|^{-1} \exp[-q(a)]

Equilibrium:

\exp[q(a)]/Z

Constant Dissolution Continuum STERGM (CDCSTERGM)

Description:

This process is a continuum version of the discrete time constant dissolution separable temporal ERGM (STERGM) introduced by Carnegie et al. (2015); here, edges are lost randomly at a fixed rate, with a formation potential q_f that governs edge addition. This is a special case of the continuum STERGMs (below), and is particularly easy to identify from limited information.

Event Rate (a \to b):

If b is formed by adding an edge to a, then \exp[q_f(b)-q_f(a)]; otherwise \exp[\theta_d]

Equilibrium:

\exp[q_f(a) - \theta_d w_e(a)]/Z

Constant Formation Continuum STERGM (CFCSTERGM)

Description:

This process is analogous to the CDCSTERGM, except that in this case edge formation occurs randomly at a fixed rate, with a dissolution potential q_d governing edge loss. It is a simple model for settings in which edges arise from essentially idiosyncratic events, with the resulting network structure subsequently stabilizing or destabilizing particular edges.

Event Rate (a \to b):

If b is formed by adding an edge to a, then \exp[\theta_f]; otherwise \exp[q_d(b)-q_d(a)]

Equilibrium:

\exp[q_d(a) + \theta_f w_e(a)]/Z

Continuum STERGM (CSTERGM)

Description:

This process represents a continuum limit of the discrete time separable temporal ERGMs (STERGMs) introduced by Krivitsky and Handcock (2014). Edge formation is here governed by one potential (q_f), while dissolution is governed by another (q_d), allowing these processes to be governed by different effects. The resulting equilibrium pmf is based on the sum of both potentials.

Event Rate (a \to b):

If b is formed by adding an edge to a, then \exp[q_f(b)-q_f(a)]; otherwise \exp[q_d(b)-q_d(a)]

Equilibrium:

\exp[q_d(a) + q_f(a)]/Z

Continuum TERGM (CTERGM)

Description:

This process is a continuum limit of the discrete time temporal ERGMs (TERGMs) introduced in Robins and Pattison (2001). The transition rates for this class are particularly natural, with the log rates being equal to the potential differences between states. Note that the potential of the equilibrium ERGM is scaled by a factor of 2 from the transition potential (as can be obtained from the CSTERGM by letting q_f=q_d); intuitively, this arises because states of higher potential are both more stable (lower exit rates) and more attractive (higher entrance rates) than states of lower potential.

Event Rate (a \to b):

\exp[q(b)-q(a)]

Equilibrium:

\exp[2q(a)]/Z

Further details on each process can be found in Butts (2023). All of the above transition rates are defined up to an arbitrary pacing constant (which is generally specified separately, and taken to be 1 in package tools if not otherwise indicated). Note that the LERGM and Change Inhibition processes have unit-maximum transition rates, and thus the pacing constant sets the maximum rate of change.

Information on functions for simulation or analysis of EGPs is provided in their respective manual pages. Information on ERGMs and their specification can be found within the ergm page in the ergm library.

Author(s)

Carter T. Butts [e-mail]

References

Butts, Carter T. (2023). “Continuous Time Graph Processes with Known ERGM Equilibria: Contextual Review, Extensions, and Synthesis.” Journal of Mathematical Sociology. doi:10.1080/0022250X.2023.2180001

Carnegie, Nicole B.; Krivitsky, Pavel N.; Hunter, David R.; and Goodreau, Steven M. (2015). “An Approximation Method for Improving Dynamic Network Model Fitting.” Journal of Computational and Graphical Statistics, 24(2):502-519.

Grazioli, Gianmarc; Yu, Yue; Unhelkar, Megha H.; Martin, Rachel W.; and Butts, Carter T. (2019). “Network-based Classification and Modeling of Amyloid Fibrils.” Journal of Physical Chemistry, B, 123(26):5452-5462.

Koskinen, Johan H. and Snijders, Tom A. (2007). “Bayesian Inference for Dynamic Social Network Data.” Journal of Statistical Planning and Inference, 137(12):393–3938. 5th St. Petersburg Workshop on Simulation, Part II.

Krivitsky, Pavel N. and Handcock, Mark S. (2014). “A Separable Model for Dynamic Networks.” Journal of the Royal Statistical Society, Series B, 76(1):29-46.

Robins, Garry L. and Pattison, Philippa E. (2001). “Random Graph Models for Temporal Processes in Social Networks.” Journal of Mathematical Sociology, 25:5-41.

Snijders, Tom A. B. (2001). “The Statistical Evaluation of Social Network Dynamics.” Sociological Methodology, 31:361-395.

See Also

simEGP, EGPHazard, EGPRateEst, ergm, durations