070. ERGM for Dynamic Networks

ERGM for Dynamic Networks

However, a need for statistical models representing the evolving phenomena ⇒ ”Dynamic Models” with a temporal structure

• ERGM → TERGM → STERGM

One-step transition probability $(t-1)\to (t)$ (Markov Assumption)

$$P_{\eta ,g}(Y^t=y^t|Y^{t-1};\theta )=\frac{\exp \{\eta (\theta )\cdot g(y^t,y^{t-1})\}}{c_{\eta ,h}(\theta ,y^{t-1})}$$

Temporal ERGM (TERGM, T ERGM)

시간 t에서의 네트워크는, t-1 시점의 (어쩌면 t-2도 가능하고) 네트워크로 조건을 건 ERGM 으로부터의 단일 생산으로 생각될 수 있음. 소셜 네트워크의 변화를 간단히 하기 위해 Markov assumption 적용.

이는 곧, $A^t$가 t 시점에서의 단일-관계 소셜 네트워크의 weight 매트릭스를 표현하고, 우리에게 $A^{t-1}$ 의 값이 주어져 있다면, $A^t$ 는 $A^1,\cdots ,A^{t-2}$ 으로부터는 독립임을 의미한다는 뜻. 수식으로 표현하면 아래와 같다.

$$P(A^2,A^3,\cdots ,A^t|A^1)=P(A^t\left|A^{t-1}\right)P\left(A^{t-1}\right|A^{t-2})\cdots P(A^2\left|A^1\right)\text{\hspace{1em}(Temporal ERGM)}$$

마르코프 가정이 주어져 있음을 고려하면, evolving 네트워크 전반에 대해 ERGM 을 일반화하는 방법이란 $A^t|A^{t-1}$ 가 ERGM 표현법을 채택했음을 가정하는 것. to assume $A^t|A^{t-1}$ admits an ERGM representation.

함수 $\Psi :{\mathbb{R}}_{n\times n}\times {\mathbb{R}}_{n\times n}\to {\mathbb{R}}^k$ 를 생각해보자. 이는 시간적으로 인접한 2개의 네트워크 ($t$, $t-1$ 등) 에 걸친 cliques 들의 잠재적은 potential로 인지될 수 있다. 이때 패러미터 벡터 $\theta \in {\mathbb{R}}^k$ 는 이하와 같은 conditional pdf를 가지며, ${\theta }_i$ 는 곧 tendency to have more $S_i$ network statistics as time evolves.

$$P\left(A^t\right|A^{t-1},\theta )=\frac{1}{\kappa (\theta ,A^{t-1})}\exp \left\{{\theta }^{\prime }\Psi \left(A^t,A^{t-1}\right)\right\}$$

joint likelihood 에서 ${\theta }^{\prime }$ 는, as time evolves, how likely to have this network statistics.

특히 우리는 해당 모델에서 이하와 같은 특수한 경우에 관심이 있다.

$$\Psi \left(A^t,A^{t-1}\right)=\sum _{ij}{\Psi }_{ij}\left(A_{ij}^t,A^{t-1}\right)$$

이 형의 temporal potential 함수는 $A^t|A^{t-1}$의 조건부 분포의 This form of the temporal potential function represents situations where the conditional distribution of $A^t|A^{t-1}$ factors over the entries $A_{ij}^t$ of $A^t$.

Network Statistics for Temporal ERGM

여기서 4개의 network Statistics 를 제안하자. 여기서 $n$ 은 # of dyad.

\begin{align} S_D = \Psi_D \left ( A^t , A^{t-1}\right) &= \frac{1}{n-1} \sum_{ij = (i<j)} A^t_{ij} \tag{Density} \\ \Psi_S \left ( A^t , A^{t-1}\right) &= \frac{1}{n-1} \sum_{ij} \left \{ A^t_{ij} A^{t-1}_{ij} + \left (1-A^t_{ij} \right) \left (1-A^{t-1}_{ij} \right) \right \} \tag{Stability} \\ \Psi_R \left ( A^t , A^{t-1}\right) &= n \left ( \frac{\sum_\limits{ij} A_{ij}^t A_{ij}^{t-1}}{\sum_\limits{ij}A_{ij}^{t-1}}\right ) \tag{Reciprocity} \\ \Psi_T \left ( A^t , A^{t-1}\right) &= n \left ( \frac{\sum_\limits{ijk} A_{ik}^t A_{ij}^{t-1}A_{jk}^{t-1}} {\sum_\limits{ijk}A_{ij}^{t-1}A_{jk}^{t-1}}\right ) \tag{Transitivity} \end{align}

