7.7 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) → (t)\) (Markov Assumption)
\[ P_{\eta, g} \Big ( Y^t = y^t \Big | Y^{t-1} \; \; ; \; \; \theta \Big ) = \frac{\exp \Big \{ \eta(\theta) \cdot g(y^t, y^{t-1})\Big \}}{c_{\eta, h}(\theta, y^{t-1})} \]
7.7.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\Big(A^2, A^3, \cdots, A^t \Big | A^1 \Big ) = P\Big(A^t \Big | A^{t-1} \Big ) P\Big(A^{t-1} \Big | A^{t-2} \Big ) \cdots P\Big(A^2 \Big | A^1 \Big ) \tag{Temporal ERGM} \]
마르코프 가정이 주어져 있음을 고려하면, evolving 네트워크 전반에 대해 ERGM 을 일반화하는 방법이란 \(A^t \vert A^{t-1}\) 가 ERGM 표현법을 채택했음을 가정하는 것. to assume \(A^t \vert A^{t-1}\) admits an ERGM representation.
함수 \(\Psi : \mathbb R_{n \times n} \times \mathbb R_{n \times n} \rightarrow \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 \bigg( A^t \Big | A^{t-1}, \theta \bigg) = \frac{1}{\kappa(\theta, A^{t-1})} \exp \left\{ \theta' \Psi \left ( A^t, A^{t-1} \right ) \right\} \]
joint likelihood 에서 \(\theta '\) 는, as time evolves, how likely to have this network statistics.
특히 우리는 해당 모델에서 이하와 같은 특수한 경우에 관심이 있다.
\[ \Psi \left ( A^t, A^{t-1} \right ) = \sum_{ij}\Psi_{ij} \left ( A^t_{ij}, 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^t_{ij}\) of \(A^t\).
7.7.1.1 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}\]
$$
- Density : 전체 네트워크에 들어있는 총 tie의 숫자. 단순 density.
- Stability : \(t-1\) 시점에 존재했던 link가 \(t\) 시점에도 여전히 존재하는 경향성
- Reciprocity : \(t-1\) 시점에 \(i\) 에서 \(j\) 로 향하는 link가 있었다면 \(t\) 시점에 \(j→i\) 링크가 생겨날 경향
- Transitivity : \(t-1\) 시점에 \(i→j\) 와 \(j→k\) 인 tie가 존재한다면, \(t\) 에 \(i→k\) tie의 발생으로 이어지는 경향
Claim TERGM can avoid the model degeneracy problem: NOT CORRECT!!
7.7.1.2 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{align} L\Bigl(\theta:N^{1},{ N}^{2},\cdots ,{ N}^{T}\Bigr) =\log P\Bigl({ N}^{2},{ N}^{3},\cdots,{ N}^{t}\,\Bigg \vert\,{ N}^{1},\theta\Bigr) \\ M\Bigl(t,\theta\Bigr) = E_{\theta}\Bigl(\downarrow\phi^{t},\Lambda\not v^{t-1}\Bigr)\mid{{N}}^{t-1}\Bigr) \\ G\Bigl(t,\theta\Bigr) &=E_{\theta}\Bigl(\Psi\Bigl(\underline{{{\Lambda}}}^{t},\Lambda\not{N}^{t-1}\Bigr)\Psi\Bigl(\underline{{{\Lambda}}}^{t},\Lambda\not{N}^{t-1}\Bigr)^{T}\mid\Lambda\not=\Lambda\prime\prime \end{align} \]
이때 이하의 기댓값들은 조건부 분포로부터 Gibbs 샘플링을 돌리는 것으로 근사 가능. Newton 방법론과 유사한 과정을 통해 unconstrained optimization 을 하자. 기댓값을 근사하고, Likelihood를 증가시키는 방향으로 패러미터값을 업데이트. 이 과정을 수렴하기까지 반복.
\[ \Delta{ L}\Bigl(\theta:N^1 , N^2 , \cdots, N^T \Bigr) = \sum_{t=2}^{T}\Bigl(\Psi\big( N^t, N^{t-1} \Bigr)-M\big(t,\theta\big)\Bigr) \\ \triangle^{2} L\Big(\theta:N^1 , N^2 , \cdots, N^T\Big)= \sum_{t=2}^{T}\Big(\mathrm{M}\big(t,\theta\big)\mathrm{M}\big(t,\theta\big)^{\prime}-{{C}}\big(t,\theta\big)\Big) \]
- algorithm
randomly initialize \(\pmb \theta^{(1)}\).
$$ \[\begin{alignat}{2} \hat{N}_{(i)}^{t,1},\cdots, \hat{N}_{(i)}^{t,B} & \sim\,{P}\left(\underline N^t\,\mid\,{N^{t-1}}_{\cdot}\,\pmb{\theta}^{(i)}\right) \\ \hat{\mu}_{(i)}^{t} & = {\frac{1}{B}}\sum_{b=1}^{B}\Psi\Big(\hat{ N}_{(i)}^{t,b},N^{t-1}\Big) \\ \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)' \\ \hat{H}_{(i)} & {=}\sum_{i=2}^{T}\left(\mu_{(i)}^{t}\hat{\mu}_{(i)}^{t}-\hat{C}_{(i)}^{t}\right) \tag{after iteration} \\ \end{alignat}\] $$
\[ \pmb \theta^{(i+1)} = \pmb \theta^{(i)}-\hat{{H}}_{(i)}^{-1}\sum_{t=2}^T\Bigg\{\Psi\Big(\hat{N}_{(i)}^{t,b},N^{t-1}\Big)-\hat{\mu}_{(i)}^{t}\Bigg\} \]
7.7.1.3 Degeneracy of Temporal ERGMs
간단한 케이스에는, where the transition distribution factors over the edges, 이 모델들은 그러한 문제들에서 완전히 자유롭다는 것이 알려져 있음.
이는 직관적으로도 와닿음. \(A^t_{ij} | 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^2_{ij} = A^1_{ij}\)가 성립하고 있느냐, 의 2개의 값에 대한 함수일 뿐이다. 이에 더해 \(A^1\)의 edge들은 exchangeable 하다는 점도 있다. 이들을 모두 생각해보면 결국 우리는 \(A^2\)의 marginal 분포를 순수하게 edge의 숫자를 통해서만 서술하는 것이 가능하다.
따라서 우리는 \(n(n − 1)\)의 확률값만 계산해내면 되며, 따라서 엔트로피는 weighted sum이다. 이때 weight는 각각의 edge 숫자에 대해, that many edges 를 가지고 있는 그래프의 숫자가 반영된 combinatorial quantities 가 된다.
7.7.1.4 Assessing Statistic Importance and Quality of Fit
Description of Network Statistics - 108th U.S. Senate Network Example
Three Parameter Model, Seven, Nine
\(\Psi_{R T}\left(\mathcal{A}_{\ \cdot}\mathcal{A}_{\ \ \ \ \ \ \ \ \ \mu}^{t-1}\right)\equiv\mathcal{H}\!\left(\sum_{i j k}\mathcal{A}_{i j}^{t}\mathcal{A}_{j k}^{t-1}\mathcal{A}_{k i}^{t-1}\right)\big/\left(\sum_{i j k}\mathcal{A}_{j k}^{t-1}\mathcal{A}_{k i}^{t-1}\right).\)
\(\Psi_{C S o}\Bigl(\lambda_{~,}^{t},\lambda_{~}^{t-1}\Bigr)\mathop{\displaystyle=\,1\atop i j k}\mathcal{A}_{i j}^{t}\bar{A}_{k j}^{t-1}\mathcal{A}_{k j}^{t-1}\Bigr)\Bigl(\sum_{i j k}\mathcal{A}_{k i}^{t-1}\mathcal{A}_{k j}^{t-1}\Bigr)\dots\)
\(\Psi_{C S d}\Bigl(\lambda_{\phantom{0},K}^{t},\lambda_{\phantom{-1}}^{t-1}\Bigr)\not=\imath\Bigl(\sum_{i j k}\lambda_{i j}^{t}\lambda_{i k}^{t-1}\lambda_{j k}^{t-1}\Bigr)\Bigl/\Bigl(\sum_{\textstyle{\frac{i j k}{j k}}}\lambda_{i k}^{t-1}\lambda_{j k}^{t-1}\Bigr).\)
\(\Psi_{P}\Bigl(\mathcal{A}_{\phantom{0},}^{t},\mathcal{A}^{t-1}\Bigr)\equiv\mathcal{H}\Bigl(\sum_{j k}\mathcal{A}_{k j}^{t}\mathcal{A}_{j j}^{t-1}\Bigr)\big/\left(\bigotimes_{i j}\mathcal{A}_{k j}^{t-1}\right).\)
\(\Psi_{G}\Bigl(\partial_{~,}^{t},\partial_{}^{t-1}\Bigr)\Longrightarrow\left(\sum_{i j k}\mathcal{A}_{i k}^{t}\mathcal{A}_{i j}^{t-1}\right)\Bigl/\left(\sum_{i j}\mathcal{A}_{i k}^{t-1}\right).\)
Reverse-Transitivity: Co-Supported: Co-Supporting: Popularity Generosity
7.7.2 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) → (t-1) → (t) → \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.
7.7.2.1 Temporal ERGM Interpretation
하지만 이때 패러미터 해석할 때 주의해야할 부분이 있음.
- Property1: incidence of ties / tie formation (the rate at which new ties are formed)
\[ Y^+ = Y^{t-1} \cup Y^{t} \]
- 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 \Big( Y^+ \setminust Y^{t-1}\Big) \]
given \(Y^{t-1}\), we assume \(Y^+\) and \(Y^-\) are conditionally independent.
\[ \begin{align} P(Y^+ = y^+ | Y^{t-1} = y^{t-1} ; \theta^+) = \frac{1}{\kappa(\theta^+} \exp \Big( \sum_{i=1}^P \theta_i^+ S_i^+(Y^+ , y^{t-1})\Big) \\ P(Y^- = y^- | Y^{t-1} = y^{t-1} ; \theta^-) = \frac{1}{\kappa(\theta^-} \exp \Big( \sum_{i=1}^P \theta_i^- S_i^-(Y^- , y^{t-1})\Big) \end{align} \]
- \(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})\)
\(P r(y^{+}=y^{+}\vert Y^{t-1}=y^{\iota-1};\theta^{+})=\frac{\theta x p(\eta^{+}(\theta^{+})*\mathcal{O}^{+}(y^{+},y^{I-1}))}{G_{\eta^{+},g^{+}}(\theta^{+},y^{\iota-1})}\)
\(P r(Y^{-}=y^{-}|Y^{t-1}=y^{t-1};\theta^{-})=\frac{\theta x p(\eta^{-}(\theta^{-})*g^{-}(y^{-},y^{t-1}))}{c_{\eta^{-},g^{-}}(\theta^{-},y^{t-1})}\)
\({\cal P}_{I}(\mathcal{V}^{t}\underline{{{-}}}\mathcal{V}^{t-1}\underline{{{-}}}\mathcal{D}^{t-1}\underline{{{-}}}\mathcal{J}) \times \text{incidence} \times \text{duration}\)
\(P r(y^{+}=y^{+}\vert Y^{t-1}=y^{\iota-1};\theta^{+})\)
\(P r(y^{-}=y^{-}\vert 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.
Lost: In the parameterization in terms of formation and dissolution, some flexibility(formation and dissolution processes interact within a given time step) is lost
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
\(\Pr(\mathbf{V}^{-}={\boldsymbol{y}}^{-}|\mathbf{V}^{t-1}={\boldsymbol{y}}^{t-1};{\boldsymbol{\theta}}^{-})={\frac{\exp\{(\theta^{+})^{\cdot7}g^{+}(y^{+},y^{\dot{t}-1})}{c_{g^{+}}(\theta^{+},y^{t-1})}}\)
- Duration network (or Dissolution network)
\(\Pr(\mathbf{V}^{-}={\boldsymbol{y}}^{-}|\mathbf{V}^{t-1}={\boldsymbol{y}}^{t-1};{\boldsymbol{\theta}}^{-})={\frac{\exp\{({\boldsymbol{\theta}}^{-}),{\boldsymbol{\gamma}}^{t-1}\}}{c_{o}({\boldsymbol{\theta}}^{-},{\boldsymbol{\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{align} \hat{\theta} &= \arg\mathrm{max}_{\theta}&&\prod_{t=1}^{T}\mathrm{Pr} \Big ({Y}^{t}=y^{t} \Big | {Y}^{t-1}=y^{t-1} \Big) \\ &= &&\prod_{t=1}^{T}\frac{\exp \Big \{ (\theta^{+})^{\cdot T}g^{+}(y^{+},y^{t-1}) \Big\} } {c_{g^{+}}(\theta^{+},y^{t-1})} \cdot \frac{\exp\Big\{(\theta^{-})\cdot g^{-}(y^{-},y^{t-1})\Big\}}{c_{g^{-}}(\theta^{-},y^{t-1})}. \end{align}\] $$
- where \(c_{g}(\theta,y^{t-1})=\sum_{y^{\prime}\in\psi}\exp \Big \{(\theta)^{\cdot T}g(y,y^{t-1}) \Big\}\)
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\Big\{\prod_{t=1}^{T}\frac{c_{g}(\theta,y^{t-1})}{c_{g}(\theta^{0},y^{t-1})}\Big\}\)