Exponential family random graph models

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.

Formally a random graph ${\displaystyle Y\in \mathcal{Y}}$ consists of a set of ${\displaystyle n}$ nodes and a collection of tie variables ${\displaystyle \{Y_{ij}:i=1,\dots ,n;j=1,\dots ,n\}}$, indexed by pairs of nodes ${\displaystyle ij}$, where ${\displaystyle Y_{ij}=1}$ if the nodes ${\displaystyle (i,j)}$ are connected by an edge and ${\displaystyle Y_{ij}=0}$ otherwise. A pair of nodes ${\displaystyle ij}$ is called a dyad and a dyad is an edge if ${\displaystyle Y_{ij}=1}$.

The basic assumption of these models is that the structure in an observed graph ${\displaystyle y}$ can be explained by a given vector of sufficient statistics ${\displaystyle s(y)}$ 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:

${\displaystyle P(Y=y|\theta )=\frac{\exp ({\theta }^{T}s(y))}{c(\theta )},\mathrm{\forall }y\in \mathcal{Y}}$

where ${\displaystyle \theta }$ is a vector of model parameters associated with ${\displaystyle s(y)}$ and ${\displaystyle c(\theta )=\sum _{y^{\prime }\in \mathcal{Y}}\exp ({\theta }^{T}s(y^{\prime }))}$ is a normalising constant.

These models represent a probability distribution on each possible network on ${\displaystyle n}$ nodes. However, the size of the set of possible networks for an undirected network (simple graph) of size ${\displaystyle n}$ is ${\displaystyle 2^{n(n-1)/2}}$. 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.

Example

Let ${\displaystyle V=\{1,2,3\}}$ be a set of three nodes and let ${\displaystyle \mathcal{Y}}$ be the set of all undirected, loopless graphs on ${\displaystyle V}$. Loopless implies that for all ${\displaystyle i=1,2,3}$ it is ${\displaystyle Y_{ii}=0}$ and undirected implies that for all ${\displaystyle i,j=1,2,3}$ it is ${\displaystyle Y_{ij}=Y_{ji}}$, so that there are three binary tie variables (${\displaystyle Y_{12},Y_{13},Y_{23}}$) and ${\displaystyle 2^3=8}$ different graphs in this example.

Define a two-dimensional vector of statistics by ${\displaystyle s(y)=[s_1(y),s_2(y){]}^T}$, where ${\displaystyle s_1(y)=edges(y)}$ is defined to be the number of edges in the graph ${\displaystyle y}$ and ${\displaystyle s_2(y)=triangles(y)}$ is defined to be the number of closed triangles in ${\displaystyle y}$. Finally, let the parameter vector be defined by ${\displaystyle \theta =({\theta }_1,{\theta }_2{)}^T=(-\ln 2,\ln 3{)}^T}$, so that the probability of every graph ${\displaystyle y\in \mathcal{Y}}$ in this example is given by:

