거듭제곱 법칙과 척도 없는 네트워크

링크수 분포 그리기와 지수 측정Plotting, Fitting, and Testing Power Laws

실제 데이터에서 링크수 분포를 어떻게 그려야 거듭제곱 법칙이 제대로 보일까? 선형 묶기, 로그 묶기, 누적 분포, 등수 그림을 같은 데이터로 비교하고, 최소제곱법과 최대우도추정으로 링크수 지수를 재 본다. 마지막으로 “정말 거듭제곱 법칙이 맞는가?”를 묻는 적합도 검정을 직접 돌려 본다.

이 데모는 Claude Opus 5.5가 제작했으며, 경상국립대학교 물리학과 이상훈 교수의 강의자료(2024 복잡계 여름학교, ‘거듭제곱 법칙과 척도 없는 네트워크’ 강의)를 기반으로 합니다.

같은 표본 2만 개(γ = 2.5)를 선형 묶기(회색)와 로그 묶기(분홍)로 그린 그림. 꼬리에서 회색 점들이 1/N 높이에 평평하게 깔리는 반면, 로그 묶기는 직선을 따라 내려갑니다.

링크수 분포 그리기plotting the degree distribution

실제 네트워크에서 pkp_{k}를 그리는 “초급(?!)” 방법은 히스토그램(histogram)이다.

  • 모든 kk값에 대해 그 링크수를 가진 노드 개수 NkN_{k}를 구한다.
  • 전체 노드 개수가 NN이면 확률 pk=Nk/Np_{k} = N_{k}/N이다.
  • 가로축을 kk, 세로축을 pkp_{k}로 한 그림을 로그-로그 척도로 그린다. 선형 척도로 그리면 분포 형태를 분간하기 어렵다.

이 “잘못된”(하지만 문헌에서 자주 볼 수 있는) 방법, 곧 각 “칸”의 크기 Δk=1\Delta k = 1로 일정한 선형 묶기(linear binning)에는 문제가 있다. kk가 커질수록 “일정한” Δk\Delta k가 로그 척도에서는 점점 더 촘촘해져서 “표본”이 부족해진다. 링크수가 kk인 노드가 하나만 있는 부분에서는 Nk=1N_{k} = 1, pk=1/Np_{k} = 1/N인 평평한 부분(plateau)이 생긴다. 링크수 지수 γ\gamma 추정이 쉽지 않다!

로그 묶기 (logarithmic binning)

로그 척도에서 균일하게 표본 추출을 하기 위해 지수함수적으로 커지는 “칸(bin)”을 이용한다. 첫 번째 칸의 크기 b0=20=1b_{0} = 2^{0} = 1(k=1k = 1 포함), 두 번째 칸 b1=21=2b_{1} = 2^{1} = 2(k=2,3k = 2, 3), 세 번째 칸 b2=22=4b_{2} = 2^{2} = 4(k=4,5,6,7k = 4, 5, 6, 7) …. 크기가 bnb_{n}인 nn번째 칸에 있는 노드의 수 NnN_{n}, 해당 칸에 있는 노드의 평균 링크수 ⟨kn⟩\langle k_{n}\rangle에 대해 그림에 찍을 링크수 분포는 p⟨kn⟩=Nn/bnp_{\langle k_{n}\rangle } = N_{n}/b_{n}(전체 노드 수 NN으로 나눠 정규화)이다.

로그 묶기의 결과: 조항현 교수님의 코드 참고(github.com/h2jo/log_binning)

누적 분포 (cumulative distribution)

