네트워크 만들기와 꼬리의 종류: 척도 없는 네트워크 인터랙티브 데모

극단적인 좁은 세상ultra-small world

복습: (그냥) 좁은 세상(small-world) 성질. 한 노드에서 출발해 링크를 따라 층층이 퍼져 나가면, 각 층의 노드 수가 대략 $\langle k\rangle$ 배씩 늘어난다. 따라서

\begin{gathered}N\sim\sum_{i=0}^{l_{\mathrm{max}}}\langle k\rangle^{i}=\frac{\langle k\rangle^{l_{\mathrm{max}}+1}-1}{\langle k\rangle-1}\sim\langle k\rangle^{l_{\mathrm{max}}}\\ \Rightarrow\quad\langle l\rangle\sim l_{\mathrm{max}}\sim\log_{\langle k\rangle}N\propto\ln N\end{gathered}

이다. 척도 없는 네트워크는 더 좁은 세상이다. 허브가 멀리 떨어진 노드들을 지름길처럼 이어 주기 때문이다.

\langle d\rangle\sim\begin{cases}\mathrm{const} & \gamma=2\\ \ln\ln N & 2<\gamma<3\\ \dfrac{\ln N}{\ln\ln N} & \gamma=3\\ \ln N & \gamma>3\end{cases}

오른쪽 데모는 노드 수를 300개부터 3만 개까지 늘려 가며 네트워크를 만들고, 무작위로 고른 출발점들에서 너비 우선 탐색(BFS)으로 평균 거리를 잰다. $N$ 이 100배 커지는 동안 거리가 얼마나 자라는지 비교해 보자.

γ = 2.2γ = 2.6γ = 3.5무작위 네트워크

모든 네트워크의 평균 링크수는 4이고, 가장 큰 연결 덩어리 안에서 거리를 잽니다.

링크수 지수의 역할the role of the degree exponent

구간	〈k〉	〈k²〉	〈d〉
γ < 2: 이례적인 영역	발산	발산
γ = 2 (k_max ~ N)			const
2 < γ < 3: 척도 없는 영역	유한	발산	ln ln N
γ = 3			ln N/ln ln N
γ > 3: 무작위 네트워크 영역	유한	유한	ln N/ln〈k〉

$\gamma < 2$ 이면 가장 큰 허브의 링크수 $k_{\mathrm{max}} \sim N^{1/(\gamma -1)}$ 이 $N$ 보다 빨리 자라야 하는데, 한 노드는 많아야 $N - 1$ 개와만 연결될 수 있다. 이것이 그래프(네트워크) 구현 가능성(graphicality) 문제다. 주어진 링크수 목록으로 (자기 연결이나 중복 링크 없이) 실제로 네트워크를 만들 수 있는지는 에르되시-갈라이(Erdős–Gallai) 정리로 판정한다. 링크수를 큰 것부터 $d_{1} \ge d_{2} \ge \cdots \ge d_{n}$ 으로 정렬했을 때, 합이 짝수이고 모든 $r$ 에 대해

\sum _{i=1}^{r} d_{i} \le r(r - 1) + \sum _{i=r+1}^{n} \min (d_{i}, r)

이면 구현 가능하다. 예를 들어 링크수가 모두 2인 노드 3개는 삼각형이 되지만, 2, 2, 3은 만들 수 없다.

$\gamma > 3$ 이면 네트워크에서의 스미기(percolation), 전염병 전파, 각종 상전이(phase transition) 현상 등이 무작위 네트워크 또는 소위 평균장 이론 근사(mean-field approximation)와 같은 보편성 분류(universality class)에 속한다.

에르되시-갈라이 판정기: 링크수 목록을 쉼표로 입력하세요

\gamma

1.80 N

거듭제곱 분포(k ≥ 1, k ≤ N − 1로 자름)에서 N개의 링크수를 뽑아 구현 가능한지 판정합니다. 합이 홀수인 경우는 아무 노드나 하나에 1을 더해 짝수로 맞춥니다.

임의의 링크수 분포를 가진 네트워크 만들기the configuration model

복습. 링크를 무작위로 연결하면 링크수가 이항/푸아송 분포를 따르게 된다. 그러면 거듭제곱 분포를 따르는 네트워크는 어떻게 만들까?

