차수 분포를 읽는 법 — '허브가 있다'를 숫자로

1. 오늘의 질문: 느낌을 숫자로 (From a Feeling to a Number)

지난 두 단원의 성적표를 한 장으로 합치면 이렇게 된다.

WS는 손잡이 하나로 거리와 군집을 동시에 맞혔다. 그런데 오른쪽 두 열은 그대로다. 격자는 모두가 차수 4라 분산이 정확히 0이고, 거리·군집을 맞히는 $p \approx 0.1$에서도 분산은 겨우 0.73이다. 손잡이를 끝까지 돌려 $p=1$로 만들어도 3.41에서 멈춘다. 실제는 15.04다. 네 배 넘게 모자란다.

이 차이가 뭘 뜻하는지는 이미 안다. 가라테에는 차수 17인 사람(34번, 사범)과 차수 16인 사람(1번, 관장)이 있다. 학급으로 치면 반 전체의 절반과 이름을 트고 지내는 학생이다. 그런 사람이 있는 반과 없는 반은 다른 반이다.

2. 정의 — 차수 분포와 CCDF (Degree Distribution and the CCDF)

2-1. 세 가지를 구별한다 (Distinguishing Three Things)

정점이 $n$개인 그래프에서 $\deg(i)$를 $i$번의 차수라 하자. 세 가지 함수를 정의한다.

셋은 서로에게서 복원된다.

검산은 두 개를 늘 같이 쓴다.

2-2. 거듭제곱 법칙과 지수 $\gamma$ (Power Laws and the Exponent γ)

차수 분포가 거듭제곱 법칙(power law)을 따른다는 것은

이라는 뜻이다. $\gamma$를 지수(exponent)라 부른다. 왜 이 모양이 특별한가? 양변에 로그를 씌우면

즉 로그–로그 축에서 직선이 된다. 기울기가 $-\gamma$다. 직선이라는 것은 눈으로 판정하기 가장 쉬운 모양이고, 기울기 하나로 요약된다는 뜻이기도 하다.

3. 손 계산 ① 가라테의 CCDF — 34명 전부 세기 (The Karate CCDF, Counted by Hand)

가라테 클럽 34명의 차수를 작은 것부터 늘어놓는다.

1  2 2 2 2 2 2 2 2 2 2 2  3 3 3 3 3 3  4 4 4 4 4 4  5 5 5  6 6  9  10  12  16  17

3-1. $n_k$를 센다 (Counting n_k)

같은 값끼리 묶어 세면 이렇게 된다. 값이 없는 차수(7, 8, 11, 13, 14, 15)는 $n_k=0$이다 — 빠뜨리지 말고 적어 둔다.

검산 1 — 사람 수: 0인 칸도 전부 더한다.

검산 2 — 악수 정리: 각 항을 전부 전개한다.

3-2. CCDF를 만든다 — 위에서부터 누적 (Building the CCDF from the Top Down)

$\bar F(k)$를 만드는 가장 안전한 방법은 가장 큰 차수부터 아래로 누적하는 것이다. $N(\ge k)$를 "차수 $k$ 이상인 사람 수"라 하면 $N(\ge k) = N(\ge k{+}1) + n_k$다.

검산 3: 가장 아래 $\bar F(1) = 1$이어야 한다 — 모두가 차수 1 이상이니까(가라테에는 고립 정점이 없다). $\checkmark$

3-3. 로그를 씌운다 (Taking Logarithms)

$n_k \neq 0$인 차수만 골라 $\log_{10}$을 취한다. 이게 로그–로그 그림에 찍히는 점들이다.

점이 11개다. 34명짜리 네트워크에서 나온 점이 11개. 이 숫자를 기억해 두자 — §12에서 다시 쓴다.

4. 왜 히스토그램이 아니라 CCDF인가 (Why Not a Histogram)

§3 표에서 이미 이유가 보인다. $k=7,8,11,13,14,15$에서 $n_k=0$이었다. $P(k)=0$이면 $\log P(k) = \log 0 = -\infty$라서 그 점은 로그–로그 그림에 아예 찍히지 않는다.

