Overview of Social Network Models

Models for Social Networks

Today, we will take a brief (very brief) look at the following models:

• Spatial Auto-correlation Models

• Exponential Random Graph Models

• Stochastic Actor Oriented Models

• Network Matching

First, a brief introduction

Exponential Random Graph Models (ERGMs)

The distribution of \(\mathbf{Y}\) can be parameterized in the form

\[ \Pr\left(\mathbf{Y}=\mathbf{y}|\theta, \mathcal{Y}\right) = \frac{\exp{\theta^{\mbox{T}}\mathbf{g}(\mathbf{y})}}{\kappa\left(\theta, \mathcal{Y}\right)},\quad\mathbf{y}\in\mathcal{Y} \tag{1} \]

Where \(\theta\in\Omega\subset\mathbb{R}^q\) is the vector of model coefficients and \(\mathbf{g}(\mathbf{y})\) is a q-vector of statistics based on the adjacency matrix \(\mathbf{y}\).

• Model (1) may be expanded by replacing \(\mathbf{g}(\mathbf{y})\) with \(\mathbf{g}(\mathbf{y}, \mathbf{X})\) to allow for additional covariate information \(\mathbf{X}\) about the network. The denominator,

  \[ \kappa\left(\theta,\mathcal{Y}\right) = \sum_{\mathbf{z}\in\mathcal{Y}}\exp{\theta^{\mbox{T}}\mathbf{g}(\mathbf{z})} \] 0

• Is the normalizing factor that ensures that equation (1) is a legitimate probability distribution.

• Even after fixing \(\mathcal{Y}\) to be all the networks that have size \(n\), the size of \(\mathcal{Y}\) makes this type of models hard to estimate as there are \(N = 2^{n(n-1)}\) possible networks! (Hunter et al. 2008)

How does ERGMs look like (in R at least)

network ~ edges + nodematch("hispanic") + nodematch("female") +
  mutual +  esp(0:3) +  idegree(0:10)

Here we are controlling for:

• edges: Edge count,
• nodematch(hispanic): number of homophilic edges on race,
• nodematch(female): number of homophilic edges on gender,
• mutual: number of reciprocal edges,
• esp(0:3): number of shared parterns (0 to 3), and
• indegree(0:10): indegree distribution (fixed effects for values 0 to 10)

(See Hunter et al. 2008).

Separable Exponential Random Graph Models (a.k.a. TERGMs)

• A discrete time model.

• Estimates a set of parameters \(\theta = \{\theta^-, \theta^+\}\) that capture the transition dynamics from \(\mathbf{Y}^{t-1}\) to \(\mathbf{Y}^{t}\).

• Assuming that \((\mathbf{Y}^+\perp\mathbf{Y}^-) | \mathbf{Y}^{t-1}\) (the model dynamic model is separable), we estimate two models: \[ \begin{align} \Pr\left(\mathbf{Y}^+ = \mathbf{y}^+|\mathbf{Y}^{t-1} = \mathbf{y}^{t-1};\theta^+\right),\quad \mathbf{y}^+\in\mathcal{Y}^+(\mathbf{y}^{t-1})\\ \Pr\left(\mathbf{Y}^- = \mathbf{y}^-|\mathbf{Y}^{t-1} = \mathbf{y}^{t-1};\theta^-\right),\quad \mathbf{y}^-\in\mathcal{Y}^-(\mathbf{y}^{t-1}) \end{align} \]

• So we end up estimating two ERGMs.

Latent Network Models

• Social networks are a function of a latent space (literally, xyz for example) \(\mathbf{Z}\).

• Individuals who are closer to each other within \(\mathbf{Z}\) have a higher chance of been connected.

• Besides of estimating the typical set of parameters \(\theta\), a key part of this model is find \(\mathbf{Z}\).

• Similar to TERGMs, under the conditional independence assumption we can estimate:

\[ \Pr\left(\mathbf{Y} =\mathbf{y}|\mathbf{X} = \mathbf{x}, \mathbf{Z}, \theta\right) = \prod_{i\neq j}\Pr\left(y_{ij}|z_i, z_j, x_{ij},\theta\right) \]

