[논문 리뷰] Latent Space Approaches to Social Network Analysis

N명의 사람들이 서로 상호작용하는 SNS가 있다고 가정하자. 서로 친한 관계의 사람들은 친구 관계로 연결되어 있을 것이고, 이를 Node와 Edge로 이루어진 Network data의 형태로 표현할 수 있을 것이다.

이렇게 만들어진 네트워크는 N이 커질수록 매우 복잡해질 것이다. 즉, SNS에 참여하는 사람들이 많아질수록 어떤 사람들이 서로 친구이고 어떤 공통점이 있는지 등의 네트워크에서 나올 수 있는 정보를 시각적으로 발견하기가 불가능에 가까워진다. 이런 경우, 네트워크에 어떤 통계 모형을 가정하여 복잡한 관계로부터 의미 있는 정보를 추출할 수 있다.

 

그렇다면 복잡한 네트워크로부터 어떻게 정보를 가져올 수 있을까? 논문에서는 서로 다른 사람들 사이의 "사회적 거리"를 가지고 친구가 될 확률을 모델링한다. 예를 들어 A와 B의 사회적 거리가 가까우면 친구가 될 확률이 높고, 사회적 거리가 멀면 친구가 될 확률이 낮아질 것이다. 사회적 거리를 측정하기 위해서는 네트워크에 존재하는 사람들, 즉 노드들을 임의의 차원을 가진 "사회적 공간"으로 옮겨주어야 일반적으로 정의하는 거리를 측정할 수 있다. 즉, 각각의 사람들에게 사회적 공간에서의 좌표를 부여함으로써 우리가 흔히 사용하는 유클리드 거리 등을 계산할 수 있도록 만들어 주는 것이다.

---

이제부터 본격적으로 논문에서 제시하는 모형을 살펴보고자 한다.

 

(1) Distance model

 

$ logit(y_{ij} = 1 \mid z_i, z_j, x_{ij}, \alpha, \beta) = \alpha + \beta^{T}x_{ij} - |z_i - z_j| $

 

논문에서 가장 먼저 제시된 모형은 서로 다른 노드 사이의 유클리드 거리를 가정한 모형이다. $z_i$와 $z_j$는 각각 사회적 공간에 투영된 노드 i와 노드 j의 좌표를 의미한다. $x_{ij}$는 노드에 대한 공변량(성별, 연령 등 노드에 대한 정보)을 의미하며, $\beta$는 이에 대응되는 parameter이다. 마지막으로 $\alpha$는 일종의 intercept term으로 해석할 수 있다. 만약 공변량을 고려하지 않고, 방향이 존재하지 않는 그래프를 가정한다면 모형을 다음과 같이 단순화할 수 있다.

 

$ logit(y_{ij} = 1 \mid z_i, z_j, \alpha) = \alpha + |z_i - z_j|$

 

network model에서 intercept $\alpha$는 네트워크의 밀도를 의미한다. 따라서 위의 모형에서의 distance term에 의한 효과는 밀도에 의한 효과를 제한하였을 때의 효과로 해석할 수 있다. 사회적 공간 Z의 차원은 다변량정규분포를 가정하며, 2차원부터 임의의 p차원까지 부여할 수 있다. 다만 Z의 차원이 2차원일 때 사회적 공간에 대한 해석이 가장 편하기 때문에 주로 이변량 정규분포를 가정한다.

 

Distance model은 소셜네트워크의 특징 중 하나인 triangle effect를 잘 반영하는 모형이다. 예를 들어 노드 i와 노드 j가 연결되어 있고, 노드 j와 노드 k가 연결되어 있다면 노드 i와 노드 k의 사회적 거리는 가까울 가능성이 높다. 한 마디로 "친구의 친구는 친구가 되기 쉽다."라고 말할 수 있다.

 

위에서 언급한 방향이 존재하지 않는 그래프에 대해 부연설명하자면, 두 노드 사이의 관계가 일방적이지 않고 서로 동등하다는 것으로 이해할 수 있다. SNS의 예를 들면 인스타그램은 팔로워와 팔로잉이 있고, 내가 어떤 계정을 팔로우한다고 해서 그 계정이 나를 반드시 팔로우하지는 않는다. 따라서 인스타그램에서의 관계는 방향이 존재하는 관계라고 할 수 있다. 만약 두 계정이 서로 팔로우하는 경우만 존재한다면 누가 누구를 팔로우하는지에 대한 정보는 더 이상 중요하지 않기 때문에 두 계정 사이에는 서로 연결되었다는 정보 하나만 존재한다. 이 경우 두 계정 사이의 관계에는 방향이 존재하지 않는다.

 

 

(2) Projection model

 

Distance model에서는 각 노드에 부여된 좌표 $z_i, z_j$사이의 거리를 정의하여 두 노드 사이에 연결이 생길 확률을 모델링하였다. 만약 $z_i$와 $z_j$가 좌표가 아니라 p차원 벡터라고 가정한다면 두 벡터의 방향이 가까운 정도를 계산하여 distance term을 대체할 수 있다. 

 

