7.8 Latent Network Models

7.8.1 Latent Position Model

ERGMs 와 다르게, 이 모델은 소셜 스페이스의 개념을 도입함. 이 소셜 스페이스에서는, 네트워크 관계에 있어 unobserved latent 특성이 potential transitive 경향을 represent, 즉 위력? 을 나타낼 수 있음. 이때 이 소셜 스페이스에서 각 actor (혹은 node) \(i\)는 알려지지 않은 포지션 \(z_i\)를 각각 차지하게 됨. 우리는 이를 latent position 이라고 부름.

여기서 우리는 주된 가정으로 ties 간의 조건부 독립을 가정한다. latent position이 주어진다면, 네트워크 안의 ties들은 조건부 독립임이 가정된다. 두 개인들 간의 특정한 tie의 확률은 그들의 positions 들의 함수로 모델링된다. 가령 소셜 스페이스 안에서의 두 actor 사이의 거리라던가.

  • main assumption
    • given the latent position, each connection is conditionally independent each others
    • latent positions can capture all dependence structures
    • the prob of having an edge is a function of latent positions
      • 이때 주로 사용되는 function 은 distance.

이때 이를 노테이션으로 표기하자면 다음과 같다. 아래는 joint likelihood function.

\[ P(Y | Z, X, \theta) = \prod_{i \not = j, i<j} P(y_{i,j} | z_i , z_j , x_{i,j}, \theta) \]

  • \(i<j\) 는 undirected network 상황에서
  • sociomatrix (binary network) \(Y_{n \times n}\), 이때 요소 \(y_{i,j}\)는 actor \(i\)로부터 \(j\)로의 관계를 의미하는 값.
  • additional covariate information \(X\) (nodal covaraites)
  • 이때 \(X\)와 \(x_{i,j}\)는 unobserved 성질이며, \(\theta\)는 estimate되어야 하는 패러미터, \(Z\)는 estimate 되어야 하는 포지션.
    • \(z_i\): node \(i\) 의 latent position.




7.8.1.1 Methods

7.8.1.1.1 Distance Models

\(P(y_{i,j} | z_i , z_j , x_{i,j}, \theta)\)는 logistic regression framework 를 활용하는 것으로 편하게 패러미터化 (설명) 할 수 있다. 이렇게 패러미터化 할 때 tie의 확률은 \(z_i , z_j \in \mathbb R\) 인 \(z_i , z_j\) 사이의 euclidean distance 에 의존한다. 수식은 아래와 같다.

