허브는 어디서 오는가 — 성장과 선호적 연결

1. 오늘의 질문: 허브는 어디서 오는가 (Where Do Hubs Come From?)

지금까지 만난 모형은 전부 정적이었다. $G(n,p)$는 $n$명을 한꺼번에 세워 놓고 동전을 던졌고, 와츠–스트로가츠는 완성된 고리를 놓고 간선을 재배선했다. 둘 다 사람 수가 처음부터 정해져 있다.

그런데 실제 교실은 그렇지 않다. 3월 2일에 서른 명이 동시에 서로를 알게 되는 게 아니라, 관계가 하나씩 시간에 걸쳐 생긴다. 전학생은 4월에 들어온다. 동아리는 5월에 만들어진다.

바라바시와 알버트(1999)의 주장은 이것이다 — 차수 분포가 거듭제곱이 되는 이유는 그래프가 어떻게 생겼는지가 아니라 어떻게 자랐는지에 있다.

2. 정의 — 성장과 선호적 연결 (Growth and Preferential Attachment)

BA 모형은 규칙이 두 개뿐이다.

규칙 ① 성장 (Growth)

시각 $t=1,2,3,\dots$마다 정점 한 개가 새로 들어온다. 들어올 때 간선 $m$개를 들고 온다. 따라서 시각 $t$에 정점은 $t$개, 간선은 대략 $mt$개, 차수 합은 $\sum_i d_i \approx 2mt$이다.

규칙 ② 선호적 연결 (Preferential Attachment)

새 정점이 상대를 고를 때, 정점 $i$를 고를 확률은 $i$의 현재 차수에 비례한다.

이게 전부다. "친구가 많은 애한테 더 붙는다" — 흔히 부익부(rich-get-richer), 머튼의 용어로는 마태 효과(Matthew effect)라 부른다.

확률의 합이 1인지 확인하는 것도 매번 해 두자. $\sum_i \Pi(i)=\sum_i d_i/\sum_j d_j = 1$ — 자동으로 1이다. 손 계산 표에서 이 열을 검산에 쓴다.

3. 손 계산 ① 일곱 명이 들어오는 동안 (Hand Simulation: Seven Arrivals)

$m=1$, 시작은 정점 1–2가 연결된 상태(차수 1, 1). 정점 3부터 7까지 다섯 명을 넣어 본다. 매 시각 모든 정점의 $\Pi$를 하나도 빼놓지 않고 쓴다.

$t=3$ — 차수 합 2 (Degree Sum 2)

뽑힌 상대: 1번. 새 차수 → 1번=2, 2번=1, 3번=1.

$t=4$ — 차수 합 4 (Degree Sum 4)

뽑힌 상대: 1번. 새 차수 → 1번=3, 나머지 1.

$t=5$ — 차수 합 6 (Degree Sum 6)

뽑힌 상대: 1번. 새 차수 → 1번=4, 나머지 1.

$t=6$ — 차수 합 8 (Degree Sum 8)

뽑힌 상대: 4번 — 확률 $1/8$짜리 사건이 실제로 일어났다. 새 차수 → 1번=4, 4번=2, 나머지 1.

$t=7$ — 차수 합 10 (Degree Sum 10)

뽑힌 상대: 5번. 최종 차수 → (4, 1, 1, 2, 2, 1, 1).

4. 손 계산 ② 왜 먼저 온 사람이 이기는가 (First-Mover Advantage)

표를 보면 1번이 계속 유리했다. 그 유리함을 식으로 뽑아 보자. 차수를 연속량으로 취급하는 연속 근사(continuum approximation)를 쓴다.

시각 $t$에서 정점 $i$가 차수를 얻는 속도는 "새 정점이 들고 온 간선 $m$개 각각이 $i$를 고를 확률"이다.

$m$이 약분되어 사라지는 것을 눈여겨보자. 변수를 분리한다.

초기 조건은 "정점 $i$는 자기가 들어온 시각 $t_i$에 차수 $m$으로 시작한다", 즉 $d_i(t_i)=m$. 따라서 $C' = m/\sqrt{t_i}$이고

지수가 $\tfrac12$라는 것이 핵심이다. 이 지수를 $\beta$라 부른다.

손으로 읽어 보기 (Reading It by Hand)

즉 차수의 격차는 실력 차이가 아니라 도착 시각의 제곱근 차이다. 모두가 똑같은 규칙을 따르는데도 그렇다.

$t_i=2$ 한 줄만 이론에서 크게 벗어난다(1.679). 이유는 모형 탓이 아니라 시작 상태 탓이다 — 정점 1과 2는 처음부터 서로 연결된 채 동시에 존재하므로 실제로는 둘 다 $t_i=1$이다. 회색 점선이 2번에 대해 $\sqrt{10000/2}=70.7$을 요구하는 것이 잘못이다.