1. Density : 전체 네트워크에 들어있는 총 tie의 숫자. 단순 density.
2. Stability : $t-1$ 시점에 존재했던 link가 $t$ 시점에도 여전히 존재하는 경향성
3. Reciprocity : $t-1$ 시점에 $i$ 에서 $j$ 로 향하는 link가 있었다면 $t$ 시점에 $j\to i$ 링크가 생겨날 경향
4. Transitivity : $t-1$ 시점에 $i\to j$ 와 $j\to k$ 인 tie가 존재한다면, $t$ 에 $i\to k$ tie의 발생으로 이어지는 경향

Claim TERGM can avoid the model degeneracy problem: NOT CORRECT!!

Estimation

• Notation & Algorithm & Convergence

observed 네트워크의 sequence $N^1,N^2,\cdots ,N^T$ 를 사용하자. 무엇을 위해? 실제 패러미터값 $\theta$ 에 가까운 estimator $\hat{\theta }$ 을 찾기 위해. normalizing constant 는 보통 계산해내는 것이 불가능하여 MLE 방법론의 도입은 불가. 따라서 MCMC stochastic approximation 를 사용해 패러미터 estimate. 이하와 같이 notation 한다. 이때 t 시점의 네트워크인 랜덤변수 ${\underline{N}}^t$ 에 대해 기댓값들이 계산되었음을 notice.

