[논문소개] Scale-Free Networks Generated by Random Walkers

 바라바시 선생님이 척도불변성을 지닌 네트워크의 성질을 네트워크의 확장성과, 새로운 노드는 이미 연결을 많이 가지고 있는 노드에 연결되려는 성질(Preferential attachment)로 설명한 논문 Emergence of Scaling in Random Networks (http://mons1220.tistory.com/47)을 읽고 한동안 연결이 지니는 선호성에 대해 생각해보며 가진 궁금증이 있었다.

 Preferential attachment 는 마치 모든 노드들이 얼마나 연결을 지니고 있는지 미리 알고 있는 것처럼 느껴진다. 누가 얼마나 연결을 지니고 있는지 미리 알고 있고, 그에 따른 확률로 새로운 연결이 생성된다. 연구실에서 네트워크 연구를 하고 있는 친구와 나는 이러한 결정론적인 시각이, 모든 정보가 주어지지 않는 인간세상을 반영할 수 있을까에 의문을 가지고, 우연한 만남과 그로부터 생기는 추가적인 네트워크를 통해 실제 사람들이 만들어내는 사회 연결망의 구성이 어떠한지에 대해 생각해 보고 있었다.

 그리고 논문들은 검색하던 중, 우리의 고민과 바라바시 모델의 연결다리가 되어주는 논문을 찾았다. 바로 이번에 소개할 논문이다.

 Scale-Free Networks Generated by Random Walkers, Jari Saramaki & Kimmo Kaski

 바라바시 선생님의 선호성을 지니는 네트워크는 한 노드가 지닌 연결의 개수가 새로운 연결이 생길 확률과 비례한다. 이를 랜덤워크를 통해 생각해볼 수 있다. 랜덤워크는 무작위적으로 네트워크를 통해 한 노드에서 다른 노드로 이동하는 것을 뜻하는데, 아주 오래 걷다보면 특정 노드에 있을 확률은 그 노드가 지닌 연결의 개수에 비례하게 된다. 그리고 이는 바라바시 모델이 지니는 새로운 연결이 생길 확률과 같다. 즉, 아주 오랫동안 네트워크를 무작위적으로 행보하다보면, 모든 노드들이 지니는 연결의 개수에 대한 파악이 가능하고, 확실하게 연결을 많이 가지고 있는 노드에게 연결할 수 있게 되는 것이다.

 하지만 이 논문의 저자들은 짧은 길이의 랜덤워크, 즉 1~2회 정도의 탐색만이 가능할 때 어떻게 될까에 주목하고 있다. 실제로 우리가 무한히 네트워크망을 활보하며, 모든 정보를 얻을 수 없기에.. 더 현실적인 탐색 모형을 제시한 것이다.

수학적 해석

 먼저, A라는 노드에 우연히 연결이 생길 확률은 전체 노드의 개수가 N개 일 때 다음과 같다.

그리고, A라는 노드에 연결이 생기고 나서, A의 이웃 B에게 연결이 생길 확률은 베이즈 정리를 통해 다음과 같이 나타낼 수 있고, 이를 통해 노드 B에 연결이 생길 확률 P(B)를 나타낼 수 있다.

 여기서 사건 B가 일어나고 나서 A가 일어날 확률은 랜덤 워크를 통해 사건이 일어나기 때문에, B가 가진 연결의 개수에 반비례 하게 된다. 연결이 3개가 있으면, 그 중 A는 한개의 연결에 속해있으니 1/3의 확률이 되는 것이다. 반대로 사건 A가 일어나고 나서 B가 일어날 확률은 A가 가진 연결의 개수에 반비례 하게 된다. 이를 식으로 나타내면 다음과 같다.

 이를 윗 식에 대입하면 노드 B에 연결이 생길 확률은

 가 된다. 이는 B의 이웃 노드 C에 연결이 생길 확률도 똑같이 적용되는데, 

와 같이, B의 노드의 연결개수 k_B가 상쇄되어 진다. 똑같이 이웃의 이웃으로 확장해 나가도 마찬가지로, 랜덤워크의 길이와는 상관없이 첫 노드가 지니는 연결의 개수와 해당 노드가 지니는 연결의 개수의 비의 확률로 나타내어진다고 한다. (B가 아닌 다른 노드를 통해 C로 가는 확률은 생략되어져있다. 이 확률이 무시된다함은 )

 그리고, 노드 A가 지니는 연결의 개수 k_A의 기대값은 A가 우연히 선택되기 때문에 네트워크의 모든 연결 개수의 평균값을 가진다. 그래서, 특정 노드에 연결이 생길 확률은

짠! 바라바시 모델의 연결이 생길 확률로 둔갑하게 된다. 그래서 랜덤 워크의 길이 l에 상관없이 바라바시모델과 같은 차수 분포(노드가 지니는 연결의 수와 그러한 노드의 개수를 나타낸 분포)가 나타난다고 한다.

 실제, l = 1, 랜덤워크 스탭을 1로 설정하였을 때의 실험결과와 바라바시 차수 분포를 비교한 결과가 다음 그림이다.

실선이 바라바시 모델의 차수분포를 나타낸 선이고, 동그라미 네모 세모 마름모는 랜덤워크 1스텝에서의 시뮬레이션 결과이다. 새로 추가되는 노드가 2개, 4개, 8개, 16개의 연결을 지닐 때로 나누어 모양을 표시하였다. 바라바시 차수분포와 일치하는 결과가 나타남을 알 수 있다.

 자, 그럼 바라바시 모델과 뭐가 다른가 하는 이야기가 되는데, 클러스터 계수가 달라진다. 클러스터 계수는 나의 이웃과 이웃이 서로 이웃인 모양에 관계된다. 즉, 차수분포는 같되, 애들이 뭉쳐져있는 모양은 다르다는 이야기다. 바라바시 모델은 중앙집중적인 모습을 보이는데 반해 이 모델은 조금 더 클러스터 계수가 높은, 즉 이웃과 이웃이 서로 이웃인 3각형 형태가 많이 나타나게 된다. 그리고, 이러한 클러스터 계수는 랜덤워크의 길이가 길면 길수록 바라바시 모델의 클러스터 게수와 일치해 나가는 것을 시뮬레이션으로 보였다.

 실제로 네트워크 모양이 나왔으면 좋았을텐데, 개수가 10의 6승이어서 그래프화 하기에는 무리가 있었던걸까(2008년도 논문) 네트워크의 모습을 볼 수는 없었다.. 그래서 내가 만들어본 네트워크로 대신해 본다.

 노드 개수 1000개(컴퓨터 속도상 10의 6승까지는 그릴 수 없었다...), 새로운 노드가 지니는 연결의 개수 2개, 랜덤워크 시행횟수 1회의 네트워크(빨강)과 기존 바라바시 모델의 비교 그림이다. 완전 중앙 집중이 이루어진 바라바시 모델보다는 좀 더 군데군데 군집화 되어있는 모양임을 알 수 있다. 여기서 클러스터 계수가 차이가 나게 되나보다. 

결론

 랜덤워크 베이스의 무향네트워크의 성장 메커니즘을 통해 스케일 프리 네트워크를 구현한 것이 이 연구의 결과이다. 그리고 랜덤워크의 스텝 수는 차수 분포의 지수 -3에 영향을 끼치지 않으며, 심지어 스탭수 1의 랜덤워크만으로도 거듭제곱 분포의 차수분포가 나타남을 확인하였다. 이러한 네트워크는 클러스터 계수에서 차이를 보이며, 랜덤워크가 충분히 긴 스탭일 때 바라바시 모델에 근접함을 확인하였다.