[네트워크이론] Network Assortativity (네트워크 동류성)

 네트워크 구조에는 동류성(Assortativity)이라는 특징이 있다. 동류성은 같은 종류의 사람들끼리 뭉치는 경향을 나타낸다. 

 다음 그림을 보면 쉽게 이해할 수 있다.

 Assortative network(동류성 네트워크)에서는 link를 많이 가진 node 즉, hub는 hub들 끼리 뭉쳐있다(중심부). 또 적은 link를 가진 node들은 적은 link를 가진 node들 끼리 뭉쳐있다(외곽부). 

 Disassortative network(비동류성 네트워크)에서는 link를 많이 가진 node와 link를 적게 가진 node들이 연결되어있다.

 이렇게 Assortativity는 네트워크의 구조를 결정하는 중요한 요소이다. 같은 degree분포의 network 여도 assortativity와 같은 특징들은 다 다를 수 있기 때문에, 정말 같은 구조의 network인지 조사하기 위해선 다양한 특징들을 비교 분석해봐야 한다.

 그럼, Assortativity를 분석하는 방법을 알아보자.

Node 중심 Analysis

 먼저, node 중심적인 Assortativity 분석법을 살펴보자.

 어떤 node i의 이웃이 지닌 degree의 평균치는 다음과 같이 나타낼 수 있다.

---

---

 A_ij 는 node i와 node j가 link를 가지고 있을 때 1의 값을 갖는 행렬이고, N은 node의 개수를 나타낸다. 윗 식은 node i의 이웃이 지닌 degree k_j를 계산한 후, 이웃의 수 k_i로 나누어 평균치를 구한 값이다. 

 한 발자국 더 나아가, 특정 node i가 아닌 degree k를 지닌 node들이 대체로 어떤 degree를 지닌 node들과 접하고 있을까를 분석하기 위해 다음과 같은 특징량도 이용한다.

---

