거듭제곱 분포와 척도 없음: 척도 없는 네트워크 인터랙티브 데모

월드와이드웹과 허브the World Wide Web and hubs

1998년, 노트르담 대학교 바라바시(Albert-László Barabási) 연구실에서 정하웅 박사는 웹 문서를 따라다니며 링크를 수집하는 프로그램(웹 크롤러)으로 월드와이드웹(WWW, World Wide Web)의 구조를 지도로 그렸다. 웹 문서를 노드(node), 하이퍼링크를 링크(link)로 보면 웹은 거대한 방향성 네트워크다. 그 결과는 놀라웠다.

대부분의 웹 문서는 링크가 몇 개뿐인데, 일부 문서에는 링크가 압도적으로 많이 몰려 있었다. 이런 노드를 허브(hub)라고 한다. 들어오는 링크수 $k_{\mathrm{in}}$ 와 나가는 링크수 $k_{\mathrm{out}}$ 의 분포는 모두

P(k) \propto k^{-\gamma }

꼴의 거듭제곱 분포(power-law distribution)를 따랐다[Albert, Jeong, and Barabási 1999].

무작위 네트워크와 비교하면

무작위 네트워크 모형에서는 각 링크가 확률 $p$ 로 독립적으로 생긴다. 한 노드가 $(N - 1)$ 개의 다른 노드 중 정확히 $k$ 개와 연결될 확률은 이항분포

P(k)=\binom{N-1}{k}p^{k}(1-p)^{N-1-k}\approx\frac{\langle k\rangle^{k}e^{-\langle k\rangle}}{k!}

이고, 노드 수 $N$ 이 매우 크고 $p$ 가 매우 작으면 푸아송 근사(the Poisson approximation)가 성립한다. 평균이 같은 푸아송 분포는 평균에서 멀어지면 매우 빠르게 0으로 떨어진다. 무작위 네트워크로는 웹에서 관찰된 허브가 나올 수 없다.

오른쪽 데모에서 노드 수와 평균 링크수가 같은 두 네트워크를 비교해 보자. 그림에는 서로 연결된 가장 큰 덩어리만 그렸고, 아래 분포 그래프는 각각 노드 2만 개짜리 네트워크로 그린 것이다.

허브(hub): 링크수가 압도적으로(?) 많은 노드

\langle k\rangle

3.0

\gamma

2.30

무작위 네트워크 (노드 300개)

척도 없는 네트워크 (노드 300개)

무작위 네트워크평균이 같은 푸아송 분포척도 없는 네트워크기울기 −γ 기준선

거듭제곱 분포와 로그 척도power law on a log-log scale

$P(k) = ck^{-\gamma }$ 의 양변에 로그를 취하면

\log P(k) = \log c - \gamma \log k

이다. $Y = a - \gamma X$ 꼴이니, $k$ 와 $P(k)$ 에 각각 로그를 취해서 가로, 세로축에 표시하면 기울기 $-\gamma$ 로 감소하는 직선 그래프가 된다. 로그 척도에서는 1, 2, 4, 8, 16이 같은 간격으로 놓인다( $a^{b} = c \to b = \log _{a} c$ ). 여기서 $\sum _{k=k_{\mathrm{min}}}^{k_{\mathrm{max}}} P(k) = 1$ 이 되어야 하므로 $c = (\sum k^{-\gamma })^{-1} \approx (\int k^{-\gamma }\,\mathrm{d}k)^{-1}$ 이다.

$\gamma$ 를 링크수 지수(degree exponent)라고 한다. 링크수 지수 $\gamma$ 가 클수록(작을수록) 분포가 더 급격하게(완만하게) 감소하고 링크수가 더 균일하다(불균일하다)는 뜻이다. 웹의 분포는 거의 4개 자릿수의 규모에 걸쳐 직선을 유지했다.

척도 없는 네트워크(scale-free network)링크수 분포가 거듭제곱 법칙을 따르는 네트워크.

눈치채셨나요?

지금까지 거창하게 “거듭제곱 법칙”이라고 한 건 그냥 항이 하나만 있는 다항식(polynomial), 곧 “−γ차항만 있는 함수”다. 예를 들어 $\gamma = -1$ 이면 그냥 1차함수다. 링크수가 2배가 되면 링크수에 정비례하는 양도 2배가 된다.