구조 모형(configuration model): 링크수 분포를 미리 정해놓고 만들기!

$\{p_{k}\}$ 에서 $N$ 개의 미리 정해진 링크수를 뽑는다. 누적 분포 $D(k) = \sum _{k'\ge k} p_{k'}$ 를 만들고, 0과 1 사이에서 균일하게 난수(random number) $r$ 을 $N$ 개 생성해 이 변환으로 $N$ 개의 $k$ 값을 부여한다.
노드마다 정해진 “미연결 링크(stub)”들이 있다.
미연결 링크를 무작위로 짝지어 네트워크를 “조립”한다.

주어진 이웃 수 안에서 무작위로 연결하여 네트워크를 “조립”하므로, 정해진 이웃 수에 대해 여러 네트워크 구조가 만들어질 수 있다. 모형의 용도: 특정 링크수 분포를 가진 네트워크의 일반적 성질을 연구하기 위해 가능한 많은 네트워크 구조를 점검한다. 다만 언제나 가능하지는 않다. 자기 연결(self-loop)과 다중 링크(multi-link)가 생길 수 있다.

링크수 목록

난수 r을 누적 분포 D(k)로 링크수 k로 바꾸기 (γ = 2.5)

이웃 수 보존 무작위화degree-preserving randomization

실제 네트워크의 어떤 성질이 링크수 분포 때문인지, 아니면 그 이상의 연결 구조 때문인지 알고 싶을 때 쓴다. 두 링크 $(S_{1} - T_{1})$ 과 $(S_{2} - T_{2})$ 를 골라 $(S_{1} - T_{2})$ 와 $(S_{2} - T_{1})$ 로 바꾸는 일을 반복한다. 각 노드별 “링크수(이웃 수)”는 보존하면서 연결 구조를 무작위로 섞는다!

반면 링크를 전부 다 “수거”해서 다시 노드들 사이에 무작위로 배치하면, 링크수 분포가 푸아송 분포인 무작위 네트워크가 된다. 허브가 사라진다.

오른쪽 데모는 동네(클러스터)가 뚜렷한 네트워크에서 출발한다. 교환을 반복하면 링크수 목록은 그대로인데, 삼각형(친구의 친구가 친구인 관계)은 급격히 줄어든다. 삼각형이 많은 것은 링크수 분포만으로 설명되지 않는 구조라는 뜻이다.

숨은 매개변수 모형hidden parameter model

링크수 분포를 직접적으로 할당하는 대신, 노드 고유의 “숨은 매개변수”가 있어서 연결이 그 매개변수에 의존하는 확률로 이뤄지는 모형이다. 구조 모형의 다중 링크와 자기 연결이 생길 수 있는 문제를 극복할 수 있다.

노드마다 할당된 숨은 매개변수 $\{\eta _{i}\}$ 에 대해, $\eta _{i}$ 를 가진 노드와 $\eta _{j}$ 를 가진 노드가 연결될 확률은

p(\eta_{i},\eta_{j})=\frac{\eta_{i}\eta_{j}}{\langle\eta\rangle N}

이다. 예상되는 전체 링크 수는 $L = (1/2)\sum _{i,j} \eta _{i}\eta _{j}/(\langle \eta \rangle N) = (1/2)\langle \eta \rangle N$ 이고, 링크수 분포는 $p_{k} = (1/N)\sum _{j} e^{-\eta _{j}}\eta _{j}^{k}/k!$ , 곧 숨은 매개변수의 분포 $\rho (\eta )$ 에 대해 $p_{k} = \int e^{-\eta }\eta ^{k}/k! \rho (\eta )\,\mathrm{d}\eta$ 이다.

척도 없는 네트워크 만들기 $\eta _{i} = c/i^{\alpha }$ , $i = 1, \dots , N$ ( $c$ 는 $\langle k\rangle$ 를 조절하는 상수)로 두면 $p_{k} \sim k^{-(1+1/\alpha )}$ . 거듭제곱 지수 $\gamma = 1 + 1/\alpha$ 로 조절할 수 있음!