See Hoff, Raftery, and Handcock (2002)

Estimation of ERGMs

In statnet, the default estimation method is based on a method proposed by Geyer and Thompson (1992), Markov-Chain MLE, which uses Markov-Chain Monte Carlo for simulating networks and a modified version of the Newton-Raphson algorithm to do the parameter estimation part.

Estimation of ERGMs (cont’ d)

In general terms, the MC-MLE algorithm can be described as follows:

1. Initialize the algorithm with an initial guess of \(\theta\), call it \(\theta^{(t)}\)

2. While (no convergence) do:

   1. Using \(\theta^{(t)}\), simulate \(M\) networks by means of small changes in the \(\mathbf{Y}_{obs}\) (the observed network). This part is done by using an importance-sampling method which weights each proposed network by it’s likelihood conditional on \(\theta^{(t)}\)

   2. With the networks simulated, we can do the Newton step to update the parameter \(\theta^{(t)}\) (this is the iteration part in the ergm package): \(\theta^{(t)}\to\theta^{(t+1)}\)

   3. If convergence has been reach (which usually means that \(\theta^{(t)}\) and \(\theta^{(t + 1)}\) are not very different), then stop, otherwise, go to step a.

For more details see Lusher, Koskinen, and Robins (2012);Admiraal and Handcock (2006);T. A. Snijders (2002);Wang et al. (2009) provides details on the algorithm used by PNet (which is the same as the one used in RSiena). Lusher, Koskinen, and Robins (2012) provides a short discussion on differences between ergm and PNet.

The main problems with ERGMs are:

1. Computational Time: As the complexity of the model increases, it gets harder to achieve convergence, thus, more time is needed.

2. Model degeneracy: Even if convergence is achieved, model fitness can be very bad

Stochastic Actor Oriented Models (SOAMs)

• Also known as Siena: Simulation Investigation for Empirical Network Analysis.

• Models both, structure and behavior as a time-continuous Markov process where changes happen one at a time (as a poisson process).

• In other words, individuals choose between states \(x\) and \(x'\) in which either a tie changes, or their behavior changes.

• Ultimately, we maximize the following function:

\[ \frac{\exp{f_i^Z(\beta^z,x, z)}}{\sum_{Z'\in\mathcal{C}}\exp{f_i^{Z}(\beta, x, z')}} \]

• Like ERGMs, the denominator is what makes estimating this models hard.

See Tom A B Snijders, Bunt, and Steglich (2010);Lazega and Snijders (2015);Ripley et al. (2011).

Network Matching: Aral et al. (2009)

• Built on top of the Rubin Causal Model (RCM). Uses matching (non-parametric method) to estimate the effect that changes on exposure has over behavior

• As a difference from RCM, we don’t have one but multiple treatments

• In the dynamic case, for each time \(t\), we can build multiple levels of treatments, in particular, given that individual \(i\) had an exposure \(E_{t-1}=j-1\) at \(t-1\), we write:

  \[ T_{itj} = \left\{\begin{array}{ll} 1 &\mbox{if }E_t = j \\ 0 &\mbox{otherwise.} \end{array}\right. \]

• Based on the previous equation, we can use some matching algorithm to build counter factuals and estimate a simil to Average Treatment Effect on the Treated (ATT).

• For more on matching methods see Imbens and Wooldridge (2009);Sekhon (2008);King and Nielsen (2016) (special attention to the last one).

Other Models

• GERGM: Generalized Exponential Random Graph Models (using weighted graphs, see Desmarais (2012)).

• SERGMs: Statistical Exponential Random Graph Models, suitable for large graphs, uses sufficient statistics. (see Chandrasekhar and Jackson 2012)

• DyNAM: dynamic network actor models (see Stadtfeld, Hollway, and Block 2017).

• REM: Relational Event Models (see Butts 2008), which are very similar to DyNAMs.

• ALAAM: Autologistic actor attribute models (see Daraganova and Robins 2013; Kashima et al. 2013)

Some other models can be found in Tom A. B. Snijders (2011).

Summary