[네트워크이론] Local assortativeness

예전 네트워크 동류성(Assortativity), 특히 Degree 동류성을 다뤘던 적이 있다. 

 

오늘은 M. Piraveenan, M. Prokopenko, A. Y. Zomaya 의 논문 'Local assortativeness in scale-free networks'을 토대로 지역적인 assortativity, 더 정확하게 말하자면 각각의 node가 전체 assortativity에 기여하는 정도를 정량화 하는 방법을 정리해보려 한다.

---

먼저, 총 network의 assortativity를 구하는 방법부터 복습.

 

Degree assortativity는 링크 양단의 node의 link 수 간의 상관계수이다. 이 때 상관계수를 살펴볼 link 수로는 두 node 사이를 연결한 링크를 제외한 $k = Degree - 1$ 값을 이용하는데 이를 'remaining degree' 라고 부른다.

 

Remaining degree 간의 상관계수는 pearson 상관계수를 통해 구할 수 있다.

 

$r= \frac{Cov(J, K)}{\sqrt{V(J)V(K)}} = \frac{Cov(J, K)}{\sigma^{2}_{q}}$

 

이 때, $J$와 $K$는 각각 링크 양단의 remaining degree를 나타낸다. 식의 분모는 remaining degree 분포의 분산 값을 나타낸다.

 

$J$와 $K$의 공분산은 다음과 같이 나타낼 수 있다.

 

$Cov(J, K) = E(JK) - E(J)E(K) = \sum_{jk} jke_{jk} - \sum_{j} jq(j) \sum_{k} kq(k)$

 

여기서 $e_{jk}$ 는 무작위로 고른 link의 양 끝단의 node의 remaining degree 값이 $j$와 $k$일 확률이고, $q(k)$는 remaining degree의 확률분포를 나타낸다.

 

참고로 $q(k) = \frac{(k+1)p(k+1)}{\sum_{i} ip(i)}$ 인데, 이 때 $p(i)$는 degree 의 확률 분포이다. $ip(i)$는 임의로 선택한 link를 통해 degree가 $i$인 node를 만날 확률을 나타내는데, $q(k)$는 remaining degree가 $k$, 즉 degree가 $k+1$인 node가 있을 확률을 나타낸다.

 

정리하면, 다음과 같다 ($\sigma_{q}$ : $q$의 표준편차, $\mu_{q}$ : $q$의 평균).

 

$r = \frac{1}{\sigma^{2}_{q}} \left[ \sum_{jk} jk(e_{jk} - q(j)q(k)) \right]$

    $ = \frac{1}{\sigma^{2}_{q}} \left[ \left( \sum_{jk} jke_{jk} \right) - \mu^{2}_{q} \right]$

 

---

Local assortativity는 총 assortativity $r$에 각 node가 기여하는 정도를 추려낸 값이다.

 

네트워크 내부의 링크의 숫자를 $M$이라고 하였을 때, 링크를 통해 node로 접근하는 방법은 $2M$의 경우의 수를 갖는다 (링크 양단에 node가 있으므로). 즉 어떤 링크 양단에 $a$와 $b$라는 node가 있다면, 이 링크는 $a$로 접근하는데 한번, $b$로 접근하는데 한번 사용되는 샘이다.

 

그렇다면 특정 remaining degree $j$, $k$가 양단에 있는 하나의 link가 assortativity의 $\sum_{jk} jke_{jk}$ 항에 대해 갖는 기여도는 $jk/2M$ 이라고 할 수 있다. 그리고, 이를 remaining degree $j$를 지닌 node에 대해 합산해보면 다음과 같다.

 

$\alpha = \frac{jk_{1}}{2M} + \frac{jk_{2}}{2M} + \cdots + \frac{jk_{j+1}}{2M} = \frac{j}{2M} \sum_{i=1}^{j+1} k_{i}$

 

다음으로는 assortativity의 마이너스 항 $\mu^{2}_{q}$에 대한 기여도를 살펴보자. 위와 마찬가지로 하나의 링크는 $1/2M$이라고 할 수 있는데, remaining degree $j$인 node는 $j+1$개의 link를 지니므로 기여도를 합산하면 다음과 같다.

 

$\beta = (j+1) \frac{\mu^{2}_{q}}{2M}$

 

위에서 구한 $\alpha$와 $\beta$를 이용해서 degree가 j인 하나의 node가 기여하는 assortativity의 정도를 나타내보면 다음과 같다.

 