$ logit(y_{ij} = 1 \mid z_i, z_j, \alpha) = \alpha + \dfrac{z_i^{T}z_j}{|z_j|}$

 

위의 식에서 $\frac{z_i^{T}z_j}{|z_j|}$는 $z_i$ vector를 $z_j$ vector에 투영(Projection) 한 것이다. 즉, $z_i$가 $z_j$와 얼마나 유사한지를 측정하는 항으로 볼 수 있다.

---

다음은 모형에 포함된 parameter를 추정하는 방법을 소개할 것이다.

 

Metropolis-Hastings algorithm

 

Metropolis-Hastings algorithm(이하 MH 알고리즘)은 가장 널리 알려진 MCMC 알고리즘이다. 논문에서는 다음과 같이 sampling 과정을 제시하였다.

 

1. Identify an MLE $\widehat{Z}$ of Z, centered at the origin, by direct maximization of the likelihood.
2. Using $Z_0 = \widehat{Z}$ as a starting value, construct a Markov chain over model parameters as follows:
   1. Sample a proposal $Z^{'}$ from $J(Z \mid Z_{t-1})$, a symmetric proposal distribution.
   2. Accept $Z^{'}$ as $Z_t$ with probability $\frac{p(Y \mid Z^{'}, \alpha_{t-1}, \beta_{t-1}, X)}{p(Y \mid Z_{t-1}, \alpha_{t-1}, \beta_{t-1}, X)} \frac{\pi(Z^{'})}{\pi(Z_{t-1})}$;
      otherwise, set $Z_t = Z_{t-1}$
   3. Store $\tilde{Z}_{t} = argmin_{TZ_k} tr(\widehat{Z} - TZ_t)^{T}(\widehat{Z} - TZ_t)$
3. Update $\alpha$ and $\beta$ with Metropolis-Hastings algorithm

논문에서는 Z를 update 하는 과정만 자세하게 설명하였지만 $\alpha$와 $\beta$ 역시 이전 시점의 다른 파라미터들이 주어졌다고 가정하고 값을 update 할 수 있다.

 

위의 sampling 과정을 통해 Z에 대한 샘플을 구할 수 있지만, 이를 일반적인 bayesian inference에서 하는 것처럼 평균을 구하여 사용하는 것은 적절하지 않다. 그 이유는 각 노드 사이의 거리는 유지되더라도 좌표는 변할 수 있기 때문인데, 서로 다른 두 점 사이의 직선의 길이만 동일하다면 2차원 평면 위의 어느 지점에 두 점을 찍어도 거리는 동일하게 유지할 수 있음을 생각하면 어렵지 않게 이해할 수 있을 것이다. 우리가 관심 있는 것은 두 점 사이의 거리이지만 동일한 거리를 가지는 두 점이라고 할지라도 sampling 과정을 거치면서 좌표가 변화할 수 있기 때문에 Z에 대한 sampling을 끝마친 후 Z에 대한 MAP(Maximum A Prior)를 구하여 해당 값을 기준으로 Procrustes matching을 수행하여야 한다. Procrustes matching을 하는 이유는 MAP를 기준으로 다른 Z들을 "돌려"줌으로써 Z 내의 노드들의 좌표가 동일 좌표계를 기준으로 정렬되도록 만들기 위함이다.

---

Practice

 

latentnet 은 Latent space model을 R로 구현한 패키지이다. 패키지의 ergmm function을 사용하여 네트워크 데이터를 가지고 latent space model을 적합시킬 수 있다.  

---

Discussion

 

이 게시글에서는 소셜 네트워크 분석을 위한 유용한 모형 중 하나인 latent space model을 제안한 논문인 "Latent space approaches to social network analysis"에 대한 리뷰를 진행하였다. 네트워크에 내재된 정보를 추출하기 위해 네트워크를 latent space에 투영하고, latent space를 이용하여 각 노드끼리의 관계까지 시각화할 수 있다는 점에서 활용하기 매우 좋은 모형이다. 다만 현재 노드의 좌표 값을 update 하기 위해 다른 노드들에 대한 좌표 정보와 파라미터 정보가 모두 주어져야 하기 때문에 네트워크의 크기가 커질수록 계산하는 데 걸리는 시간이 크게 증가한다는 단점이 있다. 특히 노드의 수가 매우 많은 반면 서로 연결된 노드는 적은 sparse network라면 하나의 노드에 대한 latent position을 구하기 위해 다른 모든 노드의 위치 정보를 활용하는 것은 비효율적일 것이다. 

 

이후에는 Latent space model을 활용한 모형과 Latent space model의 한계점을 극복한 모형에 대한 논문들을 찾아서 읽은 후 이에 대한 리뷰를 진행할 것이다.

 

 

Reference

Hoff, P. D., Raftery, A. E., & Handcock, M. S. (2002). Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460), 1090-1098.

https://www.tandfonline.com/doi/abs/10.1198/016214502388618906

Latent Space Approaches to Social Network Analysis