5. 손 계산 ③ 차수 분포를 재귀로 (Exact Degree Distribution by Recursion)

이제 분포 전체를 구한다. $m=1$로 놓자. $n_k(t)$를 "시각 $t$에 차수가 정확히 $k$인 정점의 수"라 하자.

주방정식 (Master Equation)

정점 $t+1$이 들어와 간선 하나를 붙일 때 무슨 일이 일어나는지 세 가지로 나눠 센다.

분자가 $k\,n_k$인 이유: 차수 $k$인 정점이 $n_k$개 있고 각각이 확률 $k/2t$로 뽑히므로 "차수 $k$인 누군가가 뽑힐" 기댓값은 $k n_k/2t$다. 분모 $2t$는 §2에서 센 차수 합이다.

정상 해 (Stationary Solution)

"분포의 모양은 굳어지고 인원만 비례해서 늘어난다"고 가정한다. 즉 $n_k(t)=P(k)\cdot t$. 대입하면

양변에서 $P(k)t$를 빼고 $t$를 약분하면 $t$가 완전히 사라진다 — 이게 정상 해가 존재한다는 증거다.

$k=1$일 때 (The Case k = 1)

차수 0인 정점은 없으므로 $P(0)=0$. 대입하면

$k\ge 2$일 때 — 재귀식 (The Recursion)

4-5의 푸아송 재귀 $P(k)/P(k-1)=\lambda/k$와 나란히 놓고 보자. 푸아송은 비가 $k$에 반비례해서 빠르게 0으로 떨어지지만, BA는 비가 $\frac{k-1}{k+2}$로 1에 가까워진다($k=10$에서 0.75, $k=100$에서 0.971). 꼬리가 안 끊기는 이유가 여기 있다.

전부 전개하기 (Expanding Every Term)

마지막 열이 정확히 일치한다. 즉 재귀의 닫힌 해는

R로 $k=1$부터 30까지 재귀와 닫힌식을 비교하면 최대 오차가 $3.5\times10^{-18}$ — 부동소수점 잡음뿐이다.

일반 $m$ (General m)

같은 계산을 $m$에 대해 하면 $k\ge m$에서

$m$은 상수만 바꾼다. $k$에 대한 의존성 $k^{-3}$은 그대로다. 이것이 다음 절의 핵심이다.

6. 왜 $\gamma=3$인가 — CCDF로 확인 (Why Gamma Equals 3)

4-5에서 배운 대로, 로그로그에 그릴 것은 히스토그램이 아니라 CCDF다. BA는 CCDF도 닫힌식으로 나온다.

망원경 항등식 (The Telescoping Identity)

다음을 확인하자. 우변을 통분하면

따라서 $P(j)$의 꼬리 합은 중간 항이 전부 지워지고 첫 항만 남는다.

검산: $\bar F(1)=2/(1\cdot2)=1$ ✓ (모두가 차수 1 이상이다).

$\gamma$를 뽑는다 (Extracting γ)

$k$가 커지면 $k(k+1)\approx k^2$이므로

로그로그에서 기울기는 $-2$. 4-5에서 유도한 항등식 $\gamma = 1-(\text{CCDF 기울기})$를 쓰면

같은 결론을 $P(k)$ 쪽에서도 확인할 수 있다. $k^3P(k)=\dfrac{4k^2}{(k+1)(k+2)}$이므로 $k=8$에서 $\dfrac{4\cdot64}{9\cdot10}=2.844$, $k=12$에서 $\dfrac{4\cdot144}{13\cdot14}=3.165$ — 천천히 4로 수렴한다. 즉 $P(k)\to 4k^{-3}$.

7. R 검증 ① 모의가 정확식을 따라가는가 (Simulation vs Exact Formula)

손으로 얻은 $\bar F(k)=2/(k(k+1))$를 실제 모의와 맞춰 본다. $n=100000$, $m=1$, 20회 평균.

d <- igraph::degree(sample_pa(100000, power=1, m=1,
                              zero.appeal=0, directed=FALSE))
sapply(1:14, function(k) mean(d >= k))      # 모의 CCDF
2/((1:14)*(2:15))                           # 이론 CCDF

오차가 1% 이내다. 손으로 유도한 식이 맞다.

$\gamma$ 자체도 재 보자. $n=50000$:

모두 3에 붙지만 조금씩 모자란다(2.88~2.95). 왜 정확히 3이 안 나오는지는 §10에서 다룬다 — 자료 탓이 아니다.

8. R 검증 ② 성장만으로는 부족하다 (Growth Alone Is Not Enough)