척도 없는 네트워크를 만드는 “정적 모형(static model)”[Goh, Kahng, and Kim 2001]으로, 거듭제곱 지수를 원하는 대로 조절할 수 있는 대표적 모형이다. 이 시리즈의 다른 데모에 나온 척도 없는 네트워크도 모두 이 방식으로 만들었다.

\alpha

0.67

\langle k\rangle

4

로그 묶기한 링크수 분포 (N = 3000, 3번 평균)기울기 −(1 + 1/α)

작은 예: 숨은 매개변수 η = (1, 1.5, 2, 0.5)일 때 연결 확률

부록: 거듭제곱 분포 vs 지수함수적으로 제한된 분포heavy tails vs bounded tails

두꺼운 꼬리(fat tail), 무거운 꼬리(heavy tail), 긴 꼬리(long tail), 파레토(Pareto), 브래드포드(Bradford) 분포 … 대 제한이 있는 분포(인간의 키, 자동차 사고를 당할 확률, …). 제한이 있는 분포는 큰 $x$ 값에 대해 $p_{x}$ 가 지수함수적으로( $e^{-x}$ ) 또는 그것보다 더 빠르게(예: $e^{-x^{2}/\sigma ^{2}}$ ) 감소한다.

$e^{-x/a}$ 라는 함수는 $x = a$ 가 되면 원래의 $1/e$ , $x = 2a$ 가 되면 $1/e^{2}$ 의 비율이 된다. $x = a$ 라는 지점을 경계로 그것보다 큰 값을 가질 확률이 급격하게 작아진다. 방사성 동위원소의 “반감기(half-life)”처럼, $x = a$ 라는 특징적인 규모(scale)가 있다. 척도가 있다! 분포의 꼬리 부분이 “얇음”: 얇은 꼬리(thin tail).

반면 두꺼운 꼬리에서는 이상치(outlier) 또는 희귀한 사건(rare event)에 해당하는 매우 큰 사건 $x$ 가 자주 일어난다. 사건 $x$ 의 크기가 몇 개의 자릿수(order of magnitude)에 걸쳐 있을 수 있다. 위 첫 화면의 그림이 그 예다.

위키백과의 파레토 법칙(80 대 20 법칙) 그림에서 “머리”와 “꼬리”는 거듭제곱 분포의 누적분포와 등수 이야기를 할 때 “꼬리”라고 불렀던 곳과 반대다. 등수 그림에서는 큰 값이 왼쪽(높은 등수)에 놓이기 때문이다.

y = e^−xy = e^−x²y = x⁻²

모두 로그 척도에서 x⁻²는 직선(ln y = −2 ln x)이고, 지수함수는 ln y = −e^{ln x}처럼 급격히 꺾입니다. y만 로그 척도에서는 e^−x가 직선입니다.

혼합된 분포 (crossover distribution)

지수함수 절단(cutoff)이 있는 거듭제곱 법칙: $p(x) = Cx^{-\gamma }e^{-\lambda x}$ , $C = \lambda ^{1-\gamma }/\Gamma (1 - \gamma , \lambda x_{\mathrm{min}})$ (상부 불완전 감마 함수 $\Gamma (s, x) = \int _{x}^{\infty } t^{s-1}e^{-t}\,\mathrm{d}t$ ). $\ln p(x) = \ln C - \gamma \ln x - \lambda x$ 이니, 지수함수 부분 때문에 $1/e$ 배가 되는 “절단”까지는 거듭제곱 법칙을 잘 따르는 것으로 보인다.

펼쳐진 지수함수(stretched exponential), 베이불(Weibull) 분포: 누적분포함수 $P(x) = e^{-(\lambda x)^{\beta }}$ 에서 확률분포함수 $p(x) = Cx^{\beta -1}e^{-(\lambda x)^{\beta }}$ , $C = \beta \lambda ^{\beta }$ . $\beta = 1$ 이면 지수함수와 같고, $0 < \beta < 1$ 이면 지수함수의 감소하는 정도가 여러 자릿수로 “펼쳐짐”, $\beta$ 가 작아질수록 거듭제곱 법칙과 구분하기가 힘들어진다. $\beta > 1$ 이면 감소하는 정도가 더 “압축됨”, $\beta = 2$ 이면 레일리 분포(Rayleigh distribution).