가라테는 작아서 구멍이 6개뿐이었다. 큰 네트워크에서는 이게 재앙이 된다. BA 모형(다음 단원)으로 만든 $n=5000$ 네트워크의 차수 30 이상 구간을 실제로 세어 보자.

차수 30~59 구간 30칸 중 18칸이 0이다. 그 구간에는 사람이 19명이나 있는데도 그렇다. 더 위로 가면 완전히 무너진다 — 차수 60~80 구간 21칸은 전부 0인데, 차수 60 이상인 사람은 3명 있다. 어디에 있는가? 82, 82, 135에 있다.

5. 손 계산 ② 무작위였다면 몇 명이었을까 (What Poisson Would Have Predicted)

"허브가 있다"를 재는 가장 직접적인 방법: 같은 크기·같은 간선 수의 무작위 그래프라면 그런 사람이 몇 명 나왔을까를 계산해서 실제와 비교하는 것이다.

4-1에서 $G(n,p)$의 차수가 근사적으로 푸아송을 따른다는 걸 봤다.

5-1. 재귀로 손 계산한다 (Hand Calculation by Recursion)

$k!$를 매번 계산할 필요는 없다. 이웃한 항끼리 비를 보면

이므로 $P(0)=e^{-\lambda}$에서 시작해 $\lambda/k$를 곱해 가면 된다.

5-2. 꼬리 전체를 한 번에 (The Whole Tail at Once)

낱개보다 꼬리 전체를 묻는 게 해석이 쉽다. "차수 16 이상인 사람"의 기대 인원은

실제는 2명이다. 뒤집어 읽으면 더 선명하다.

5-3. 같은 계산을 FMH에 (The Same Calculation on FMH)

FMH(가상의 고등학교, $n=1461$, $m=974$, $\lambda = 4/3 = 1.3333$)에 똑같이 해 보면 다른 이야기가 나온다.

두 끝이 동시에 부풀어 있다.

• 왼쪽 끝: 친구가 0명인 학생이 524명 — 전교생의 35.9%다. 무작위였다면 385명(26.4%)이어야 했다. 1.36배 많다.
• 오른쪽 끝: 차수 8인 학생 2명은 무작위 기대치 0.095명의 21배다. 꼬리 전체로 보면 $P(K\ge8)\times1461 = 0.112$명 기대에 실제 2명.

그러나 가라테와 결정적으로 다른 점이 있다. FMH의 최대 차수는 8이다. 1461명이나 되는데 친구가 9명 이상인 학생이 단 한 명도 없다. 가라테는 34명 중에 17명과 연결된 사람이 있었는데 말이다.

6. 손 계산 ③ 로그–로그 기울기에서 $\gamma$를 뽑는다 — 두 점으로 (Slope to Exponent)

§3-3 표에서 두 점만 골라 기울기를 내 보자. 꼬리를 대표하는 두 점으로 $k=4$(절반 지점)와 $k=17$(끝점)을 잡는다.

점 1: $k=4$, $\bar F(4) = 16/34 = 0.470588$

점 2: $k=17$, $\bar F(17) = 1/34 = 0.029412$

기울기는 세로 변화 나누기 가로 변화다.

그리고 §7에서 증명할 관계를 쓰면

7. 왜 $\gamma = 1 - \text{기울기}$인가 (Why the CCDF Slope Is One Less)

§6에서 쓴 관계를 증명한다. 이게 오늘 유일한 "유도"다.

가정: 어떤 $k_{\min}$ 이상에서 $P(k) = C k^{-\gamma}$이고 $\gamma > 1$이다.

CCDF는 정의상 꼬리의 합이다.

$k$가 충분히 크면 이 합은 적분으로 근사된다.

양변에 로그를 씌운다.

즉 CCDF의 로그–로그 기울기는 $-(\gamma-1) = 1-\gamma$다. 뒤집으면

7-1. 수치로 확인 (Numerical Check)

순수한 거듭제곱 $P(k) \propto k^{-\gamma}$를 $k=1,\dots,10^5$에서 만들어 CCDF의 기울기를 실제로 재 보면:

세 경우 모두 $1-\text{기울기}$가 참값으로 돌아온다. 그리고 $k$가 클수록 정확해진다 — 합을 적분으로 바꾼 근사가 큰 $k$에서 더 잘 맞기 때문이다.

