📂그래프이론

스케일 프리 네트워크

정의 ¹

차수분포가 파레토 분포인 랜덤 네트워크를 무척도 네트워크^{scale-free Network}라고 한다.

설명

스케일-프리(SF) 네트워크라는 명명은 파레토 분포가 가지는 무척도성에서 온 말이다. 차수분포로 정의되는 네트워크인만큼 그 분포의 성질을 진하게 물려받은 것이 특징이다. 수식으로 나타내보자면 스케일-프리 네트워크 $G$ 의 노드 $v \in V(G)$ 들의 차수는 어떤 파라미터 $\gamma > 0$ 에 대해 다음과 같이 나타낼 수 있는 것이다. $$ P \left( \deg v = k \right) \sim k^{-\gamma} $$ SF 네트워크는 파레토 분포가 그러하듯 과학계 전반에서 빈번하게 나타나며, 사회나 자연 현상을 묘사하기에 아주 좋은 모델로 알려져있다. 그러나 최근에는 이러한 SF 네트워크 만능주의에 대해 경고하는 논문²이 발표되기도 했으니 주의해야할 것이다.

이의 대표적인 응용은 특정 다이내믹스에서의 기반 구조를 모방하는 것이다. 수많은 실제 데이터에서 유도된만큼 인간관계, 도로망, 생태계 등 수학적으로 보편타당한 구조가 필요할 때 가장 먼저 고려되며 실제로 많이 쓰이기도 한다. SF 네트워크를 인공적으로 생성하는 방법으로는 다음과 같은 모델들이 알려져있다.

• 청-루 적합도 모델
• 바라바시-알버트 모델

다음은 바라바시-알버트 모델로 생성되는 SF 네트워크를 시각화한 것이다.

수식에서 차수분포의 히스토그램은 로그로그 그림을 그렸을 때 직선을 이루어야한다. 다시 말해, $$ p(x) \sim x^{-\gamma} $$ 의 양변에 로그를 취했을 때 $$ \log p (x) = - \gamma \log x $$ 이므로 기울기가 $- \gamma$ 인 직선이 되는 것이다. 실제로 그려보면 다음과 같이 허브 노드가 생기는 영역을 빼고는 뚜렷한 직선을 이루는 것을 확인할 수 있다.