로그 정규 분포(log-normal distribution): $\ln x$ 가 정규분포를 따르는 경우 $p(x) = [1/(\sqrt{2\pi }\sigma x)] \exp [-(\ln x - \mu )^{2}/(2\sigma ^{2})]$ . 골턴(Galton) 또는 지브라(Gibrat) 분포라고도 한다. 변수가 많은 독립적인 양의 난수들의 곱으로 주어지는 경우(예: 금융에서 지속적인 거래로 발생하는 복합적인 수익)에 나타난다. $\sigma ^{2} = \langle (\ln x)^{2}\rangle - \langle \ln x\rangle ^{2}$ 는 자릿수 단위로 표현되는 $x$ 의 크기 규모에 대한 변화 정도이니, $\ln x$ 가 정규 분포를 따르면 $x$ 값 자체는 다소 크게 변할 수 있다.

교재 오타 메모『네트워크 사이언스』의 펼쳐진 지수함수 부분에는 “확률분포함수”라는 표시가 빠져 있다. 로그 정규 분포 식에는 없어야 할 아래첨자 $x$ 가 붙어 있고, $\sigma ^{2}$ 식에는 $\rangle$ 가 하나 더 있다(원문의 오타).

진짜(?) 심화 주제: 이러한 다양한 분포들이 왜 생기는가?

통계(물리)학적 설명법. 주어진 제한 조건들(constraints)을 만족하는 상태(state)들 중 가장 경우의 수 $\Omega$ 가 많은 상태들로 구성된 “패턴”이 생길 가능성이 크다는 설명 방식이다[Frank 2009]. 볼츠만(Ludwig Eduard Boltzmann, 1844–1906)의 묘비에 새겨진 $S = k_{B} \log \Omega$ 를 엔트로피(entropy)라고 부르기로 …. 평균이 정해져 있으면 지수함수 분포가, 평균과 분산이 정해져 있으면 정규분포가, 로그의 평균이 정해져 있으면 거듭제곱 분포가 엔트로피를 최대로 한다.

네트워크 모형으로 설명. 특정한 규칙으로 만들어진 네트워크가 자연계에서 관찰되는 링크수 분포를 보인다면 그 규칙으로 만들어진 것일지도? 그런데 구조 모형과 숨은 매개변수 모형은 링크수 분포를 (직간접적으로) 미리 정해 놓고 만드는 것이라, 거듭제곱 분포가 왜 생기는지는 설명하지 못한다.

To Be Continued … (네트워크가 자라나는 규칙을 다루는 다음 이야기: 『네트워크 사이언스』 5장의 바라바시-알버트 모형)

요약많은 네트워크가 링크수 분포가 거듭제곱 분포인 척도 없는 네트워크이고(보편성), 허브가 있으면 시스템의 동작이 근본적으로 바뀐다. 다만 거듭제곱 법칙 형식은 실제 시스템에서 순수한 꼴로 거의 볼 수 없다. 크게 지수함수적으로 제한된 네트워크와 두꺼운 꼬리를 가진 네트워크로 뭉뚱그려 구분하고, 고도로 연결된 몇 개의 허브가 링크수가 적은 많은 노드와 공존한다는 것만으로도 종종 실제 네트워크의 성질을 이해하기에 충분하다.

참고문헌references

『네트워크 사이언스』 (에이콘출판사, 2023), 이미진·윤진혁·이상훈·이은·조항현·김희태·손승우 옮김. 원서: Albert-László Barabási, Network Science (Cambridge University Press, 2016). 4장 「척도 없는 성질」.
『네트워크 분석』 (에이콘출판사, 2022), 손승우·엄영호·이상훈·이은·김희태·이미진 옮김. 원서: Filippo Menczer, Santo Fortunato, and Clayton A. Davis, A First Course in Network Science (Cambridge University Press, 2020). 3장 「허브」.
K.-I. Goh, B. Kahng, and D. Kim, “Universal Behavior of Load Distribution in Scale-Free Networks,” Physical Review Letters 87, 278701 (2001).
S. A. Frank, “The common patterns of nature,” Journal of Evolutionary Biology 22(8), 1563–1585 (2009).
D. Sornette and G. Ouillon, “Dragon-kings: Mechanisms, statistical methods and empirical evidence,” The European Physical Journal Special Topics 205, 1–26 (2012).