$\rho = \frac{\alpha - \beta}{\sigma^{2}_{q}}$

 

이것이 하나의 node에 대한 local assortativity의 정의이며, 총 assortativity는 local assortativity의 합으로 나타낼 수 있다. 

 

$r = \sum_{i=1}^{N} \rho_{i}$

---

Local assortativity는 하나의 node에 대한 기여도이므로, node를 어떻게 그룹짓는가에 따라서, 그 그룹이 전체 assortativity에 갖는 영향력을 가늠해볼 수 있다.

 

이 논문에서는 degree가 같은 node의 집단으로 local assortativity의 평균 값을 구하여, 전체 network 중 node의 size에 따른 assortativity의 기여도를 분석한다.

 

먼저 scale-free network, 즉, degree distribution이 heavy-tail로 나타나는, degree의 이질성이 큰 network에서는 그 network의 총 assortativity와는 상관 없이 지역적으로 disassortative한 node들이 다수 발생한다. (내 의견: 이는 scale-free network의 hub와 연결되면서 자연스럽게 발생한 disassortativeness로 보여진다)

 

또한 assortative 와 disassortative network에서는 매우 큰 giant hub가 생성되기 힘들다고 한다 (non-assortativeness 여야 가능). 이는 assortativeness는 link를 많이 지닌 Hub들끼리 연결되어야 하고,  disassortativeness는 다수의 독립된 hub들을 만들어야 하므로, 소수의 Giant Hub의 생성을 억제하기 때문이다. (Giant hub를 포함한 network는 hub에 대한 공격에 특히 취약하다)

 

실제 network를 대상으로 한 결과는 기존 assortativity의 정의 보다 더 깊은 정보를 제공한다. 예를들어, disassortative network로 알려진, biological (& foodweb) network에서도 degree가 큰 hub 영역에서는 assortativeness가 확인된다. 즉, 비교적 degree가 낮은 영역에서는 disassortative한, 즉, local hub와 peripheral nodes가 연결되어 있는 조각 구조(fragments)가 형성되어 있지만, 높은 degree 영역에서는 이들 사이에서 묶인  Assortativeness한 연결들이 형성되어 있다는 설명이다.

 

저자는 이러한 이질적 local assortativity의 형성이 initial phase와 mature phase의 성장 패턴에 기인한다고 주장하는데, 무척 흥미롭다. 즉 초기 node가 유입되고 link가 자유롭게 형성되는 시기에는 지역적으로 hub와 주변부 node들이 결합한 network 조각들을 형성하는데 (inital phase), 점차 node의 생성에 제약이 생기고 network 전반의 목표가 조정되기 시작하면 (mature phase), 조정에 들어가는 비용 측면에서 node보다 값싼 link에 조정이 발생하고, 이러한 조정이 fragment들을 묶으며 assortativeness를 만들어낸다는 설명이다. 

 

한편, 인터넷 망에서는 assortativeness가 전혀 확인되지 않는다. 저자는 Internet은 고정적인 목표(연결 속도?)를 가지고 빠른 속도로 성장한 network라는 점을 강조하는데, 이는 biological 또는 foodweb network가 변화하는 제약과 목표라는 환경 속에서 점진적으로 진화한 (fine-tuning) network라는 점과 상반되어 있다는 점을 조명한다. 또한, Internet이 아직 initial phase에 있으며, mature phase로 진입할 가능성에 대해서도 이야기 하는데, 그렇게 된다면 현재의 network 조각들 간에 assortativeness가 형성되는, 즉, hub에 대한 공격에 강인한 네트워크 망으로 성장할 수 있다는 설명이다.

 

Social network로 유명한 citation network에서는 disassortativeness한 구간이 잘 나타나지 않고, 대개 assortativeness하다. 이에 대해서 저자는 initial phase, 즉, network의 fragment가 형성이 활발하지 못한 상태에서 mature단계로 성장한 것이라는 추측을 내린다. 

---

종합하자면, local assortativeness는 기존 assortativity를 더 다양한 스펙트럼으로 관찰할 수 있게 해준다. 사실, assortativity라는 것이 network에 대해 단일 값으로 결정된다는 점, 그것도 선형 관계만 취급한다는 점에서 모호한 해석을 내릴 수 밖에 없는 형태의 상관관계들이 다수 존재했었다.

 

Local assortativity는 총 assortativity에 대한 기여도를 scale별로, 지역(모듈구조)별로 도출할 수 있다는 점에서, 한발자국 더 나아간 분석이 가능케 해준다.