\[ \eta_{i,j} = logodds (y_{i,j} = 1 | z_i , z_j , x_{i,j}, \alpha, \beta) = \underbrace{\alpha}_{\text{intercept}} + \underbrace{\beta ' }_{\substack{\text{effect of}\\\text{nodal covariates}}} x_{i,j}- \underbrace{|z_i - z_j |}_{\text{euclidean}} \]

\[ \begin{alignat}{2} P(Y|Z,X,\theta) &= \prod_{i<j} &&\pi_{ij}^{y_{ij}}&&(1-\pi_{ij})^{1-y_{ij}} &= \prod_{i<j} &&\left(\frac{\exp(\alpha + \beta x_{ij} - \|z_i - z_j \|)} {1+\exp(\alpha + \beta x_{ij} - \|z_i - z_j \|)} \right)^{y_{ij}} &&\left(\frac{1}{1+\exp(\alpha + \beta x_{ij} - \|z_i - z_j \|)} \right)^{1-y_{ij}} \end{alignat} \]

  • 이때 distance \(|z_i - z_j |=d_{ij}\) 는 그 어떤 metric으로도 대체될 수 있다는 것을 notice. 삼각부등식 \(d_{i,j} \le d_{i,k} + d_{k,j}\)만 만족하면 됨.
    • \(d_{ij}\) 이 증가하면 edge 를 가질 prob은 감소. 역도 성립. out of sight, out of mind.

latent 포지션 모델은 본질적으로 reciprocal 하고 transitive 함. 왜? 만약 \(i \rightarrow j\) 이고 \(j \rightarrow k\) 이라면, \(d_{i,j}\) 와 \(d_{j,k}\) 는 어쩌면 지나치게 크지는 않을 수도 있는 것이고, 이 경우에는 이하로 이어짐:

  1. events \(j \rightarrow i\) (reciprocity)
  2. 그리고 \(i \rightarrow k\) (transitivity)

when a node \(i,j,k\) are connected, the latent position of \(z_i\) and \(z_j\) are close.

  • benefits: visualize the relationship / very easy to capture the cluster - structures disadvantages: even though a latent space model can capture the transitivities with triangle inequalities, it still has a limitatino in capturing a high-order dependence




7.8.1.1.2 Projection Models

Invariance of distance. distance 모델은 본질적으로 symmetric 임. 즉 \(p(i → j) = p(j → i)\). 하지만 많은 (directed) 모델에서 이런 symmetry 는 성립을 안함. 예를 들어 actor \(i\) 가 대량의 ties 들을 보내는 반면 \(j\) 가 \(i\) 에게서 ties 들을 받은 actors 전체 중 작은 subset 에게만 보낸다면? 따라서 행위의 변수 레벨은 관계에서 확률의 transitivity 를 allow하는 latent 포지션 모델의 맥락 속에서 모델링될 필요가 있다. 개개인의 소셜 활동의 특정한 수준도 고려되어야 함은 물론이다.

그러나 likelihood 는 only include a distance function -> distance 는 2개의 latent position 사이의 infinite realization 을 보유.

latent position 들 자체도 무한한 realization 이 존재.

-> Bayesian Inference

-> post-process for posterior sample (Procrustes Matching: based on a reference point, all posterior samples are moved / rotated tward a reference point. commonly used in statistical shape analysis)

  1. set up a reference point generally a posterior sample that yiedls MAP (Maximum A Posterior)

  2. all other posterior samples are transformed by procrustes matching -> \(procrustes(X_{ref}, X_{ref})\) in MCMCpack pacakage of R.

distance -> undirected network projection method -> directed network

actor \(i\)의 특성의 벡터 \(v_i\)를 unit \(k\)-dim 이라고 가정. \(i,j\) 사이의 angle 에 따라 둘 사이에 tie 가 존재할 가능성이 이하와 같이 영향받는다.

  • 예각: high
  • 직각: neutral
  • 둔각: low

actor \(i\) 의 활동 레벨 \(a_i >0\) 를 설정한 후, \(i→j\)의 tie의 존재 확률을 \(a_i v_i ' v_i = \frac{z_i' z_j}{| z_j |}\) (이때 \(z_i = \underbrace{a_i}_{\text{strength (length)}} \underbrace{v_i}_{\text{unit vector}}\)) 라고 설정한다면 이하의 등식이 성립.

\[ \eta_{i,j} = logodds (y_{i,j} = 1 | z_i , z_j , x_{i,j}, \alpha, \beta) = \alpha + \beta ' x_{i,j} + \frac{z_i' z_j}{| z_j |} \]

from note:

\[ \pi_{ij} = logodds(y_{ij} | z_i , z_j , \alpha) = \alpha + \frac{z_i ' z_j}{\|z_i \|} \\ \pi_{ji} = \phantom{logodds}(y_{ji} | \phantom{z_i , z_j , \alpha) = \alpha} + \frac{z_j ' z_i}{\|z_j \|} \]

Latent Space Model (LSM)

-> map each node into unobserved latent space -> easy to visualized -> easy to observe cluster structures

  1. LSM \(z_i \sim (0, \sigma^2)\), \(\pi(z_i) \sim N(0, \sigma^2)\)

-> need a model that capture clusture structures using a model

여기서 \(z_i\) 는 mixture normal prior (one of the typical way to implement clustering)




7.8.1.2 Estimation

Distance 모델 상황을 생각해보자. 유클리드 공간에서 set points 간의 거리는 회전, 반사, 이동에 불변 (invariant). 따라서 모든 각각의 latent postion의 행렬 \(Z_{k \times n}\) 에 대해 같은 log-likelihood 를 갖는 다른 positions 을 표상하는 행렬이 존재한다.

\(\mathcal Z\) 를 회전, 반사, 이동에 불변한 \(Z\)와 equivalent 한 postions들의 class 라고 하자. 각각의 \(\mathcal Z\)에 대해 node 들 간의 거리를 모아 set 1개가 나옴. 이러한 positions 들의 class를 configuration 이라고 부름.