\gamma

2.50

\langle k\rangle

6

거듭제곱 분포 p_k ∝ k^−γ (k ≥ 1)푸아송 분포 (평균 〈k〉)

“모두 선형”에서는 두 분포 모두 오른쪽 꼬리가 바닥에 붙어 구분이 안 됩니다. “모두 로그”로 바꾸면 거듭제곱 분포만 직선이 되고, 푸아송 분포는 급격히 꺾여 떨어집니다. “세로축만 로그”에서는 지수함수가 직선이 됩니다.

로그 척도의 눈금: 1, 2, 4, 8, 16이 같은 간격

“척도 없음”의 의미what “scale-free” means

“척도(scale)” 변환을 해 보자.

링크수 $k$ 인 노드에 비해, 링크수 $2k$ 인 노드가 있을 확률이 $2^{-\gamma } = 1/2^{\gamma }$ 배로 작다.
링크수 $2k$ 인 노드에 비해, 링크수 $4k$ 인 노드가 있을 확률이 $2^{-\gamma }$ 배로 작다.
링크수 $4k$ 인 노드에 비해, 링크수 $8k$ 인 노드가 있을 확률이 $2^{-\gamma }$ 배로 작다. …

이 비율이 관심의 대상인 링크수와는 무관하고, 몇 배 큰 걸 생각하는지에 따라서만 결정되는 상수다! 곧 $P(k) \propto k^{-\gamma }$ 는 어떤 크기(scale)인 $k$ “입장”에서 봐도 똑같은 분포함수다. $k$ 의 $b$ 배, $bk$ 인 노드가 얼마나 많은지 또는 적은지가 $k$ 자체와 무관하게 결정된다.

대표적인 링크수를 상징하는 크기 또는 척도(scale)가 없다: 척도 없음(scale-free).

오른쪽에서 $k$ 를 움직여 보자. 거듭제곱 분포의 비율 $p(bk)/p(k)$ 는 언제나 $b^{-\gamma }$ 로 일정하지만, 푸아송 분포의 비율은 $k$ 에 따라 크게 달라진다. 푸아송 분포에는 평균 $\langle k\rangle$ 라는 대표적인 크기가 있기 때문이다.

“정상(Normal)” 세계에서는 다들 비슷한 크기, “척도 없는(Scale-free)” 세계에서는 크기의 기준이 없음 [Bagrow and Ahn 2024의 그림]

k

b

\gamma

2.50

\langle k\rangle

6

비율 $p(bk)/p(k)$ 와 $k$ (로그 척도)

프랙탈(fractal) 구조

척도 없음은 해안선, 시에르핀스키 삼각형, 2차원 정사각격자의 각 격자점을 0.59274621…의 확률로 채운 구조, 망델브로 집합 같은 프랙탈의 성질과 같은 종류다. 프랙탈 차원 $d_{f}$ 는

\text{길이}\ l\text{인 크기 안에 들어 있는 단위체의 개수}\ \propto l^{d_{f}}

로 정의된다. 이것도 거듭제곱꼴이다! 척도 변환을 하면, 길이 $l$ 인 정사각형 내부의 단위체 개수에 비해 길이 $bl$ 인 정사각형 내부의 단위체 개수가 $l$ 과 무관하게 언제나 $b^{d_{f}}$ 배다.

오른쪽은 파스칼 삼각형의 홀수 칸을 칠해 만든 시에르핀스키 삼각형이다. 한 변이 $l$ 인 정사각형(분홍 테두리) 안의 칠해진 칸 수를 세면, $l$ 을 2배로 늘릴 때마다 정확히 3배가 된다. 따라서 $d_{f} = \ln 3/\ln 2 \approx 1.585$ 이다. 1차원 선( $d = 1$ )과 2차원 면( $d = 2$ ) 사이의 “분수 차원”이다.

거듭제곱 분포 vs 거듭제곱 스케일링

거듭제곱 분포(distribution)와 거듭제곱 스케일링(scaling)은 구분해야 한다. 생물의 몸집 크기 $x$ 와 대사량 $y$ 의 관계 $y = x^{\alpha }$ 처럼 두 양 사이의 관계가 거듭제곱인 것은 스케일링이다. 링크수 분포가 거듭제곱인 것은 확률분포에 대한 이야기다. 수많은 현상에서 거듭제곱 법칙이 보고되었지만, 그 통계적 근거와 작동 원리(mechanism)가 얼마나 확실한지는 경우마다 다르다[Stumpf and Porter 2012].