(상보적, complementary) 누적 분포 P(k)=∫k∞p(k′) dk′P(k) = \int _{k}^{\infty } p(k')\,\mathrm{d}k'는 링크수가 kk 이상인 노드의 비율이다. 거듭제곱 분포 p(k)∝k−γp(k) \propto k^{-\gamma }이면 P(k)∝k−γ+1P(k) \propto k^{-\gamma +1}, 누적 분포도 거듭제곱꼴이고 지수만 1 차이가 난다. 누적하는 과정에서 여러 링크수에 대한 정보가 취합되어 통계가 정확해진다는 장점이 있다.

등수(rank) 이용

P(k)P(k)는 전체 노드들 중 링크수가 kk 이상인 노드의 비율이다. 전체 노드가 NN개라면, 링크수 kk인 노드가 노드들을 링크 순서대로 정렬해 등수를 매길 때 NP(k)NP(k)등에 해당한다는 뜻이다(“내 위로 NP(k)NP(k)개의 노드가 있음”). 따라서 각 kk에 대해 개수를 세고 다시 합산하는 과정 대신, 노드의 링크수들을 크기 순서대로 정렬해서 등수 그림(rank plot)을 로그-로그 척도로 그리면 된다! 이때 기울기는 −1/(γ−1)-1/(\gamma - 1)이다.

데이터참값 γ로 그린 기준선

링크수 지수 측정하기estimating the degree exponent

로그-로그 척도에서 직선의 기울기를 추정하는 문제이므로, 최소제곱법(method of least squares)으로 ∑(yi−b0−b1xi)2\sum (y_{i} - b_{0} - b_{1}x_{i})^{2}가 최소가 되는 b0b_{0}와 b1b_{1}을 추정할 수 있다(선형회귀분석, linear regression). 문제점: 로그 척도라서 모형과 데이터가 벗어나는 정도가 위치마다 실제로는 다르다! 좀 더 통계적으로 엄밀한 최대우도추정(maximum likelihood estimation)법을 권장한다[Clauset, Shalizi, and Newman 2009].

  1. kmink_{\mathrm{min}}과 kmaxk_{\mathrm{max}} 사이에서 하나의 KminK_{\mathrm{min}} 값을 선택하고, KminK_{\mathrm{min}} 이상인 링크수 kik_{i}(NN개)로
    γ=1+N[∑i=1Nln⁡kiKmin−12]−1\gamma=1+N\left[\sum_{i=1}^{N}\ln\frac{k_{i}}{K_{\mathrm{min}}-\tfrac{1}{2}}\right]^{-1}
    로 추정한다.
  2. 이것은 링크수 분포가 pk=k−γ/ζ(γ,Kmin)p_{k} = k^{-\gamma }/\zeta (\gamma , K_{\mathrm{min}})라고 추정하는 것이다. ζ(s,q)=∑k=0∞(k+q)−s\zeta (s, q) = \sum _{k=0}^{\infty }(k + q)^{-s}는 후르비츠(Hurwitz)-제타 함수다. 누적분포함수는 Pk=∑k′≥kpk′=ζ(γ,k)/ζ(γ,Kmin)P_{k} = \sum _{k'\ge k} p_{k'} = \zeta (\gamma , k)/\zeta (\gamma , K_{\mathrm{min}})이다.
  3. 콜모고로프-스미르노프(Kolmogorov-Smirnov) 검정을 사용해 데이터에 대한 누적분포함수 S(k)S(k)와 PkP_{k} 사이의 최대 거리 D=max⁡k≥Kmin∣S(k)−Pk∣D = \max _{k\ge K_{\mathrm{min}}} |S(k) - P_{k}|를 추정한다.
  4. (1)~(3) 과정을 kmink_{\mathrm{min}}에서 kmaxk_{\mathrm{max}}까지의 전체 KminK_{\mathrm{min}} 범위를 쭉 훑으며 반복한다. DD가 최소가 되는 지점의 KminK_{\mathrm{min}}이 거듭제곱 분포를 따르기 시작하는 최소 링크수, 그때의 γ\gamma가 링크수 지수에 대한 추정치다.

(1)의 식은 이산적인 우도를 근사한 것이라 KminK_{\mathrm{min}}이 작으면(대략 6 미만) 오차가 커진다[Clauset, Shalizi, and Newman 2009]. 데모에서는 근사식 대신 이산적인 로그 우도 L(γ)=−γ∑ln⁡ki−Nln⁡ζ(γ,Kmin)\mathcal{L}(\gamma ) = -\gamma \sum \ln k_{i} - N \ln \zeta (\gamma , K_{\mathrm{min}})를 직접 최대화했고, 근사식의 값도 함께 보여 준다.

이때 링크수 지수에 대한 표준 오차는 σγ=1/N[ζ′′(γ,Kmin)/ζ(γ,Kmin)−(ζ′(γ,Kmin)/ζ(γ,Kmin))2]\sigma _{\gamma } = 1/\sqrt{N[\zeta ''(\gamma , K_{\mathrm{min}})/\zeta (\gamma , K_{\mathrm{min}}) - (\zeta '(\gamma , K_{\mathrm{min}})/\zeta (\gamma , K_{\mathrm{min}}))^{2}]}이다. 여기서 ζ′(s,q)=∂ζ(s,q)/∂s\zeta '(s, q) = \partial \zeta (s, q)/\partial s.

교재 오타 메모『네트워크 사이언스』 222쪽 (4.44)식 위쪽 설명의 “데이터 S(k)의 CDF”는 “데이터에 대한 CDF인 S(k)”가 맞다.

오른쪽 데모는 참값 γ\gamma를 아는 표본에 네 가지 방법을 적용한다. “여러 번 반복”을 누르면 같은 실험을 반복해 각 방법의 추정치가 참값 주변에 얼마나 모이는지 보여 준다.

누적 분포와 최대우도추정으로 맞춘 결과

Kmin에 따른 KS 거리 D

반복 실험: 방법별 추정치 (세로선: 참값)

적합도 검정: 링크수가 진짜 거듭제곱 법칙이 맞는가?goodness-of-fit test

어떤 데이터라도 앞서 소개한 방법으로 링크수 지수를 측정하면 어떻게든 가장 적합한 KminK_{\mathrm{min}}과 γ\gamma값이 나오게 된다. 거듭제곱 법칙 가설의 타당성을 정량화하는 적합도 검정을, 통계학에서 중요한 양인 pp-값(pp-value)으로 표현해야 한다.

  1. 진짜 데이터에 대해 위의 (3) 단계에서 얻은 거리를 DrealD^{\mathrm{real}}이라 한다.
  2. (2) 단계에서 추정한 분포함수를 이용해서 (가상의) “링크수”들을 생성하고, 그것들의 누적분포와 추정한 누적분포함수 사이의 거리 DsyntheticD^{\mathrm{synthetic}}을 구한다.
  3. 이것을 M≫1M \gg 1번 반복하여 DsyntheticD^{\mathrm{synthetic}}에 대한 분포 p(Dsynthetic)p(D^{\mathrm{synthetic}})을 얻는다. 이제 진짜 데이터 분포로부터의 거리 DrealD^{\mathrm{real}}이 그 분포가 예측하는 범위에 들어가는가를 살펴보면 된다.
p=∫Dreal∞p(Dsynthetic) dDsyntheticp = \int _{D^{\mathrm{real}}}^{\infty } p(D^{\mathrm{synthetic}})\,\mathrm{d}D^{\mathrm{synthetic}}

DrealD^{\mathrm{real}}이 얼마나 통계적 변동이 허용하는 범위 안에 있는지를 나타내는 측정량이다. 예를 들어 p<10−4p < 10^{-4}이면 이 데이터가 추정한 pkp_{k}로 설명할 수 있는 범위 한참 밖에 있다는 뜻이다(보통 1% = 0.01 정도를 허용 범위로 본다).

교재 오타 메모『네트워크 사이언스』 222쪽 3.에서 “2번 단계를 2M번”은 “2번 단계를 M번”이 맞다. pp-값 수식에도 적분하는 함수를 대문자 PP로 쓰고 적분 아래끝을 그냥 DD로 쓴 오타가 있다(원문의 오타).

오른쪽 데모는 성질을 아는 다섯 가지 데이터에 검정을 적용한다. KminK_{\mathrm{min}}을 자동으로 고르면, 지수함수 분포나 로그 정규 분포라도 꼬리의 좁은 범위만 남겨 거듭제곱 법칙을 기각하지 못하는 경우가 많다. KminK_{\mathrm{min}}을 1로 고정해 넓은 범위에서 검정하면 결과가 크게 달라진다. 거듭제곱 법칙을 “얼마나 넓은 범위에서” 주장하는지가 중요한 이유다.

가상 데이터마다 KminK_{\mathrm{min}}을 고정한 채 γ\gamma를 다시 추정한 뒤 거리를 잰다(클라우셋 등의 원래 방법은 KminK_{\mathrm{min}}까지 다시 찾는다).

데이터의 누적 분포와 맞춘 거듭제곱 분포

가상 데이터의 거리 분포 p(Dsynthetic)와 Dreal

척도 없는 네트워크는 드문가, 흔한가rare or everywhere?

2018년 공개되고 2019년 출판된 브로이도와 클라우셋의 논문 “Scale-free networks are rare”[Broido and Clauset 2019]는 사회, 생물, 기술, 교통, 정보 분야의 약 1000개 네트워크에 위의 엄격한 통계 도구를 적용했다. 결론은 강한 척도 없는 구조가 경험적으로 드물고, 대부분의 네트워크에서는 로그 정규 분포가 거듭제곱 법칙만큼 또는 더 잘 맞는다는 것이었다.

반론도 이어졌다. 바라바시는 블로그 글 “Love is All You Need”로 반박했고, 보이탈로프 등은 “Scale-free networks well done”[Voitalov et al. 2019]에서 다른 통계적 관점으로 척도 없는 성질이 흔하다고 주장했다. 홀메(Holme)는 논평 “Rare and everywhere”[Holme 2019]에서 이 논쟁이 무엇을 “척도 없음”이라고 부를지에 대한 정의의 문제이기도 하다고 정리했다. 교과서들도 이 스펙트럼의 “well-done” 쪽과 “rare” 쪽 사이 어딘가에 있다.

바라바시 교수의 견해를 따르는 교재의 해결법은 “순수한” 거듭제곱 법칙을 “살짝” 변형하는 것이다.

pk=(k+ksat)−γ e−k/kcut∑k′(k′+ksat)−γ e−k′/kcutp_{k}=\frac{(k+k_{\mathrm{sat}})^{-\gamma}\,e^{-k/k_{\mathrm{cut}}}}{\sum_{k'}(k'+k_{\mathrm{sat}})^{-\gamma}\,e^{-k'/k_{\mathrm{cut}}}}

작은 kk 쪽의 포화(saturation) ksatk_{\mathrm{sat}}와 큰 kk 쪽의 절단(cutoff) kcutk_{\mathrm{cut}}을 넣은 형태다. 한국어로 된 해설로는 KIAS 웹진 호라이즌의 「척도 없는 연결망은 드문 걸까 흔한 걸까?」와 「통계와 메커니즘」을 참고할 수 있다.

논쟁의 양쪽 모두에 진지한 이유가 있다. 데이터를 볼 때는 “얼마나 넓은 범위에서, 얼마나 정확히”를 함께 물을 것

참고문헌references

  1. 『네트워크 사이언스』 (에이콘출판사, 2023), 이미진·윤진혁·이상훈·이은·조항현·김희태·손승우 옮김. 원서: Albert-László Barabási, Network Science (Cambridge University Press, 2016). 4장 「척도 없는 성질」.
  2. 『네트워크 분석』 (에이콘출판사, 2022), 손승우·엄영호·이상훈·이은·김희태·이미진 옮김. 원서: Filippo Menczer, Santo Fortunato, and Clayton A. Davis, A First Course in Network Science (Cambridge University Press, 2020). 3장 「허브」.
  3. A. Clauset, C. R. Shalizi, and M. E. J. Newman, “Power-law distributions in empirical data,” SIAM Review 51, 661–703 (2009). 코드와 자료: aaronclauset.github.io/powerlaws.
  4. A. D. Broido and A. Clauset, “Scale-free networks are rare,” Nature Communications 10, 1017 (2019).
  5. P. Holme, “Rare and everywhere: Perspectives on scale-free networks,” Nature Communications 10, 1016 (2019).
  6. I. Voitalov, P. van der Hoorn, R. van der Hofstad, and D. Krioukov, “Scale-free networks well done,” Physical Review Research 1, 033034 (2019).
  7. 로그 묶기 코드: github.com/h2jo/log_binning.