[네트워크이론] degree에 따른 attachment rate 구하기

 Barabasi-Albert 모델에서 중요한 것은 Preferential attachment와 Network의 성장이다. 이 규칙을 통해 신규 유입되는 node들은 link의 개수가 많은 node와 연결을 맺을 확률이 높고, 이는 다른 node와 비교했을 시 아주 많은 link를 지닌 node, 즉 Hub들을 만들어낸다.

 하지만, 특정 네트워크에서 이러한 규칙을 조금 더 엄밀히 살펴보기 위해 실제 node들이 연결을 갖는 비율 Attachment rate를 구하는 방법이 있다. 이 Attachment rate가 실제로 node가 지닌 link 수(degree, 관용적으로 k로 표현)에 비례하는가 확인함으로써 특정 네트워크가 지니고 있는 BA 모델의 성질을 확인할 수 있다.

 오늘은 in-degree network에서 Attachment rate를 추정할 수 있는 방법을 소개하려고 한다. network에 있어 degree는 추가적인 정보를 담을 수 있는데 weight와 방향성이다. weight는 연결의 강도를 표현할 때 이용하며, 방향성은 누가 누구에게 연결을 걸었는지 표현할 때 이용한다. 예를 들면 A가 B의 논문을 인용했을 때 AーB 가 아닌 A→B로 표현하는 것이다. 이러한 방향성을 지닌 network를 Directed network라고 부르며, 이러한 네트워크의 In-degree는 특정 node에 Attach 한 node의 개수를 의미한다. 즉, Attachment rate는 In-degree와 관련이 있다.

 In-degree network의 Attachment rate를 추정하는 대표적인 3가지 방법을 소개한다.

Jeong's method

---

 처음 소개할 방법은 KAIST 대학의 정하웅 교수님이 고안한 방법으로 Jeong's method로 불리운다. 가장 간단한 방법으로, 특정 시간 영역(T2)에 유입된 node가 기존 시간영역(T1)의 node에 연결된 비율을 통해 Attachment rate를 구한다. 이 때 degree k 별로 Attachment rate(A)를 구하는 방법을 통해 k와 A의 관계를 밝힌다.

 

A_k : degree k 인 node에 신규 node가 연결을 맺는 비율

N : 기존 node의 개수

n_k : 기존 node 중 degree k 인 node의 개수

m : 총 신규 link의 수

m_k : 신규 link 중 degree k 인 node에 연결된 link의 수

 이 식은 다음 식으로부터 유추할 수 있다.

 추가되는 link 들 중에서 기존 network의 degree k 와 연결되는 link의 비율은 Attachment rate에 degree k 인 node의 비율을 곱해줌으로써 구할 수 있다. 단순히 m_k/m 이 Attachment rate가 아닌 이유는, degree k 인 node의 개수가 각각 다르기 때문.

 Jeong's method는 직관적이고 유용하지만, 시간 영역을 어떻게 설정하는가에 따라 불안정한 결과값을 지닌다. 이 분석 방법에서는 T1이 고정적이다. 그래서 T2를 넓게 잡으면 잡을 수록, 그 사이에 실제로는 변화하고 있는 T1 내의 node들의 degree 변화율이 무시되어, Attachment rate에 bias가 형성된다. 반대로 T2를 좁게 잡으면 bias는 감소하지만, 실제 분석에 이용되는 node들의 개수가 줄어드므로 variance는 증가한다. bias-variance trade-off !

---

Newman's method

---

 Newman은 이를 잘게 나눈 time-step에서의 histogram을 조합함으로 해결한다.

식을 풀어 말하자면, 가능한 작은 window로 time-step을 구성하고, 각 time-step마다 Jeong's method로 Attachment를 구하여, weight를 곱한 뒤 더하는 방법이다. weight로써 m(t), 그 시간대에 새로이 추가된 link의 개수를 곱하여 당시 추정된 Attachment rate에 가중치를 둔다. C는 normalizing 하기 위한 상수이다.

 이 방식은 낮은 degree k 에서는 Attachment rate를 잘 추정하지만, degree k 가 높아지면 Attachment rate가 낮게 평가되는 경향이 있다. 이점은 corrected Newman's method에서 설명!

---

Corrected Newman's method

---

Newman's method의 문제점은 모든 영역의 degree k 가 네트워크의 성장에 균등히 존재한다는 암묵적 해석에 있다. 

 Network는 사실 시간이 흐름에 따라 점점 성장한다. 그래서 낮은 degree k 는 네트워크의 초반부터 줄곧 존재하고, 높은 degree k는 네트워크 후반부터 잠시 등장한다. 당연히 높은 영역대의 degree k에 대한 weight가 더 낮게 책정된다.

 그래서 사실은 degree k 별로 weight의 총 합을 나누어 줘야, 이러한 부당한 편향을 없앨 수 있었던 것이다.

 분모에 w_k가 없을 경우를 생각해보자 낮은 degree k에서는 w_k(신규 link의 개수)가 낮은 t 영역대부터 착실히 쌓인다. 하지만 높은 degree k는 높은 t 영역대부터 w_k가 쌓이기 시작한다. 당연히 높은 degree k 에서 Attachment rate가 낮게 평가될 수 밖에 없다. 고로, degree k 에서의 w_k(t)의 총합을 각각의 degree k 에 대해 나누어 줌으로써 이러한 편향을 제거한다.

---

 이 내용은 다음 논문을 참조해서 작성했다. 

"PAFit: A Statistical Method for Measuring Preferential Attachment in Temporal Complex Networks", Thong Pham et al., PloS one, 2015

 정작 논문에서 사용한 PAFit 방법은 최적 해를 구하는 방식인데, 어려워서 보류했다..!

 실제 분석 결과와 code는 다음 글 참조.

[네트워크이론] degree에 따른 attachment rate 구하기 - 실전편   https://mons1220.tistory.com/188