스케일 프리 네트워크

스케일 프리 네트워크

Scale-free Network

정의 1

차수분포파레토 분포랜덤 네트워크무척도 네트워크Scale-free Network라고 한다.

설명

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

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

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

zoomout.gif

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

logloghist.png


  1. Albert. (2002). statistiical mechanics of complex networks. https://doi.org/10.1103/RevModPhys.74.47 ↩︎

  2. Broido. (20109). Scale-free networks are rare. https://doi.org/10.1038/s41467-019-08746-5 ↩︎

댓글