${\displaystyle P(Y=y|\theta )=\frac{\exp (-\ln 2\cdot edges(y)+\ln 3\cdot 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 ${\displaystyle y}$ of each isomorphism class, we first compute the term ${\displaystyle x(y)=\exp (-\ln 2\cdot edges(y)+\ln 3\cdot triangles(y))}$, which is proportional to the probability of ${\displaystyle y}$ (up to the normalizing constant ${\displaystyle c(\theta )}$).

If ${\displaystyle y}$ is the graph with zero edges, then it is ${\displaystyle edges(y)=0}$ and ${\displaystyle triangles(y)=0}$, so that

${\displaystyle x(y)=\exp (-\ln 2\cdot 0+\ln 3\cdot 0)=\exp (0)=1.}$

If ${\displaystyle y}$ is a graph with exactly one edge, then it is ${\displaystyle edges(y)=1}$ and ${\displaystyle triangles(y)=0}$, so that

${\displaystyle x(y)=\exp (-\ln 2\cdot 1+\ln 3\cdot 0)=\frac{\exp (0)}{\exp (\ln 2)}=\frac{1}{2}.}$

If ${\displaystyle y}$ is a graph with exactly two edges, then it is ${\displaystyle edges(y)=2}$ and ${\displaystyle triangles(y)=0}$, so that

${\displaystyle x(y)=\exp (-\ln 2\cdot 2+\ln 3\cdot 0)=\frac{\exp (0)}{\exp (\ln 2{)}^2}=\frac{1}{4}.}$

If ${\displaystyle y}$ is the graph with exactly three edges, then it is ${\displaystyle edges(y)=3}$ and ${\displaystyle triangles(y)=1}$, so that

${\displaystyle x(y)=\exp (-\ln 2\cdot 3+\ln 3\cdot 1)=\frac{\exp (\ln 3)}{\exp (\ln 2{)}^3}=\frac{3}{8}.}$

The normalizing constant is computed by summing ${\displaystyle x(y)}$ over all eight different graphs ${\displaystyle y\in \mathcal{Y}}$. This yields:

${\displaystyle c(\theta )=1+3\cdot \frac{1}{2}+3\cdot \frac{1}{4}+\frac{3}{8}=\frac{29}{8}.}$

Finally, the probability of every graph ${\displaystyle y\in \mathcal{Y}}$ is given by ${\displaystyle P(Y=y|\theta )=\frac{x(y)}{c(\theta )}}$. Explicitly, we get that the graph with zero edges has probability ${\displaystyle \frac{8}{29}}$, every graph with exactly one edge has probability ${\displaystyle \frac{4}{29}}$, every graph with exactly two edges has probability ${\displaystyle \frac{2}{29}}$, and the graph with exactly three edges has probability ${\displaystyle \frac{3}{29}}$ 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 (${\displaystyle {\theta }_1=-\ln 2}$) 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 (${\displaystyle {\theta }_2=\ln 3}$) 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

Sampling from an ERGM

Exact sampling from a given ERGM is computationally intractable in general since computing the normalizing constant requires summation over all ${\displaystyle y\in \mathcal{Y}}$. 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. Informally, given an ERGM on a set of graphs ${\displaystyle \mathcal{Y}}$ with probability mass function ${\displaystyle P(Y=y|\theta )=\frac{\exp ({\theta }^{T}s(y))}{c(\theta )}}$, one selects an initial graph ${\displaystyle y^{(0)}\in \mathcal{Y}}$ (which might be arbitrarily, or randomly, chosen or might represent an observed network) and implicitly defines transition probabilities (or jump probabilities) ${\displaystyle \pi (y,y^{\prime })=P(Y^{(t+1)}=y^{\prime }|Y^{(t)}=y)}$, which are the conditional probabilities that the Markov chain is on graph ${\displaystyle y^{\prime }}$ after Step ${\displaystyle t+1}$, given that it is on graph ${\displaystyle y}$ after Step ${\displaystyle t}$. The transition probabilities do not depend on the graphs in earlier steps (${\displaystyle y^{(0)},\dots ,y^{(t-1)}}$), which is a defining property of Markov chains, and they do not depend on ${\displaystyle t}$, that is, the Markov chain is time-homogeneous. The goal is to define the transition probabilities such that for all ${\displaystyle y\in \mathcal{Y}}$ it is

${\displaystyle \underset{t\to \mathrm{\infty }}{lim}P(Y^{(t)}=y)=\frac{\exp ({\theta }^{T}s(y))}{c(\theta )},}$

independent of the initial graph ${\displaystyle y^{(0)}}$. 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 ${\displaystyle y\in \mathcal{Y}}$ 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 ${\displaystyle y^{\prime }}$ in a neighborhood of the current graph ${\displaystyle y}$ and, second, to accept ${\displaystyle y^{\prime }}$ with a probability that depends on the probability ratio of the current graph ${\displaystyle y}$ and the candidate ${\displaystyle y^{\prime }}$. (If the candidate is not accepted, the Markov chain remains on the current graph ${\displaystyle y}$.) If the set of graphs ${\displaystyle \mathcal{Y}}$ 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 ${\displaystyle y_{ij}}$ uniformly at random and to define the candidate by flipping this single variable (i.e., to set ${\displaystyle y_{ij}^{\prime }=1-y_{ij}}$; all other variables take the same value as in ${\displaystyle y}$). A common way to define the acceptance probability is to accept ${\displaystyle y^{\prime }}$ with the conditional probability

${\displaystyle P(Y=y^{\prime }|Y=y^{\prime }\vee Y=y)=\frac{P(Y=y^{\prime })}{P(Y=y^{\prime })+P(Y=y)},}$

where the graph probabilities are defined by the ERGM. Crucially, the normalizing constant ${\displaystyle c(\theta )}$ cancels out in this fraction, so that the acceptance probabilities can be computed efficiently.