l

32

칠해진 칸의 수 $N(l)$ 와 $l$ (로그-로그 척도)

이산적인 형식과 연속적인 형식discrete and continuum forms

이산적인(discrete) 형식

노드의 링크수는 정수 $k = 0, 1, 2, \dots$ 이다.

p_{k} = Ck^{-\gamma }

는 무작위로 선택한 노드가 링크수 $k$ 를 가질 확률이다. 정규화 조건(확률분포의 합 = 1) $\sum _{k=1}^{\infty } p_{k} = 1$ 에서

C=\frac{1}{\sum_{k=1}^{\infty}k^{-\gamma}}=\frac{1}{\zeta(\gamma)}

이고, $\zeta (\gamma )$ 는 리만-제타 함수(Riemann-zeta function)다.

수학적인 문제점.

$k = 0$ 에서 발산한다(정의가 안 된다). $p_{0}$ 을 따로 정의해서 해결할 수 있다. 예를 들어 $p_{0} = 0$ , 곧 링크수가 0인 고립된 노드는 없다고 둔다.
$\gamma \le 1$ 이면 $\sum _{k=k_{\mathrm{min}}}^{\infty } p_{k} \to \infty$ 로 발산하여 정규화 조건을 맞출 수 없다(확률분포가 제대로 정의되지 않는다). $\gamma > 1$ 에서 정의하거나, $\gamma \le 1$ 이면 큰 $k$ 쪽에서 절단(cutoff)을 해야 한다.
$\gamma > 1$ 인 경우에도 발산과 관련된 여러 문제가 있을 수 있는데, 이것은 다음 편에서 다룬다.

연속적인(continuum) 형식

해석적(analytic) 계산의 편의 등을 위해 링크수 $k$ 를 연속변수로 가정하면

p(k) = Ck^{-\gamma } = (\gamma - 1)k_{\mathrm{min}}^{\gamma -1} k^{-\gamma }

이다. 정규화 조건 $\int _{k_{\mathrm{min}}}^{\infty } p(k)\,\mathrm{d}k = 1$ 에서 $C = (\gamma - 1)k_{\mathrm{min}}^{\gamma -1}$ 이고, $k_{\mathrm{min}}$ 은 거듭제곱 법칙이 유지되는 가장 작은 링크수다.

$\int _{k_{1}}^{k_{2}} p(k)\,\mathrm{d}k$ 는 무작위로 선택한 노드가 $k_{1}$ 과 $k_{2}$ 사이의 링크수를 가질 확률이다. 정확히 특정 자연수 $k$ 라는 값을 가질 확률은 엄밀하게는 0이고, $k$ 근처에서 적분한 값을 이용하게 된다.

교재 오타 메모『네트워크 사이언스』 176쪽 맨 윗줄의 “거듭제곱 법칙(식 4.8)”은 “거듭제곱 법칙(식 4.9)”이 맞다.

\gamma

2.50

부분합 $S(K) = \sum _{k=1}^{K} k^{-\gamma }$ 와 $K$

k_{\mathrm{min}}

1.0

k_{1}

k_{2}

연속적인 형식 $p(k) = (\gamma - 1)k_{\mathrm{min}}^{\gamma -1}k^{-\gamma }$ 와 $\int _{k_{1}}^{k_{2}} p(k)\,\mathrm{d}k$

참고문헌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장 「허브」.
R. Albert, H. Jeong, and A.-L. Barabási, “Diameter of the World-Wide Web,” Nature 401, 130 (1999).
M. P. H. Stumpf and M. A. Porter, “Critical Truths About Power Laws,” Science 335, 665 (2012).
J. Bagrow and Y.-Y. Ahn, Working with Network Data (Cambridge University Press, 2024).
K.-I. Goh, B. Kahng, and D. Kim, “Universal Behavior of Load Distribution in Scale-Free Networks,” Physical Review Letters 87, 278701 (2001). 데모의 척도 없는 네트워크를 만드는 데 쓴 정적 모형(static model).