The origins of exponential random graph models

The article An Exponential Family of Probability Distributions for Directed Graphs, published by Holland and Leinhardt (1981), set the foundation for the now known exponential random graph models (ERGM) or p* models, which model jointly the whole adjacency matrix (or graph) $latex X$. In this article they proposed an exponential family of probability distributions to model $latex P(X=x)$, where $latex x$ is a possible realisation of the random matrix $latex X$.

The article is mainly focused on directed graphs (although the theory can be extended to undirected graphs). Two main effects or patterns are considered in the article: Reciprocity, which relates to appearance of symmetric interactions ($latex X_{ij}=1 \iff X_{ji}=1$) (see nodes 3-5 of the Figure below).


and, the Differential attractiveness of each node in the graph, which relates to the amount of interactions each node “receives” (in-degree) and the amount of interactions that each node “produces” (out-degree) (the Figure below illustrates the differential attractiveness of two groups of nodes).

Stochastic_block_model_directed2 The model of Holland and Leinhardt (1981), called p1 model, that considers jointly the reciprocity of the graph and the differential attractiveness of each node is:

$latex p_1(x)=P(X=x) \propto e^{\rho m + \theta x_{**} + \sum_i \alpha_i x_{i*} + \sum_j \beta_j x_{*j}}, $

where $latex \rho,\theta,\alpha_i,\beta_j $ are parameters, and $latex \alpha_*=\beta_*=0 $ (identifying constrains).  $latex \rho $ can be interpreted as the mean tendency of reciprocation, $latex \theta$ can be interpreted as the density (size) of the network, $latex \alpha_i $ can be interpreted as as the productivity (out-degree) of a node, $latex \beta_j $ can be interpreted as the attractiveness (in-degree) of a node.

The values $latex m, x_{**}, x_{i*}$ and $latex x_{*j}$ are: the number of reciprocated edges in the observed graph, the number of edges, the out-degree of node i and the in-degree of node j; respectively.

Taking $latex D_{ij}=(X_{ij},X_{ji})$, the model assumes that all $latex D_{ij}$ with $latex i<j $ are independent.


To better understand the model, let’s review its derivation:

Consider the pairs $latex D_{ij}=(X_{i,j},X_{j,i}),\,i<j $ and describe the joint distribution of $latex \{D_{ij}\}_{ij}$, assuming all $latex D_{ij}$ are statistically independent. This can be done by parameterizing the probabilities

$latex P(D_{ij}=(1,1))=m_{ij} \text{ if } i<j,$

$latex P(D_{ij}=(1,0))=a_{ij} \text{ if } i\neq j,$

$latex P(D_{ij}=(0,0))=n_{ij} \text{ if } i<j,$

where $latex m_{ij}+a_{ij}+a_{ji}+n_{ij}=1,\, \forall \, i<j $.

Hence leading

$latex P(X=x)=\prod_{i<j} m_{ij}^{x_{ij}x_{ji}} \prod_{i\neq j}a_{ij}^{x_{ij}(1-x_{ji})} \prod_{i<j}n_{ij}^{(1-x_{ij})(1-x_{ji})}

=e^{\sum_{i<j} {x_{ij}x_{ji}} \rho_{ij} + \sum_{i\neq j}{x_{ij}} \theta_{ij}} \prod_{i<j}n_{ij}, $

where $latex \rho_{ij}=log(m_{ij}n_{ij} / a_{ij}a_{ji})$ for $latex i<j$, and $latex \theta_{ij}=log(a_{ij}/n_{ij})$ for $latex i\neq j$.

It can be seen that the parameters $latex \rho_{ij}$ and $latex \theta_{ij}$ can be interpreted as the reciprocity and differential attractiveness, respectively. With a bit of algebra we get:

$latex exp(\rho_{ij})=[ P(X_{ij}=1|X_{ji}=1)/P(X_{ij}=1|X_{ji}=0) ]/[ P(X_{ij}=1|X_{ji}=0) / P(X_{ij}=0|X_{ji}=0) ], $
$latex exp(\theta_{ij})=P(X_{ij}=1|X_{ji}=0)/P(X_{ij}=0|X_{ji}=0). $

Now, if we consider the following restrictions:

$latex \rho_{ij}=\rho,\, \forall i<j$, and $latex \theta_{ij}=\theta+\alpha_i + \beta_j,\, \forall i\neq j $ where $latex \alpha_*=\beta_*=0 $.

With some algebra we get the proposed form of the model

$latex p_1(x)=P(X=x) \propto e^{\rho m + \theta x_{**} + \sum_i \alpha_i x_{i*} + \sum_j \beta_j x_{*j}}.$



Leave a Reply