[논문소개] 성장하는 네트워크의 시간 의존성

 약 2년간 참여했던 프로젝트가 논문화 되었다. 개인적으로 성장하는 네트워크와 그 분석 방법에 대해 공부할 수 있는 좋은 기회였다. 간단히 설명하자면, 성장하는 network를 시간 의존적이지 않은 보편적 메커니즘을 통해 설명하려는 시도가 어떤 오해를 낳을 수 있는지 고찰한 논문이다.

 네트워크 내에서 node들이 갖는 link의 수의 분포 (degree distribution) 를 그려보면, 멱함수 꼴의 두터운 꼬리를 지닌 분포가 자주 나타난다. 이는 주로 신규 유입된 node가 기존 node와 link를 형성할 확률 (attachment rate) 이 그 node의 link의 수에 비례할 경우 나타날 수 있다고 알려져 있다. 이를 설명하는 model로 바라바시 알베르트 (BA) 모델이 대표적이며, 이 메커니즘을 일컬어 preferential attachment 라고 부른다.

 그래서 degree distribution은 network의 형성 메커니즘을 간접적으로 살펴 보기 위한 지표로 활용되어 왔다. 그리고 최근에 다시 degree distribution이 갖는 멱함수 꼴에 대한 해석을 더 엄밀히 할 필요성이 재조명 되고 있다.

 이 프로젝트는 그 논의의 연장선 상에 있다. Preferential attachment는 보통 고정된 시점에서 논의가 이루어져 왔다. 그런데 이 비율이 시간 의존성을 지닌다면 과연 고정된 시점에서 이루어진 해석이 일반적인 해석이 될 수 있을까? 이는 얼마나 치명적일 수 있을까? 라는 질문이 남는다.

 이 논문에서는 시간 의존적 preferential attachment rate를 지닌 model과 실제 data 분석을 통해 잘못된 해석이 이루어 질 수 있음을 보인다. 분석을 위해 각 시점에서 attachment rate를 추정하고, 비교하는 방법을 이용했는데, model과 실제 data에서 시점에 따라 attachment rate는 복잡한 변화 양상을 보였다. 그리고 한 시점의 분석은 시간이 지나면 전혀 다른 결과의 degree distribution과 attachment rate의 형태로 나타날 수 있다는 것을 확인했다. 즉, 한 시점에서 이루어진 해석을 통해 일반적인 메카니즘을 추정하기에는 무리가 있다는 것을 보였다.

 논문의 많은 부분은 시간 의존성을 지닌 model의 설명에 할애 되었다. BA model의 link의 비례한 attachment rate를 한 거리 확장한 두 거리 내의 link의 수에 비례한 attachment rate를 갖는 model로, 보통 degree를 지칭하는 k에 2를 붙여 k2모델로 명명했다. 모델은 network의 성장에 따른 구조의 변화에 의해 자연스럽게 시간 의존성을 갖는다. 재미있는 점은 초기 BA model 처럼 행동하던 모델이 성장에 따라 전혀 다른 형태로 나타난다는 점이었다. 이를 설명하기 위한 과정이 매니악 하기도 하면서 개인적으로는 재미있는 부분이었다.