규칙이 둘이었다. 어느 쪽이 진짜 원인인가? 통제 실험을 한다 — 성장은 그대로 두고 선호적 연결만 끈다.

d1 <- igraph::degree(sample_pa(5000, power=1, m=1, zero.appeal=0, directed=FALSE))  # 선호적
d0 <- igraph::degree(sample_pa(5000, power=0, m=1,                directed=FALSE))  # 균등

손으로: 균등 연결의 분포 (By Hand: The Uniform-Attachment Distribution)

같은 주방정식을 확률만 바꿔 쓴다. 이제 뽑힐 확률이 차수와 무관하므로 분자에서 $k$가 빠진다.

$n_k(t)=P(k)t$를 넣고 $t$를 약분하면

$k=1$: $P(1)=0-P(1)+1 \Rightarrow P(1)=\tfrac12$. $k\ge2$: $2P(k)=P(k-1) \Rightarrow P(k)=\tfrac12 P(k-1)$. 따라서

검산: $\sum_k (1/2)^k = 1$ ✓, $\sum_k k(1/2)^k = 2 = 2m$ ✓. 거듭제곱이 아니라 지수 분포다.

평균 차수가 똑같이 2인데 최대 차수가 100 대 14, 분산/평균이 6.94 대 1.01이다. 균등 연결의 $D=1.013$은 4-5에서 본 무작위 그래프의 1.025와 사실상 같다 — 성장만으로는 무작위와 구별되지 않는다.

9. 함정 ① igraph의 zero.appeal (The zero.appeal Trap)

args(sample_pa)
function (n, power = 1, m = NULL, out.dist = NULL, out.seq = NULL,
    out.pref = FALSE, zero.appeal = 1, directed = TRUE, ...)

왜 이렇게 크게 달라지는가? $m=1$일 때 새로 들어온 정점은 차수가 1이다. $A=1$을 더하면 그 사람의 몫이 $1$에서 $2$로 두 배가 되는 반면, 차수 100인 허브는 $100\to101$로 1%만 오른다. 보정이 약자에게만 크게 작용해 격차를 눌러 버린다.

$k=2$에서는 오히려 많고 $k\ge8$부터 적다 — 꼬리를 깎아 바닥으로 옮긴 것이다. $k=2{\sim}14$ 구간의 로그로그 기울기로 보면 이론 $-1.839$, za=0 $-1.834$, za=1 $-2.214$로 확실히 다른 직선이다.

선점 효과 지수도 달라진다 (The First-Mover Exponent Changes Too)

일반적으로 $d_i(t)\propto (t/t_i)^{\beta}$이고 $\beta = \dfrac{m}{2m+A}$다. $A=0$이면 §4의 $\beta=1/2$지만, $A=1,m=1$이면 $1/3$로 줄어든다.

같은 sample_pa(10000, power=1, m=1, directed=FALSE) 한 줄에서 1번의 기대 차수가 40.5냐 118.5냐가 갈린다. 거의 3배다.

10. 함정 ② 정확한 식조차 $\gamma=3$을 안 준다 (Even the Exact Formula Misses)

§7에서 모의값이 2.88~2.95로 3에 못 미쳤다. 자료가 부족해서일까? 확인하는 방법이 있다 — 모의를 빼고 이론식 $\bar F(k)=2/(k(k+1))$에 직접 자를 대 본다.

이유는 대수다. $\bar F(k)=\dfrac{2}{k(k+1)}=\dfrac{2}{k^2}\cdot\dfrac{1}{1+1/k}$이고, 뒤의 보정 항 $\dfrac{1}{1+1/k}$는 $k=10$에서 0.909, $k=100$에서 0.990이다. 작은 $k$에서는 이 항이 곡선을 눕혀서 기울기를 $-2$보다 완만하게 만든다.

11. BA가 못 맞히는 축 — 삼각형이 없다 (What BA Gets Wrong: No Triangles)

4-3(무작위)과 4-4(WS)를 채점했던 것과 같은 방식으로 BA를 채점한다. 먼저 군집계수.

$n=5000$, zero.appeal=0

$m=1$이면 삼각형이 정확히 0개다. §3에서 확인했듯 결과가 나무이기 때문이다. $m\ge2$여도 ER의 2~4배에 그친다. 실제 가라테는 0.2557, FMH 거대성분은 0.2840 — BA는 50~100배 모자란다.

이유는 4-3에서 $G(n,p)$가 실패한 것과 구조적으로 같다. 새 정점이 $m$개의 상대를 고를 때 그 상대들끼리 친구인지는 전혀 고려하지 않는다. "내 친구의 친구를 소개받는다"는 장치가 모형 안에 없다.