$$\begin{array}{rl}L(\theta :N^1,N^2,\cdots ,N^T)=\log P(N^2,N^3,\cdots ,N^t|N^1,\theta )& \\ M(t,\theta )=E_{\theta }(\downarrow {\varphi }^t,\Lambda /v^{t-1})\mid N^{t-1})& \\ G(t,\theta )& =E_{\theta }\left(\Psi \right({\underline{\Lambda }}^t,\Lambda /N^{t-1}\left)\Psi \right({\underline{\Lambda }}^t,\Lambda /N^{t-1}{)}^T\mid \Lambda \ne \Lambda \prime \prime \end{array}$$

이때 이하의 기댓값들은 조건부 분포로부터 Gibbs 샘플링을 돌리는 것으로 근사 가능. Newton 방법론과 유사한 과정을 통해 unconstrained optimization 을 하자. 기댓값을 근사하고, Likelihood를 증가시키는 방향으로 패러미터값을 업데이트. 이 과정을 수렴하기까지 반복.

$$\begin{gathered} \Delta L(\theta :N^1,N^2,\cdots ,N^T)=\sum _{t=2}^T\left(\Psi \right(N^t,N^{t-1})-M(t,\theta \left)\right) \\ {△}^{2}L(\theta :N^1,N^2,\cdots ,N^T)=\sum _{t=2}^T\left(\mathrm{M}\right(t,\theta \left)\mathrm{M}\right(t,\theta {)}^{\prime }-C(t,\theta )) \end{gathered}$$

• algorithm

randomly initialize ${\theta }^{(1)}$.

$$\begin{array}{rl}{\hat{N}}_{(i)}^{t,1},\cdots ,{\hat{N}}_{(i)}^{t,B}& \sim P\left({\underline{N}}^t\mid {N^{t-1}}_{\cdot }{\theta }^{(i)}\right)\\ {\hat{\mu }}_{(i)}^t& =\frac{1}{B}\sum _{b=1}^B\Psi ({\hat{N}}_{(i)}^{t,b},N^{t-1})\\ {\hat{C}}_{(i)}^t& =\frac{1}{B}\sum _{b=1}^B\Psi \left({\hat{N}}_{(i)}^{t,b},N^{t-1}\right)\Psi {\left({\hat{N}}_{(i)}^{t,b},N^{t-1}\right)}^{\prime }\\ {\hat{H}}_{(i)}& =\sum _{i=2}^T\left({\mu }_{(i)}^t{\hat{\mu }}_{(i)}^t-{\hat{C}}_{(i)}^t\right)\end{array}\text{\hspace{1em}(after iteration)}$$ $${\theta }^{(i+1)}={\theta }^{(i)}-{\hat{H}}_{(i)}^{-1}\sum _{t=2}^T\left\{\Psi \right({\hat{N}}_{(i)}^{t,b},N^{t-1})-{\hat{\mu }}_{(i)}^t\}$$

Degeneracy of Temporal ERGMs

간단한 케이스에는, where the transition distribution factors over the edges, 이 모델들은 그러한 문제들에서 완전히 자유롭다는 것이 알려져 있음.

이는 직관적으로도 와닿음. $A_{ij}^t|A^{t-1}$ 의 개개의 조건부 분포가 과하게 극단적이지 않은 한, $A^{t-1}$이 주어졌을 때 $A^t$의 edge는 조건부 독립이기 때문이지. 따라서 $A^t|A^{t-1}$ 의 조건부 엔트로피는 커야 하며, 이에 의해 $A^t$의 조건부 엔트로피도 커야 할테니까.

물론 이 명제는 $A^{t-1}$ 에 대한 $A^t$ 의 의존이 그렇게 강하지 않을 때만 성립하는 것임. 이때 이 의존의 위력은 패러미터들의 위력에 의해 결정되지. 그러니까 패러미터가 이상하게 잡히면 해당 명제의 전제가 깨진다는 거.

동일한 확률값을 가진다는 것을 analytic 하게 보일 수 있는 그래프들의 class들, 즉 equivalence 클래스들에 대해서 이를 계산해보고, 엔트로피 계산에서 각각의 클래스의 크기에 따라서 weight를 부여하자.

첫 플랏의 경우를 생각해보자. $A^2|A^1$ 의 조건부 분포는 결국 $A^2$ 에 존재하는 edge의 갯수와, 얼마나 많은 $ij$ 값들에게서 $A_{ij}^2=A_{ij}^1$가 성립하고 있느냐, 의 2개의 값에 대한 함수일 뿐이다. 이에 더해 $A^1$의 edge들은 exchangeable 하다는 점도 있다. 이들을 모두 생각해보면 결국 우리는 $A^2$의 marginal 분포를 순수하게 edge의 숫자를 통해서만 서술하는 것이 가능하다.

따라서 우리는 $n(n-1)$의 확률값만 계산해내면 되며, 따라서 엔트로피는 weighted sum이다. 이때 weight는 각각의 edge 숫자에 대해, that many edges 를 가지고 있는 그래프의 숫자가 반영된 combinatorial quantities 가 된다.

Assessing Statistic Importance and Quality of Fit

Description of Network Statistics - 108th U.S. Senate Network Example

Three Parameter Model, Seven, Nine

${\Psi }_{RT}\left({\mathcal{A}}_{\cdot }{\mathcal{A}}_{\mu }^{t-1}\right)\equiv \mathcal{H}\left({\sum }_{ijk}{\mathcal{A}}_{ij}^t{\mathcal{A}}_{jk}^{t-1}{\mathcal{A}}_{ki}^{t-1}\right)/\left({\sum }_{ijk}{\mathcal{A}}_{jk}^{t-1}{\mathcal{A}}_{ki}^{t-1}\right).$

${\Psi }_{CSo}({\lambda }_{,}^t,{\lambda }_{}^{t-1})\genfrac{}{}{0ex}{}{=1}{ijk}{\mathcal{A}}_{ij}^t{\bar{A}}_{kj}^{t-1}{\mathcal{A}}_{kj}^{t-1}\left)\right({\sum }_{ijk}{\mathcal{A}}_{ki}^{t-1}{\mathcal{A}}_{kj}^{t-1})\dots$

${\Psi }_{CSd}({\lambda }_{,K}^t,{\lambda }_{}^{t-1})\ne ı\left({\sum }_{ijk}{\lambda }_{ij}^t{\lambda }_{ik}^{t-1}{\lambda }_{jk}^{t-1}\right)/\left({\sum }_{\frac{ijk}{jk}}{\lambda }_{ik}^{t-1}{\lambda }_{jk}^{t-1}\right).$

${\Psi }_P({\mathcal{A}}_{,}^t,{\mathcal{A}}^{t-1})\equiv \mathcal{H}\left({\sum }_{jk}{\mathcal{A}}_{kj}^t{\mathcal{A}}_{jj}^{t-1}\right)/\left({⨂}_{ij}{\mathcal{A}}_{kj}^{t-1}\right).$