8. R 검증 ① 같은 분포를 세 가지 눈으로 (Three Views of One Distribution)

같은 자료를 히스토그램 / 선형 CCDF / 로그–로그 CCDF로 각각 보면 결론이 얼마나 달라지는지 본다. 비교 대상은 두 개다.

set.seed(301)
gba <- sample_pa(5000, power=1, m=2, directed=FALSE)  # BA (다음 단원)
ger <- sample_gnp(5000, 4/4999)                       # ER 무작위
c(mean=mean(degree(gba)), max=max(degree(gba)), var=var(degree(gba)))
#   mean      max      var
#  3.9988 135.0000  21.1654
c(mean=mean(degree(ger)), max=max(degree(ger)), var=var(degree(ger)))
#   mean      max      var
#  4.0020  15.0000   4.1040

평균은 둘 다 4.0으로 똑같다. 간선 수도 사실상 같다. 그런데:

최대 차수가 9배 차이 난다. 평균이 같은데.

8-1. 세 눈으로 본 CCDF (The CCDF Through Three Lenses)

$k$가 두 배씩 커질 때 BA의 CCDF를 보라: $0.3344 \to 0.0944 \to 0.0204 \to 0.0040 \to 0.0006$. 매번 대략 4분의 1씩 준다. $k$가 2배일 때 $2^{-2}$배 — 이게 로그–로그에서 기울기 $-2$, 곧 $\gamma \approx 3$이라는 뜻이다(§7).

ER은 $k=16$에서 절벽이다. 5000명 중 차수 16 이상이 한 명도 없다. 로그–로그 그림에서는 아예 선이 끊긴다.

9. R 검증 ② 실제 학교 두 곳 (Two Real Schools)

그림에서 읽을 것은 세 가지다.

1. 가라테는 푸아송보다 위에 있다. $k \ge 9$ 구간에서 실제 곡선이 푸아송 점선보다 한참 위다. 꼬리가 두껍다는 뜻이고, §5의 "1153개 학급"이 그림으로 보이는 것이다.
2. 그런데 점이 너무 적다. $k \ge 9$에 있는 점은 $k=9,10,12,16,17$ 다섯 개, 사람으로는 5명이다. 직선을 긋기에 충분한가? 이 질문이 §12다.
3. FMH는 두껍지만 짧다. 왼쪽(작은 $k$)에서는 푸아송보다 위에 있는데 $k=8$에서 그냥 끝난다. 거듭제곱의 특징인 "계속 이어지는 꼬리"가 없다.

회귀 기울기로 요약하면:

BA만 이론값($\gamma=3$)에 가깝게 나왔고, 나머지는 신뢰할 만한 점 개수가 아니다. 특히 ER에서도 "$\gamma=4.503$"이라는 숫자가 나오기는 한다는 데 주목하자. 푸아송 자료인데도 말이다. 이것이 §11의 주제다.

10. 함정 ① 구간을 어떻게 나누느냐가 결론을 바꾼다 (Binning Changes the Conclusion)

히스토그램을 굳이 쓰겠다면 구간(bin)을 넓게 잡아 구멍을 메우는 방법이 있다. 그런데 어떻게 넓히느냐가 그림을 완전히 바꾼다. 같은 BA 자료다.

10-1. 등간격 구간 — 폭 10씩 (Equal-Width Bins)

첫 칸에 95.3%가 들어갔다. 정작 알고 싶은 구조(차수 1과 2와 4의 차이)가 한 칸 안에서 전부 뭉개졌다. 그리고 오른쪽은 여전히 0투성이다. 양쪽 모두 실패다.

10-2. 로그 구간 — 2배씩 (Logarithmic Bins)

이제 모든 칸에 사람이 있고(첫 칸 제외 — BA는 $m=2$라 최소 차수가 2다), 인원이 칸마다 대략 일정한 비율로 준다: $2306 \to 1550 \to 786 \to 269 \to 70 \to 16 \to 2 \to 1$. 이웃 칸의 비를 보면 0.672 → 0.507 → 0.342 → 0.260 → 0.229로 4분의 1을 향해 내려간다(마지막 두 칸은 사람이 2명, 1명뿐이라 요동친다). $k$가 2배일 때 인원이 $1/4$이라는 건 §8에서 본 것과 같은 이야기다 — $\gamma \approx 3$이면 폭 $(a, 2a]$ 칸의 인원이 $a^{-2}$에 비례하기 때문이다.