거리는 오히려 더 잘 맞힌다 (Distance Is Predicted Better)

BA는 무작위 그래프보다도 가깝다. $n$을 200배 늘리는 동안 BA 거리는 1.77배, ER은 2.12배 늘었다. 허브가 모두에게 공통인 지름길 역할을 하기 때문이다. 이 현상을 초-좁은 세상(ultra-small world)이라 부르고, 이론값은 $\ln n/\ln\ln n$으로 $G(n,p)$의 $\ln n/\ln\langle k\rangle$보다 느리게 자란다.

12. 가라테와 FMH를 BA와 대조 (Karate and FMH against BA)

같은 크기의 BA를 200번 만들어 실제 자료가 그 분포의 어디에 놓이는지 본다 (4-3·4-4와 같은 $z$ 값 방식).

가라테 (n=34, m=78)

4-3에서 $G(n,p)$는 최대 차수를 전혀 못 맞혔다(무작위 2000회 중 차수 16 이상 0회). BA는 최대 차수와 거리를 동시에 맞힌 첫 모형이다. 대신 삼각형에서 무너진다.

FMH 거대성분 (n=439, m=573)

네 축이 전부 틀렸고, 그중 둘은 방향까지 반대다. BA는 허브를 만들려고 애쓰는데 실제 FMH에는 최대 차수가 8밖에 안 된다(439명 중에!). BA는 거리를 6으로 줄이는데 실제는 16.9다.

13. 교실 적용 (Classroom Application)

① 선점 효과는 실력이 아니라 시각의 문제다 (I. First-Mover Advantage Is About Timing, Not Merit)

$d_i \propto \sqrt{t/t_i}$. 34명 학급을 BA로 보면 1번과 34번의 기대 차수 비는 $\sqrt{34}=5.83$배다. 500회 모의에서 실제 비는 4.93배(1번 평균 9.87, 34번 2.00)였고, 최고 차수가 1~5번에서 나온 비율은 95.2%, 30~34번에서 나온 비율은 0%였다.

② 원인은 성장이 아니라 되먹임이다 (II. The Cause Is Feedback, Not Growth)

§8의 통제 실험: 인원이 5000명으로 똑같이 늘어도, 상대를 균등하게 고르면 최대 차수 14·분산/평균 1.01로 무작위와 구별되지 않는다. 선호적으로 고르면 최대 차수 100·분산/평균 6.94다.

③ 개입 지점: $A$를 키우면 꼬리가 얇아진다 (III. Where to Intervene: Raising A Thins the Tail)

§9의 zero.appeal은 함정이기만 한 게 아니다. $\Pi(i)\propto d_i + A$에서 $A$는 "차수와 무관하게 누구나 갖는 기본 몫"이다. 교사가 자리를 무작위로 배정하거나 모둠을 제비뽑기로 짜는 것이 바로 $A$를 키우는 개입이다. $\gamma=3+A/m$이 커진다 = 꼬리가 얇아진다 = 쏠림이 완화된다.

$n=50000$, $m=1$

④ 한계도 그대로 말해야 한다 (IV. State the Limits Honestly)

14. 연습문제 (Exercises)

15. 해설과 답 (Solutions)

연습 1-(가) 네 시각의 $\Pi$ 전부 (Exercise 1(a): Π at All Four Time Steps)

먼저 분모. 시작이 정점 3개·간선 2개이므로 정점 $t$가 들어오려는 순간 간선은 $t-2$개, 차수 합은 $\sum_j d_j = 2(t-2)$다. $t=4\to4$, $t=5\to6$, $t=6\to8$, $t=7\to10$.

차수가 어떻게 갱신되는지도 한 줄씩:

연습 1-(나) 최종 상태 (Exercise 1(b): The Final State)

연습 1-(다) 기대 차수 — 두 방식 (Exercise 1(c): Expected Degree, Two Ways)

① 균등 연결. 시각 $t$에 이미 있는 사람이 $t-1$명이므로 2번이 뽑힐 확률은 $1/(t-1)$. 기댓값은 그냥 더하면 된다.

② 선호적 연결. 이번엔 뽑힐 확률이 $d_2/\sum_j d_j$로 자기 차수에 비례하므로 더할 수 없다. 대신 $\mathbb{E}[d_2(t+1)] = \mathbb{E}[d_2(t)] + \dfrac{\mathbb{E}[d_2(t)]}{\sum_j d_j} = \mathbb{E}[d_2(t)]\left(1+\dfrac{1}{\sum_j d_j}\right)$ — 곱셈이 된다.

연습 2-(가) $k=1\sim6$의 기대 인원 (Exercise 2(a): Expected Counts for k = 1 to 6)