${\Psi }_G({\partial }_{,}^t,{\partial }_{}^{t-1})⟹\left({\sum }_{ijk}{\mathcal{A}}_{ik}^t{\mathcal{A}}_{ij}^{t-1}\right)/\left({\sum }_{ij}{\mathcal{A}}_{ik}^{t-1}\right).$

Reverse-Transitivity: Co-Supported: Co-Supporting: Popularity Generosity

Separable Temporal ERGM (STERGM, ST ERGM)

• STERGM = A Separable Model for Dynamic Network
• Dynamic: social networks that evolve over time
• Time(discrete): $\cdots (t-2)\to (t-1)\to (t)\to \cdots$

Shows longitudinal properties based on the ERGM

• Separable Temporal ERGM
  • formation of an edge: new ties
  • duration of an edge: lasting ties
• 즉, model formation / duration seperatively.

Temporal ERGM Interpretation

하지만 이때 패러미터 해석할 때 주의해야할 부분이 있음.

1. Property1: incidence of ties / tie formation (the rate at which new ties are formed)

$$Y^{+}=Y^{t-1}\cup Y^t$$

2. Property2: duration of ties / tie dissolution (how long they tend to last once they do)

$$Y^{-}=Y^{t-1}\cap Y^t\Rightarrow Y^t=Y^{-}\cup (Y^{+}\setminus Y^{t-1})$$

given $Y^{t-1}$, we assume $Y^{+}$ and $Y^{-}$ are conditionally independent.