마찬가지로 Projection 모델에서의 \(Z\) 에 대해서도 Projection 모델들은 positions 들의 회전과 반사에는 불변하지만, 이동에 대해서는 불변이 아님.

조건부 독립 모델의 log-likelihood 모델은 다음과 같다:

\[ \log P(Y | \eta ) = \sum_{i \not = j} \Big \{ \eta_{i,j}y_{i,j} - \log (1+\exp(\eta_{i,j}) \Big \} \]

※ Steps:

  1. 각 j 에서 \(z_j '\) 샘플링하기 위해 MH 스텝 거침. proposal 분포 \(\varphi(\cdot)\) 으로부터 \(z_j'\) 생산하고 이를 이하의 확률 \(r_z \left ( z_j ' , z_j^{(t)} \right)\) 로 채택. 비슷환 과정을 따라서 \(\alpha, \beta\) 도 MH 이용해서 생산.

\[ r_z \left ( z_j ' , .z_j^{(t)} \right) = \frac{\pi \Big (z_j ' \Big \vert Y, \alpha , \beta \Big )}{\pi \Big (z_j^{(t)} \Big \vert Y, \alpha , \beta \Big )} \cdot \frac{\varphi \Big (z_j ' \rightarrow z_j^{(t)} \Big )}{\varphi \Big ( z_j^{(t)}\rightarrow z_j ' \Big )} \]

  1. Procrustes 매칭 사용해서 MCMC 샘플 후처리.

    1. latent positions 들의 reference set 을 찾기 위해, MCMC 샘플로부터 latent positions들 중 full log posterior density가 가장 높은 latent positions들 \(Z_0\)를 하나 뽑아서 쟁여둠
    2. \(Z_0\)를 사용해서 각각의 MCMC 샘플에 Procrustes 매칭 적용

\[ Z^\ast = \arg \min_{TZ} tr \Big \{ (Z_0 - TZ) ' (Z_0 - TZ) \Big \} \]




7.8.1.3 Advantages

네트워크 관계에 대한 시각적이고 모델에 기반한 공간적인 표현을 제공. 해석 용이함.

It is flexible and can be easily generalized to allow for multiple relationships, ties with varying strengths, and time-varying relations

deal easily with missing data, at least if information on ties is missing at random

the model is inherently transitive, and so we can expect an improved fit over models lacking such structure when the relations are transitive in nature







7.8.2 Latent Position Cluster Model

$$ \[\begin{align} \log \frac{P(y_{i, j} = 1\Big | z_i , z_j , x_{i,j}, \beta)}{1 - P(y_{i, j} = 1 \Big | z_i , z_j , x_{i,j}, \beta)} &= \beta_0 ' x_{i,j} - \beta_1 |z_i - z_j | \\ P(Y | Z, X, \beta) &= \prod_{i \not = j} P(y_{i, j} \Big | z_i , z_j , x_{i,j}, \beta) \tag{Likelihood} \end{align}\] $$

  • \(z_i \sim \sum\limits_{g=1}^G \lambda_g \cdot MVN_d )\mu_g , \sigma^2_g I_d )\), where \(\sqrt{\frac{1}{n} \sum_i |z_i|^2} = 1\).
  • \(\lambda_g\)는 individual distribution의 비율




  1. Latent position cluster model

\[ z_i \sim \sum^G_{g=1} \lambda_g \cdot MVN(\mu_g , \sigma^2_g I) \]

  • \(\lambda_g\): proportion of an individual distribution (probability of belonging to cluster \(g\) from node \(i\))
  • \(\mu_g\): center of cluster position
  • \(\sigma_g^2\): size of cluster

이때 \(\sqrt{\frac{1}{n} \sum\limits^n_{i=1}\|z_i\|^2} = 1\)

\[ logodd \pi_{ij} = \beta_0 ' x_{ij} - \beta_1 |z_i - z_j| = \alpha - \beta \|z_i - z_j\| \]

7.8.2.1 Bayesian Estimation

※ Fully Bayesian Estimation Procedure

  1. 모델 패러미터 \(\beta, \lambda_g, \mu_g, \sigma_g^2\) 들의 prior 분포 특정

$$ \[\begin{align} \beta &\sim MVN_p \left( \xi , \Psi \right) \\ \lambda &\sim Dirichlet(\nu) \\ \sigma^2_g &\sim \sigma_0^2 Inv- \chi_\alpha^2 && g = 1, \cdots, G \\ \mu_g &\sim MVN_d \left( 0, \omega^2 \cdot I_d \right) && g = 1, \cdots, G \end{align}\] $$

  1. \(\mathbf z_i , \beta, \lambda, \mu_g ,\sigma^2_g, K_i\)의 full 조건부 posterior 분포 특정

$$ \[\begin{align} {\bf z}_{i}\mid K_{i}=g,\mathrm{others} &\sim \phi_{d}\bigl({\bf z}_{i};\mu_{g},\sigma_{g}^{2}I_{d}\bigr) \cdot P\bigl(Y\mid Z,X,\beta\bigr),\quad &&i=1:n, \\ &= MVN(\bf z_i ; \mu_g , \sigma_g^2 I_d) \cdot P\bigl(Y\mid Z,X,\beta\bigr),\quad \tag{1} \\ \beta\mid \bf{Z},\mathrm{others} &\sim \phi_{p}\Bigl(\beta;\xi,\Psi\Bigr) \cdot P\Bigl({Y}\mid\bf {Z},\bf {X},\beta\Bigr), \\ &= MVN(\beta ; \xi, \Psi) \cdot P\Bigl({Y}\mid\bf {Z},\bf {X},\beta\Bigr), \tag{2} \\ \lambda\mid{\mathrm{others}} &\sim {Dirichlet\Big (m + \nu \Big)} \\ \mu_{g}\mid\mathrm{others} &\sim MVN_{d}\left(\frac{m_{g}\bar z_{g}}{m_{g}+\sigma_{g}^{2}/\omega^{2}},\,\frac{\sigma_{g}^{2}}{m_{g}+\sigma_{g}^{2}/\omega^{2}} \cdot I\right),\quad &&g=1:G, \\ \sigma_{g}^{2}\mid\mathrm{others} &\sim \left(\sigma_{0}^{2}+d s_{g}^{2}\right) \cdot \mathrm{Inv-}\chi^2_{\alpha + m_s d}, &&g=1:G, \\ P\Bigl(K_{i}=g \bigg | \mathrm{others}\Bigr) &= \frac{\lambda_{g}\phi_{d}\Bigl(z_{i};\mu_{g},\;\sigma_{g}^{2} \cdot I_{d}\Bigr)} {\sum_{r=1}^{G}\lambda_{r}\phi_{d}\Bigl(z_{i};\mu_{r}, \; \sigma_{r}^{2} \cdot I_{d}\Bigr)},\quad &&g=1:G. \end{align}\] $$

  • \(K_i = g\): the membership of node \(i\)
  • \(MVN(\bf z_i ; \mu_g , \sigma_g^2 I_d)\): normal for membership \(g\)
  • \(P\bigl(Y\mid Z,X,\beta\bigr)\): we cannot calculate the conditional posterior distribution analytically.
    • for same reason, for (1) and (2), use MH algorithm
  • \(m_g = \sum\limits^n_{i=1}I(K_i = g)\)
  • \(\bar z_g\): mean of latent positions that belongs to cluster \(g\)
  • \(d\): dimension
  • \(s_g^2 = \frac{1}{d}\sum\limits_{i=1}^n (z_i - \mu_g) ' (z_i - \mu_g) I(K_i = g)\)

※ Steps.

  1. MH 스텝 이용해서 \(Z_{t+1}\) 업데이트 1. proposal \(2_{i}^{\ast}\sim\left|l\right|/|\bigvee_{i}(\Sigma_{i},(\hat{L}_{i}^{\ast}|_{i})\), \(g=1, \cdots, G\) 2. accept \(Z_i^\ast\) as the i-th element of \(z_{t+1}\) with probability \(\frac{P\big(\mathbf{V}|\mathbf{Z}^{*},\mathbf{X},\beta_{t}\big)\phi_{d}\big(\mathbf{Z}_{i}^{*},\mu K_{i},\sigma_{K}^{2}|_{d}\big)}{P\big(\mathbf{V}|\mathbf{Z}_{t},\mathbf{X},\beta_{t}\big)\phi_{d}\big(\mathbf{Z}_{i i};\mu K_{i},\sigma_{K}^{2}|_{d}\big)}\)

  2. MH 스텝 이용해서 \(\beta_{t+1}\) 업데이트 1. \(2_{i}^{\ast}\sim\left|l\right|/|\bigvee_{i}(\Sigma_{i},(\hat{L}_{i}^{\ast}|_{i})\), \(g=1, \cdots, G\) 2. accept \(Z_i^\ast\) as the i-th element of \(z_{t+1}\) with probability \(\frac{{\cal P}\big(\mit{W}\lbrack\mathbf{Z}_{t+1},\mit{X},\beta^{*}\big)\phi_{\rho}\big(\beta^{*};\xi,\mit{\mit\Psi}\big)}{{\cal P}\Big(\mit{\bf V}\lbrack\Z_{t+1},\mit{\bf X},\beta_{t}\big)\phi_{\rho}\big(\beta_{t};\xi,\mit{\mit\Psi}\Big)}.\)

  3. Update λ, µg, σ, g, Ki using full conditional posterior distributions

Pros and Cons

  • 장점: 성능이 더 나음
  • 단점: 더 복잡함




7.8.2.2 Identifiability of Positions and Cluster Labels

2개의 identifiability issues

  1. invariant property of distance
  2. label-switching problem
    common problem in a Bayesian Mixture Model

Cluster label does not change the likelihood -> changing the cluster label will make problems for making inferences of individuals in a cluster.

Solution: Minimize, expectation of loss function, which is Bayes risk

Likelihood 에만 의존해서 cluster化 성능 평가하면 문제생김. positions 과 cluster labels 들의 Non-identifiabilities 문제. Likelihood 는 이하에 불변.

  1. latent positions 들의 반사, 회전, translation
  2. cluster 들의 relabeling. 이는 Label switching problem[^cluster 의 label 을 permute 하는 것은 Likelihood 에 변화를 가져오지 않지만, obs 들을 그룹에 넣는 과정에서 우리가 문제를 겪게 됨. Likelihood 는 같지만 label 이 다른 순간 이건 cluster 의 구성이 다른 것과 동일하니까.] 으로 이어짐.

이를 해결하기 위한 방법으로 Minimizing Bayes risk 가 제시.

  1. estimate 되는 Bayes risk4 를 최소화하는 actor 들의 position (i.e., reference point) 탐색
  2. latent position 의 posterior 추출값 (draw), (i.e. 모든 다른 MCMC 샘플들) 를 Procrustes Transform 하고 동일한 Transformation Matrix 를 사용하여, cluster mean 와 Cov 를 transform
  3. Estimate 된 Bayes risk 를 최소화하는 cluster membership probability 을 탐색
  1. 에 대한 계산은 이하와 같다. 이를 통하여 cluster 의 갯수를 정한다. Bayesian estimation - 이하의 equation, 즉 higehest posterior probability 를 가지는 model 을 선택.
$$ \[\begin{array} &P(Y,{\hat{Z}}|G) &= &&\underbrace {\int P(Y|{\hat{Z}},X,\beta)p(\beta)d\beta} _{\substack{\text{integrated likelihood for the logistic regression} \\ \approx BIC_{lr}(\text{logistic regression})}} &&\cdot &&\underbrace {\int P({\hat{Z}}|\theta)p(\theta)d\theta} _{\substack{\text{integrated likelihood for the mixture model} \\ \approx BIC_{mbc}(\text{mixture model})}} \\ BIC &= &&BIC_{lr} &&+ &&BIC_{mbc} \\ &= && \left \{ 2 \log \Big [ P \Big \{ Y \Big | \hat Z , X, \hat \beta ( \hat Z ) \Big \} \Big ] - d_{logit} \log (n_{logit}) \right \} && + && \left\{ 2 \log \Big [ P \Big \{ \hat Z \Big | \hat \theta ( \hat Z ) \Big \} \Big ] - d_{mbc} \log (n) \right \} \end{array}\]

$$

  • \(d_{logit} =\) # of parameters in the logistic regression
  • \(n_{logit} =\) # of ties in data (# of edges)
  • \(d_{mbc} =\) # of parameters in the clustering model