---

 P(k'|k)는 degree k를 지닌 노드 중에서 degree k' 의 이웃이 있을 조건부 확률에 해당하며, 이를 k'에 곱한 값을 모든 k'에 대해 더하면 degree k의 node와 연결된 node들의 degree의 기대값을 나타낸다.

 이제, knn을 이용해서 network가 Assortative인지, Disassortative인지 분석할 수 있다. 다음그림을 보자.

Barabasi network science book  URL: http://networksciencebook.com/chapter/7#measuring-degree

 x축이 degree k, y축이 knn(k)를 나타낸다. Assortative network는 k가 클수록 큰 knn 값을 지니고 있고, Disassortative network 에서는 k가 클수록 작은 knn 값을 지니고 있다. 이는, 네트워크의 동류성을 파악할 수 있는 지표이며, log-log 스케일에서 fitting을 통해 동류성의 정도를 분석한다.

Link 중심 Analysis

 

다음으로 link 중심적인 Assortativity 분석법을 살펴보자.

 어떤 네트워크에서 j개의 link를 가진 node와 k개의 link를 가진 node를 연결하는 link jk를 선택할 확률을 e_jk 라고 하면 다음과 같은 식을 얻을 수 있다.

---

---

 1, 2번째 식의 q_k는 특정 link를 뽑았을 때 link에 연결된 한쪽 끝의 node의 지수(degree, 연결의 개수)가 (k+1)개일 확률을 나타낸다.

 3번째 식은 link 관점과 node관점의 관계를 설명한다. 오른쪽 항의 p_k는 지수가 k인 node가 전체 네트워크에서 차지하는 비율을 나타낸다. (k+1)개인 이유는 선택한 link를 제외한 지수가 k일 확률을 관찰하고자 하기 위함이다.

 q_k는 p_k+1과 k+1에 비례 한다. k+1 지수의 node의 비율이 증가할 수록, k+1이 증가할 수록, link를 선택할 때 한쪽 node가 k+1의 지수를 가질 확률이 비례해서 증가한다. 

 (k+1)p_k+1은 지수 k+1의 기대값이다. <k>는 전체 network에서 지수 k의 기대값을 나타내는 기호로 분자를 normalizing한다.

 e_jk는 network 속에서 어떤 link를 선택했을 때 한쪽 node의 지수가 j, 다른 한쪽 node의 지수가 k일 확률을 나타내는데, network에 어떠한 Assortativitiy(동류성)이 존재하지 않을 때, e_jk는 링크를 뽑았을 때 node의 지수가 j일 확률 q_j와, 지수가 k일 확률 q_k의 곱으로 나타낼 수 있다. q_j와 q_k가 독립적이기 때문이다. 

 하지만, q_j와 q_k가 독립적이지 않은 경우, 즉 지수 j의 노드들과 지수 k의 노드들에 상관관계가 있는 경우는 값이 달라진다. 이는 지수j와 지수k의 상관계수를 통해 그 정도를 나타낼 수 있다. 

 상관계수는 다음과 같이 구한다.

상관계수

---

---

 3번째 줄에서 4번째 줄로 넘어가는 것을 이해하기 위해서는 j와 k의 관계를 알아야 한다. j와 k는 link i를 선택했을 때 양 단의 노드가 지니는 지수를 나타낸다. 고로, 동일 집단 속의 변수이며, k만으로 표현할 수 있다.

 이 식을 실제 network에 적용하여 쉽게 계산하기 위해서 다음과 같은 식을 이용한다.

상관계수 (practical)

---

 

---

 M은 전체 link의 개수를 나타내며, i는 링크 번호를 나타낸다. (i = 1, 2, .... M )

 이 식을 이용해서 모든 link에 대해 순차적으로 j_i, k_i를 대입하여 계산해 나가면 r을 구할 수 있다.

 상관계수 r에 따른 Netwrok의 분류

---

    양수 - Assortative network(동류성 네트워크) 인접한 두 node의 degree가 양의 상관관계

    0     - Neutral network(중립 네트워크) 인접한 두 node의 degree에 상관관계가 없음

    음수 - Disassortative network(비동류성 네트워크) 인접한 두 node의 degree가 음의 상관관계 

---

재미있는 점은 Social network는 주로 Assortative network 구조를, technological and biological network는 주로 disassortative network 구조를 나타낸다는 점이다.

 

M. E. J. Newman "Assortative mixing in networks"(2002)

 real-world networks의 상관계수 r을 살펴보면 상부의 Social network에서는 양의 상관계수가 하부의 Technological and biological network 에서는 음의 상관계수가 나타남을 알 수 있다. 다만, 이렇게 카테고리를 분류하였을 때 모든 상관계수가 공통점을 보인다고 할 수는 없다.

 Newman은 그의 논문*에서 social network에서 지수가 양의 상관을 가지는 이유가 community에 있다는 가설을 제시한다. 커뮤니티의 규모와 성질에 따라 끼리끼리 모여있는 social network 구조가 개인이 지니는 link의 개수에 영향을 주기 때문일 수 있다는 해석이다.  *"Why social networks are different from other types of networks, Phyical revew E 68, 036122(2003)"

 network의 assortativity(동류성)는 다음과 같은 특징과 관련성을 지닌다.

Assortative Network의 특징

---

1. network를 통한 전파

 동류성 network는 비교적 적은 밀도의 link에서도 비교적 큼직하게 응집된 구조를 생성한다. 이러한 구조는 전염병, 정보 같이 network를 통해 전파되는 성질들이 비교적 적은 밀도의 link에서도 큰 영향을 미칠 수 있다는 것을 의미한다.

2. Robustness(강인성)

 동류성 network는 허브끼리 연결되어있다. 그래서 한개의 hub가 사라진다 하여도 전체적 손실을 그렇게 크지 않다. 하지만, 비동류성 network는 hub 하나에 degree가 작은 node들이 달려있다. 그래서 hub가 사라진다면 작은 node들이 분리되며, 구조 전체적으로 큰 손실을 입게된다.

3. Stability(안정성)

 동류성 network는 자극과 섭동(동요)에 안정성을 지닌다. 강인성과도 연관되어 있는 성질이며, 특정 원인에 의해 계 전체가 요동치지 않는 안정성을 지닌다.

4. network diameter(네트워크 반경)

 네트워크 반경은 network 내에서 얼만큼 이동해야 network 전체가 닿을 수 있는지를 나타낸다. 동류성 network에서는 hub는 hub들끼리, 작은 degree의 node들은 작은 애들끼리 모여있기 때문에, hub에서 작은 degree의 node까지의 거리가 비동류성 network에 비해 길다. (비동류성 네트워크는 hub와 작은 degree를 가진 node가 짧은 거리로 연결되어있다.)

 하지만, 평균적인 반경을 생각하자면, 동류성 network는 큼직한 구조를 이루기 때문에 각 node들간의 거리는 비동류성 network에 비해 평균적으로 가깝다. (1번 특징)

---

참고자료

 Assortative mixing in networks, M.E.J. Newman, Physical review letters(2002)

 Network science book by Albert-Laszio Barabasi, URL: networksciencebook.com/chapter/7