$$\begin{array}{r}P(Y^{+}=y^{+}|Y^{t-1}=y^{t-1};{\theta }^{+})=\frac{1}{\kappa ({\theta }^{+}}\exp (\sum _{i=1}^P{\theta }_i^{+}{S}_i^{+}(Y^{+},y^{t-1}))\\ P(Y^{-}=y^{-}|Y^{t-1}=y^{t-1};{\theta }^{-})=\frac{1}{\kappa ({\theta }^{-}}\exp (\sum _{i=1}^P{\theta }_i^{-}{S}_i^{-}(Y^{-},y^{t-1}))\end{array}$$

• $S_i^{\pm }(Y^{\pm },y^{t-1})$ 는 $S_i(y^{\pm })$, $S_i(y^{t-1})$ 사이의 difference.
• $S_i(\cdot )$ 는 ERGM 상에서의 아무 network statistics

$$P(Y^t=y^t|Y^{t-1}=y^{t-1})=P(Y^{+}=y^{+}|Y^{t-1}=y^{t-1};{\theta }^{+})\cdot P(Y^{-}=y^{-}|Y^{t-1}=y^{t-1};{\theta }^{-})$$

• Network statstic

(ex) edge count $g(y^t,y^{t-1})=|y^t|$

coefficient on $g$ $\propto$ possibility of a network with many ties. 따라서 $g$의 계수가 올라가면 tie가 많은 네트워크의 발생 확률 올라감.

But, this term simultaneously increases the weight of preservation of extant ties (fewer dissolved) ⇒ Both incidence and duration ↑

The two-sided nature of these effects tends to muddle parameter interpretation. ⇒ STERGM which separates the incidence and duration of ties and allows for the separate interpretation.

• : incidence/tie formation $y^{+}=y^{t-1}\cup y^t$ – : duration/tie dissolution $y^{-}=y^{t-1}\cap y^t\Rightarrow y^t=y^{-}\cup (y^{+}\setminus y^{t-1})$

$Pr(y^{+}=y^{+}|Y^{t-1}=y^{\iota -1};{\theta }^{+})=\frac{\theta xp({\eta }^{+}({\theta }^{+})\ast {\mathcal{O}}^{+}(y^{+},y^{I-1}))}{G_{{\eta }^{+},g^{+}}({\theta }^{+},y^{\iota -1})}$

$Pr(Y^{-}=y^{-}|Y^{t-1}=y^{t-1};{\theta }^{-})=\frac{\theta xp({\eta }^{-}({\theta }^{-})\ast g^{-}(y^{-},y^{t-1}))}{c_{{\eta }^{-},g^{-}}({\theta }^{-},y^{t-1})}$

${\mathcal{P}}_I({\mathcal{V}}^t\underline{-}{\mathcal{V}}^{t-1}\underline{-}{\mathcal{D}}^{t-1}\underline{-}\mathcal{J})\times \text{incidence}\times \text{duration}$

$Pr(y^{+}=y^{+}|Y^{t-1}=y^{\iota -1};{\theta }^{+})$

$Pr(y^{-}=y^{-}|Y^{t-1}=y^{\iota -1};{\theta }^{-})$

:::{.definition name = “1”} Definition 1 We say that a dynamic model is separable if Y+ is conditionally independent of Y− given Y t−1 and the parameter space of θ is the product of the individual parameter spaces of θ+ and θ−.

:::

• Assumption: During a given discrete time step, the process by which the ties form does not interact with the process by which they dissolve.

1. Lost: In the parameterization in terms of formation and dissolution, some flexibility(formation and dissolution processes interact within a given time step) is lost

2. Gain: Ease of specification, tractability of the model and substantial improvement in interpretability of TERGM

Now the parameter and its interpretation have an implicit direction. (formation or duration)

• Formation network (+) is related to formation network only

$\mathrm{Pr}({\mathbf{V}}^{-}={\mathbf{y}}^{-}|{\mathbf{V}}^{t-1}={\mathbf{y}}^{t-1};{\mathbf{\theta }}^{-})=\frac{\exp \{({\theta }^{+}{)}^{\cdot 7}{g}^{+}(y^{+},y^{\dot{t}-1})}{c_{g^{+}}({\theta }^{+},y^{t-1})}$

• Duration network (or Dissolution network)

$\mathrm{Pr}({\mathbf{V}}^{-}={\mathbf{y}}^{-}|{\mathbf{V}}^{t-1}={\mathbf{y}}^{t-1};{\mathbf{\theta }}^{-})=\frac{\exp \{({\mathbf{\theta }}^{-}),{\mathbf{\gamma }}^{t-1}\}}{c_o({\mathbf{\theta }}^{-},{\mathbf{\gamma }}^{t-1})}$

(-) is related to duration network only

• Example of Parameter Interpretation (Edge Count)

Now the parameter and its interpretation have an implicit direction. (formation or duration) Formation network Edge count g + (y + , y t−1 ) = |y + |, y

• = y t−1 ∪ y t Recall, y

is network about formation θ

• means log-odds of gaining new tie from y t−1 =⇒ y t Dissolution network Edge count g −(y −, y t−1 ) = |y −| , y − = y t−1 ∩ y t Recall, y − is network about duration θ − means log-odds of existing tie to survive at y t−1 =⇒ y

• Likelihood-based Inference for STERGM

Fit STERGM by finding conditional MLE under an order 1 Markov assumption:

$$\begin{array}{rlrl}\hat{\theta }& =\arg {\max }_{\theta }& & \prod _{t=1}^T\mathrm{Pr}(Y^t=y^t|Y^{t-1}=y^{t-1})\\ & =& & \prod _{t=1}^T\frac{\exp \{({\theta }^{+}{)}^{\cdot T}{g}^{+}(y^{+},y^{t-1})\}}{c_{g^{+}}({\theta }^{+},y^{t-1})}\cdot \frac{\exp \{({\theta }^{-})\cdot g^{-}(y^{-},y^{t-1})\}}{c_{g^{-}}({\theta }^{-},y^{t-1})}.\end{array}$$

• where $c_g(\theta ,y^{t-1})={\sum }_{y^{\prime }\in \psi }\exp \{(\theta {)}^{\cdot T}g(y,y^{t-1})\}$

In practical, MLE can be obtained by maximizing the log-likelihood using numerical optimization.

The normalizing constant $c_{g^{+}}({\theta }^{+},y^{t-1})$ 와 $c_{g^{-}}({\theta }^{-},y^{t-1})$ 는 계산 불가. 각각은 시뮬레이션을 통해 (e.g. MCMCMLE) 를 통해 획득됨

i.e. maximizing $I(\theta )-I({\theta }^0)=\{\theta -{\theta }^0\}{\sum }_{t=1}^{T}g(y^t,y^{t-1})-\log \left\{{\prod }_{t=1}^T\frac{c_g(\theta ,y^{t-1})}{c_g({\theta }^0,y^{t-1})}\right\}$

Application Study

Conclusion

1. Introduce statistical model for networks that evolve over time.
2. Separable parameterization of incidence and duration.
3. Greatly improve interpretability of model parameters, with sacrificing a little.
4. Identify the structure of incident and durational structure