11. 함정 ② 무엇이든 거듭제곱으로 적합된다 (Anything Can Be Fitted)

igraph에는 최대우도로 $\gamma$와 $k_{\min}$을 동시에 추정하는 함수가 있다. CCDF 회귀보다 통계적으로 옳은 방법이다(§4의 상관 문제가 없다).

fit_power_law(degree(gba), implementation="plfit", p.value=TRUE)

네 자료에 전부 돌린 결과다.

11-1. 이 표를 읽는 법 (How to Read This Table)

ER 줄을 보라. 우리가 직접 만든 푸아송 자료인데도 $\alpha = 14.738$이라는 답이 나왔다. 함수는 거절하지 않는다. 언제나 숫자를 준다.

그렇다면 그 숫자가 무의미하다는 건 어떻게 아는가? 세 가지 신호가 있다.

1. $\alpha$가 터무니없이 크다. 실제 네트워크의 $\gamma$는 보통 2~3 사이다. 14.7은 "$k$가 2배 되면 확률이 $2^{-14.74} \approx 1/27000$배"라는 뜻으로, 사실상 지수적으로 끊긴다는 말이다 — 거듭제곱이 아니라 절벽의 서술이다.
2. $k_{\min}$이 너무 높아 자료의 1%만 쓴다. 5000개 중 47개. 그 47개만 보면 어떤 곡선이든 직선처럼 보인다.
3. KS $p = 0.041$로 실제로 기각된다. 유의수준 5%에서 "거듭제곱이다"라는 가설이 탈락했다.

그리고 가라테 줄을 보라. $p = 0.119$로 기각되지 않았다. 그런데 이것을 "가라테는 거듭제곱이다"의 증거로 읽으면 안 된다.

12. 그래서 가라테는 척도 없는 네트워크인가 (Is Karate Scale-Free?)

정직하게 답하자. 그 질문에는 답할 수 없다. 이유는 셋이다.

12-1. 그래도 말할 수 있는 것 (What Can Still Be Said)

"척도 없다"는 말은 못 한다. 그런데 우리가 실제로 알고 싶은 것은 그게 아니다. 알고 싶은 건 "이 반의 쏠림이 우연으로 설명되는가"이고, 그건 답할 수 있다.

같은 크기($n=34$, $m=78$)의 무작위 그래프 200개를 만들어 각각에 같은 최대우도 적합을 돌린다.

set.seed(502)
er34 <- replicate(200, fit_power_law(degree(sample_gnm(34,78)),
                                     implementation="plfit")$alpha)
range(er34)          # 2.623139 13.896558
mean(er34)           # 6.550893
sum(er34 <= 2.126278)# 0    <- 가라테보다 꼬리가 두꺼운 무작위 그래프의 수

13. 한 줄로 줄인 지표 — 분산/평균 (The Dispersion Index)

매번 CCDF를 그릴 수는 없다. 쏠림을 수 하나로 요약해야 할 때가 있다. 가장 쓸 만한 것이 분산지수다.

왜 이게 좋은가? 4-1 §8에서 본 푸아송의 성질 때문이다 — 푸아송은 분산이 평균과 같다. 따라서 $D = 1$이 "무작위 기준선"이 된다. 눈금이 저절로 붙는다.

0(완전 균등) → 1(무작위) → 3 → 5(극단)로 한 줄에 세워진다. 격자가 정확히 0인 것도 확인해 두자 — 모두가 차수 4이므로 분산이 0이다.

13-1. 같이 볼 지표 — 연결 점유율 (A Companion Measure: Share of Ties)

$D$는 단위가 없어 좋지만 직관적이진 않다. 학부모나 동료 교사에게 설명할 때는 "상위 몇 %가 관계의 몇 %를 갖는가"가 훨씬 잘 통한다.

여기서 "관계의 몫"은 차수 합 $\sum_i \deg(i) = 2m$에서 차지하는 비율로 잰다. 차수를 그냥 더하면 되므로 덧셈이 성립하고, 어떤 묶음에도 적용된다.

격자에서 상위 10%가 정확히 10%를 갖는 게 완전 평등의 정의다(1등의 몫도 $1/n$과 같다). 가라테에서는 상위 20%(7명)가 관계의 절반을 갖고, 단 한 사람이 10.9% — 평등할 때 몫(2.94%)의 3.7배 — 를 갖는다.

14. 교실 적용 (Classroom Application)

15. 연습문제 (Exercises)

16. 해설과 답 (Solutions)

16-1. 연습문제 1 (a) — 표를 전부 채운다 (Exercise 1(a): Filling In the Table)

무엇을 세는가. 12개의 값 1 1 2 2 2 3 3 3 4 5 7 9을 놓고, 각 $k$마다 ① 정확히 $k$인 개수($n_k$) ② $k$ 이상인 개수($N(\ge k)$)를 센다. $N(\ge k)$는 위에서부터 누적하는 것이 안전하다.

검산 1 — 사람 수. 0인 칸까지 전부 더한다.

검산 2 — 악수 정리. 0인 항도 생략하지 않는다.

16-2. 연습문제 1 (b) — 푸아송이라면 (Exercise 1(b): If It Were Poisson)

무엇을 곱하는가. $\lambda = 3.5$로 $P(0) = e^{-3.5}$를 구하고, $P(k) = P(k-1) \times \dfrac{3.5}{k}$를 반복한다.

16-3. 연습문제 1 (c) — 몇 개 학급당 한 명인가 (Exercise 1(c): One in How Many Classes)

무엇을 계산하는가. 낱개 $P(9)$가 아니라 꼬리 전체 $P(K \ge 9)$를 쓴다. "차수가 정확히 9"보다 "9 이상"이 물음에 맞는 사건이다.

16-4. 연습문제 1 (d) — 두 점 기울기 (Exercise 1(d): The Two-Point Slope)

무엇을 나누는가. (a) 표에서 두 점을 꺼낸다.

비율로 검산. CCDF는 $7/12 \to 1/12$, 즉 $1/7$배. $k$는 $3 \to 9$, 즉 3배.

16-5. 연습문제 1 (e) — 분산지수 (Exercise 1(e): The Index of Dispersion)

무엇을 계산하는가. 표본분산이므로 $n-1=11$로 나눈다. 편차 제곱을 전부 전개한다 ($\bar k = 3.5$).

16-6. 연습문제 2 (a) — CCDF를 말로 옮기기 (Exercise 2(a): Putting the CCDF into Words)

무엇을 읽는가. $\bar F(5) = 0.294118 = 10/34$. 분자 10이 인원이다.

16-7. 연습문제 2 (b)(c) — $\gamma$가 흔들린다 (Exercise 2(b)(c): γ Is Unstable)

무엇을 나누는가. §3-3 표에서 세 쌍을 꺼내 같은 계산을 반복한다.

$k=5\to17$ 줄의 검산이 특히 쉽다. CCDF가 $10/34 \to 1/34$, 정확히 $1/10$배다. 그러므로 $\Delta\log_{10}\bar F = -1$이 딱 떨어진다. $k$는 $17/5 = 3.4$배이므로

16-8. 연습문제 2 (d) — 그래서 무엇을 쓸 것인가 (Exercise 2(d): So What Should We Use)

무엇을 모으는가. 같은 34명 자료에서 나온 $\gamma$ 추정치 전부를 한 줄에 세운다.

다음 단원 예고 — 4-6. 오늘 우리는 차수 분포를 재는 법을 익혔고, 가라테와 FMH가 무작위와 다르다는 것을 확인했다. 그런데 왜 그런 분포가 생기는지는 묻지 않았다.
§8에서 슬쩍 꺼내 쓴 sample_pa — 이게 바라바시–알버트(BA) 모형이다. "이미 친구가 많은 사람이 새 친구를 더 얻는다"는 규칙 하나로 $\gamma = 3$의 거듭제곱 분포를 만든다. 4-6에서는 그 규칙을 손으로 굴려 보고, 먼저 들어온 사람이 유리한가(first-mover advantage)를 직접 확인한다 — 3월에 만들어진 관계가 1년을 지배하는지에 대한 질문이다.