와츠·스트로가츠 모형 — 지름길 몇 개가 세상을 좁힌다

1. 오늘의 질문: 두 극단 사이에 손잡이를 단다 (A Knob Between Two Extremes)

4-3에서 우리는 $G(n,p)$의 성적표를 두 축으로 나눠 받았다.

실제 사회망은 두 성질을 동시에 가진다. 좁고, 뭉쳐 있다. $G(n,p)$는 앞의 절반만 준다. 그렇다면 뒤의 절반을 확실히 주는 모형에서 출발하면 어떨까?

그런 모형이 있다. 고리 격자(ring lattice)다. 학생들을 원형으로 둥글게 앉히고 양옆 가까운 몇 명씩만 친구로 잇는다. 옆자리끼리 서로 아는 게 당연하니 삼각형이 넘쳐난다. 하지만 반대편 학생에게 소식을 전하려면 원을 반 바퀴 돌아야 한다.

2. 정의 — 고리 격자와 재배선 (Ring Lattice and Rewiring)

2-1. 고리 격자 $C_n^{\,\mathrm{nei}}$ (Ring Lattice)

정점 $1,2,\dots,n$을 시계 방향으로 원에 놓는다. 고리 거리(ring distance)를

로 정의하고, 인접행렬을

로 놓는다. 즉 양옆으로 $\mathrm{nei}$명씩 잇는다. 그러면

2-2. 재배선 (Rewiring)

격자의 각 간선을 훑으면서 확률 $p$로 한쪽 끝을 무작위 정점으로 갈아 끼운다. 갈아 끼워진 간선은 원을 가로지르는 지름길(shortcut)이 된다.

3. 손 계산 ① 고리 격자의 군집계수 — 여섯 쌍 전부 (Clustering of the Ring Lattice)

$n=20,\ \mathrm{nei}=2$로 두고 1번 학생의 지역 군집계수를 손으로 구한다.

1번의 이웃은 고리 거리 1, 2 이내의 정점이다:

이웃 집합 $N(1)=\{19,\,20,\,2,\,3\}$, 차수 $k_1=4$. 지역 군집계수의 정의는

여섯 쌍을 하나도 빠뜨리지 않고 전부 확인한다. 두 이웃 $u,v$가 이어져 있으려면 $\rho(u,v)\le 2$여야 한다.

0인 항까지 전부 더하면

3-1. 일반 공식으로 (The General Formula)

이 셈에는 규칙이 있다. $i$의 이웃 $2\,\mathrm{nei}$명 중 서로 이어진 쌍의 수는

이고 전체 쌍은 $\binom{2\,\mathrm{nei}}{2}=\mathrm{nei}(2\,\mathrm{nei}-1)$이므로

방금 손으로 센 값과 맞는지 검산한다. $\mathrm{nei}=2$: 분자 $3\cdot 2\cdot 1/2=3$ — 위 표에서 O가 정확히 3개였다. 분모 $2\cdot 3=6$ ✓. $C=3/6=0.5$ ✓.

4. 손 계산 ② 고리 격자의 평균 거리 — 홉별 인원 전부 (Distance in the Ring Lattice)

같은 격자($n=20,\ \mathrm{nei}=2$)에서 1번 학생의 평균 거리를 구한다.

한 홉에 최대 $\mathrm{nei}=2$칸까지 갈 수 있으므로, 고리 거리 $\rho$만큼 떨어진 정점까지의 최단 거리(홉 수)는

1번에서 본 나머지 19명을 고리 거리별로 전부 늘어놓는다. 고리 거리 $\rho$인 정점은 시계·반시계 두 방향에 하나씩 2명씩인데, $\rho=10$만 정반대편 한 사람(11번)뿐이다.

홉별로 다시 묶으면 이렇게 된다 — 같은 인원(4명)이 홉마다 반복된다는 게 격자의 본질이다.

모든 정점이 대칭이므로 이 값이 곧 전체 평균 거리다.

> g <- sample_smallworld(1, 20, 2, 0)
> mean_distance(g);  diameter(g);  transitivity(g)
[1] 2.894736842
[1] 5
[1] 0.5

5. 격자는 $n$이 커지면 절망적으로 멀다 (The Lattice Scales Badly)

4-3의 핵심은 무작위 그래프의 거리가 $\ln n$으로 아주 천천히 자란다는 것이었다. 격자는 정반대다.

$n$을 50배 키우면 격자의 거리는 43배가 되고, 무작위 그래프의 거리는 2.3배가 된다. $n=1000$에서 격자는 무작위보다 25배 멀다.

한편 $C$는 $n$이 아무리 커져도 0.5로 못 박혀 있다. 격자는 뭉침은 완벽하고 거리는 재앙이다. 정확히 $G(n,p)$의 반대다.

6. 손 계산 ③ 지름길 20개의 위력 (The Power of Twenty Shortcuts)

재배선의 효과를 이해하려면 먼저 지름길 하나가 무엇을 하는지를 봐야 한다. 설명을 깨끗하게 하려고 여기서는 재배선 대신 추가를 쓴다 — 기존 간선은 하나도 건드리지 않고 무작위 간선만 몇 개 더한다. 그러면 지름길의 효과만 떼어 볼 수 있다.

$n=1000,\ \mathrm{nei}=5$ 격자에서 출발한다. 원래 값은 $m=5000,\ L_0=50.4505,\ C_0=2/3$.

간선 하나를 더했을 뿐인데 평균 거리가 18% 사라진다. 간선 20개(전체의 0.4%)면 거리가 4분의 1로 줄고, 군집계수는 0.89%만 준다.

6-1. $C=0.6607$은 어디서 나왔나 — 분자와 분모를 직접 센다 (Counting the Numerator and Denominator)

군집계수의 전역 정의는 $C=3T/P_2$다. 간선 20개를 추가했을 때 분자 $T$와 분모 $P_2$가 각각 어떻게 되는지 손으로 센다.

분자 $T$(삼각형 수) — 간선을 추가하면 삼각형은 절대 줄지 않는다. 새 간선이 우연히 새 삼각형을 만들 수는 있지만, $n=1000$에서 무작위로 고른 두 점이 공통 이웃을 가질 확률은 지극히 작다. 그러므로

분모 $P_2$(연결 삼중쌍 수) — 이건 확실히 는다. 격자에서는 전원이 차수 10이므로

새 간선 하나는 양 끝의 차수를 10에서 11로 올린다. 한쪽 끝에서 늘어나는 삼중쌍은

양 끝이 있으니 간선 하나당 $10+10=20$. 간선 20개면

따라서

> # 20회 평균 실측
> T = 10000.8   P2 = 45400.9   C = 0.6608327
#   손 계산 예측: T = 10000, P2 = 45400, C = 0.6607930  →  소수 셋째 자리까지 일치

※ 위 표의 $L$ 값은 난수 한 번의 결과다. 20회 반복 평균은 13.31로, 12~14 사이에서 흔들린다. 결론(4분의 1로 줄어든다)은 바뀌지 않는다.

7. 손 계산 ④ 왜 군집계수는 $(1-p)^3$인가 — 여덟 경우 전부 (Why the Cube)

이제 진짜 재배선으로 돌아온다. 교과서는 재배선 후의 군집계수를

이라고 말한다. 왜 세제곱인가?

격자 안의 삼각형 하나를 골라 보자 — 예컨대 $n=20,\ \mathrm{nei}=2$에서 $\{1,2,3\}$. 이 삼각형은 간선 세 개로 이루어진다:

1 — 2  2 — 3  1 — 3

재배선은 각 간선을 독립적으로 훑으면서 확률 $p$로 한쪽 끝을 옮긴다. 그러면 이 삼각형이 살아남으려면 세 간선이 모두 살아남아야 한다. 셋 중 하나라도 옮겨지면 삼각형은 끊긴다.

$p=0.1$로 놓고 여덟 가지 경우를 하나도 빼놓지 않고 전개한다. (S = 살아남음, 확률 $1-p=0.9$ / R = 재배선됨, 확률 $p=0.1$)

검산: $0.729+3(0.081)+3(0.009)+0.001 = 0.729+0.243+0.027+0.001 = 1.000$ ✓

삼각형이 살아남는 경우는 단 하나(1번 줄)뿐이다. 그러므로

그리고 §6에서 확인했듯 분모 $P_2$는 거의 안 변한다. 재배선은 간선 수를 유지하므로 차수의 합은 그대로고, 차수가 흩어지면서 $\sum\binom{k_i}{2}$가 조금 늘 뿐이다:

분모는 $p$가 1까지 가도 11%밖에 안 움직이는데 분자는 1.7%까지 떨어진다. 그러니 $C(p)/C(0)$의 거동은 사실상 전부 삼각형 이야기다. 따라서

8. R 검증 ① 두 곡선이 다른 속도로 무너진다 (Two Curves, Two Speeds)

$n=1000,\ \mathrm{nei}=5$(차수 10, 간선 5000개)에서 $p$를 훑는다. 각 $p$마다 20회 평균.

ps <- c(0, 1e-4, 3e-4, 1e-3, 3e-3, 0.01, 0.03, 0.1, 0.3, 1)
set.seed(202)
res <- t(sapply(ps, function(p) {
  r <- replicate(20, { g <- sample_smallworld(1, 1000, 5, p)
                       c(mean_distance(g), transitivity(g)) })
  rowMeans(r) }))

※ 둘째 열 $p\,m$은 교과서 기준(간선 단위 재배선)의 기댓값이다. igraph의 실제 구현에서는 그 약 2배의 간선이 건드려진다 — 이유는 §10에서 밝힌다.

양끝 검산 — 두 극단이 우리가 아는 값과 맞는지 확인한다.

즉 $p=1$의 WS 그래프는 4-3에서 배운 무작위 그래프 그 자체다. 우리는 지금 4-3의 세계와 격자의 세계를 잇는 다리 위를 걷고 있고, 양쪽 끝이 제대로 붙어 있음을 확인했다.

9. 좁은 세상 구간 (The Small-World Regime)

표의 $p=0.01$ 줄을 다시 읽는다.

왜 이런 구간이 존재하는가는 두 곡선의 기울기를 비교하면 보인다.

$p$가 작을수록 비대칭이 극단적이다. $p=0.001$에서는 거리가 군집보다 97배 빠르게 무너진다.

10. R 구현 함정 — igraph는 $(1-p)^6$이다 (An Implementation Trap)

여기서 실측과 이론을 맞춰 보다가 이상한 것을 발견했다. §7에서 유도한 $(1-p)^3$과 §8의 실측 $C/C_0$를 나란히 놓으면 중간 $p$에서 심하게 어긋난다.

오차 0.25는 무시할 수 없다. 실측이 이론보다 훨씬 빨리 떨어진다. §7의 표에서 분모 $P_2$는 거의 안 움직인다는 걸 이미 확인했으므로, 문제는 분자(삼각형)가 예상보다 빨리 죽는다는 데 있다.

10-1. 결정적 실험 — 원래 간선이 몇 % 살아남는지 직접 센다 (The Decisive Test)

§7의 논증은 "간선 하나가 살아남을 확률 $=1-p$"를 전제로 했다. 그것부터 확인한다. 격자의 간선 목록을 저장해 두고, 재배선 후에도 남아 있는 간선의 비율을 센다.

E0 <- apply(as_edgelist(lat), 1, function(e) paste(sort(e), collapse="-"))
g  <- sample_smallworld(1, n, nei, p)
E1 <- apply(as_edgelist(g),   1, function(e) paste(sort(e), collapse="-"))
mean(E0 %in% E1)          # 원래 간선의 생존 비율

소수 넷째 자리까지 $(1-p)^2$다. 우연이 아니다.

10-2. $(1-p)^6$으로 다시 맞춰 본다 (Refitting with the Sixth Power)

$(1-p)^6$의 평균 오차는 0.0026, $(1-p)^3$의 37분의 1이다. 논쟁의 여지가 없다.

$p\ge 0.3$에서 실측이 $(1-p)^6$보다 조금 높아지는 것도 설명된다. 그쯤 되면 재배선된 간선이 워낙 많아 새 삼각형이 우연히 생기기 시작한다. 극단인 $p=1$에서 실측 0.0149는 격자 삼각형의 잔재가 아니라 무작위 그래프가 원래 갖는 군집계수($C=p_{\text{밀도}}=0.01001$, 4-3 §6)다.

11. 왜 거리만 그렇게 빨리 무너지는가 (Why Only Distance Collapses)

$p=0.001$에서 거리는 군집보다 97배 빠르게 무너졌다(§9). 이 비대칭의 원인은 간선 하나가 두 지표에 미치는 영향의 사정거리가 다르다는 데 있다.

11-1. 지름길 하나가 몇 쌍을 살리는가 — 어림 계산 (A Back-of-Envelope Count)

$n=1000,\ \mathrm{nei}=5$ 고리에서 정점 1과 정점 501을 잇는 지름길 하나를 놓았다고 하자. 원래 이 두 점 사이의 거리는 $\lceil 500/5\rceil=100$홉이었는데 이제 1홉이다.

이득을 보는 것은 이 두 점만이 아니다. 1번 근처에 있는 사람들과 501번 근처에 있는 사람들이 전부 이 다리를 건넌다. 고리에서 1번으로부터 $t$홉 안에 있는 사람은 대략 $2\,\mathrm{nei}\,t=10t$명이다. $t=20$까지만 쳐도 양쪽에 200명씩이니, 이 다리 하나로 최단 경로가 짧아지는 쌍은 대략 $200\times 200=\mathbf{40000}$쌍이다.

전체 쌍 수는 $\binom{1000}{2}=499500$. 즉 지름길 하나가 전체 쌍의 8%를 건드린다.

반대쪽을 세어 본다. 고리 거리 $\rho$인 간선 $\{i,j\}$가 낀 삼각형의 수는 $i$와 $j$의 공통 이웃 수와 같고, 세어 보면 $2\,\mathrm{nei}-\rho-1$이다.

검산: 모든 간선에 대해 더하면 $1000(8+7+6+5+4)=30000=3T=3\times 10000$ ✓ (삼각형 하나는 간선 3개에서 각각 세어지므로 $3T$가 나와야 한다.)

그러므로 간선 하나를 옮겨서 부술 수 있는 삼각형은 평균 6개 — 전체 10000개 중 0.06%다.

이것이 §9에서 본 "97배"의 정체다. (어림 계산이라 정확히 97은 아니지만, 두 자릿수 배율이라는 결론은 같다.)

12. 가라테를 WS 지도에 올린다 (Karate on the WS Map)

WS 모형은 $p$를 0에서 1까지 움직이면 $(L,C)$ 평면에 곡선 하나를 그린다. 실제 망은 그 곡선 위에 있을까?

가라테 클럽: $n=34,\ m=78,\ \lambda=4.588$. 격자로 흉내 내려면 차수를 맞춰야 하므로 $2\,\mathrm{nei}\approx 4.588$ → $\mathrm{nei}=2$.

12-1. WS는 가라테를 얼마나 잘 설명했나 (How Well Did WS Do)

먼저 잘한 점. 4-3에서 $G(n,p)$는 가라테의 $C$를 1.8배 과소평가했고 격자는 2배 과대평가했다. WS는 $p$를 0.1 근처로 돌리면 $C=0.2924$ — 실제 0.2557과 14% 차이다. 어느 극단보다도 훨씬 낫다.

이제 못한 점. $C$를 맞추는 $p=0.1$에서 $L=2.98$인데 실제는 2.41이다. 게다가 더 이상한 것이 있다.

왜? WS는 차수를 거의 균일하게 유지하기 때문이다. 격자에서는 전원이 차수 4였고, 재배선을 해도 차수는 4 근처에서만 흔들린다. 그런데 실제 가라테에는 차수 17짜리 두목이 있다. 허브는 자기에게 연결된 모든 사람을 2홉 안에 묶어 버리므로, 허브가 있으면 같은 밀도에서도 거리가 더 짧아진다. §14에서 숫자로 확인한다.

13. FMH는 지도 밖에 있다 (FMH Is Off the Map)

FMH 거대 컴포넌트: $n=439,\ m=573,\ \lambda=2.610$. 차수를 맞추면 $2\,\mathrm{nei}\approx 2.61$ → $\mathrm{nei}=1$.

그런데 §3에서 경고했듯 $\mathrm{nei}=1$인 고리 격자에는 삼각형이 하나도 없다:

출발점의 군집계수가 0이면, 재배선을 아무리 해도 $C$는 올라갈 데가 없다.

WS 곡선 전체에서 $C$의 최댓값이 0.0043이다. 실제는 0.2840 — 66배다. $p$를 어디에 놓아도 실제 점 근처에 갈 수 없다. 그림 4 오른쪽에서 빨간 삼각형이 회색 곡선에서 아득히 떠 있는 이유다.

14. WS가 여전히 못 하는 것 — 차수 축 (What WS Still Cannot Do)

세 단원째 같은 것이 발목을 잡는다. 4-1에서 $G(n,p)$의 첫 번째 실패가 차수 분산 과소평가였다. WS도 똑같다.

WS는 $p$를 0에서 1까지 다 돌려도 차수 분산이 0에서 3.45까지만 움직인다. 실제의 15.04에는 어느 $p$에서도 도달하지 못한다. 이건 조율의 문제가 아니라 모형의 구조적 한계다 — WS는 애초에 모든 사람에게 같은 수의 간선을 나눠 주고 시작한다.

그리고 이 한계가 §12에서 본 이상한 현상을 설명한다.

→ 다음 두 단원(4-5, 4-6)은 바로 이 차수 축을 정면으로 다룬다. 차수 분포를 어떻게 재고, 어떤 모형이 허브를 만들어 내는가.

15. 교실 적용 (Classroom Application)

16. 연습문제 (Exercises)

17. 해설과 답 (Solutions)

연습문제 1 (a) — 간선 수와 차수 (Edges and Degrees)

고리 격자에서는 각자 왼쪽 $\mathrm{nei}$명, 오른쪽 $\mathrm{nei}$명과 이어지므로

연습문제 1 (b) — 15쌍 전부 (All Fifteen Pairs)

1번의 이웃은 고리 거리 3 이내: 오른쪽으로 $2,3,4$, 왼쪽으로 $24,23,22$.

두 이웃 $u,v$는 $\rho(u,v)=\min(|u-v|,\,24-|u-v|)\le 3$일 때 이어져 있다. 15쌍 전부를 전개한다.

0인 항까지 전부 더한다:

공식 검산:

분자 공식으로도 검산한다: 이어진 이웃 쌍의 수 $=3\,\mathrm{nei}(\mathrm{nei}-1)/2 = 3\times 3\times 2/2 = 9$ — 위 표의 O가 정확히 9개 ✓

> g <- sample_smallworld(1, 24, 3, 0)
> transitivity(g, type="local")[1];  transitivity(g)
[1] 0.6
[1] 0.6

값의 의미: 내 친구 여섯 명을 둘씩 짝지으면 15가지 조합이 있는데, 그중 9쌍이 이미 서로 친구다. 격자에서는 $\mathrm{nei}$가 커질수록 이 비율이 올라간다 ($\mathrm{nei}=2$면 0.5, $3$이면 0.6, $\infty$로 가면 0.75). "양옆을 넓게 볼수록 내 주변이 더 촘촘히 얽힌다"는 뜻이다.

연습문제 1 (c) — 홉별 인원과 평균 거리 (Hops and Mean Distance)

한 홉에 최대 $\mathrm{nei}=3$칸 가므로 $d=\lceil \rho/3\rceil$. $n=24$에서 1번으로부터 고리 거리 $\rho$인 사람은 $\rho=1,\dots,11$에 2명씩, 정반대편 $\rho=12$(13번)에 1명 — 합 $2\times 11+1=23$명 ✓

홉별로 묶으면

지름은 4(가장 먼 사람이 4홉).

> mean_distance(g);  diameter(g)
[1] 2.434782609
[1] 4

근사식과 비교: $n/(4\,\mathrm{nei})=24/12=2$. 실제는 2.4348이므로 근사가 18% 낮다. §4에서 본 것과 같은 이유다 — 이 근사는 $n$이 $\mathrm{nei}$에 비해 아주 클 때만 좋고, $n=24,\ \mathrm{nei}=3$은 홉이 4단계밖에 없어서 끝단 효과가 크다.

연습문제 1 (d) — 무작위와의 비교 (Lattice vs Random)

값의 의미: $n=24$는 너무 작아서 격자의 거리 벌점이 거의 안 나타난다. §5에서 $n=1000$일 때 격자는 무작위보다 25배 멀었는데, 여기서는 1.29배뿐이다. 격자의 거리는 $n$에 비례해 자라고 무작위는 $\ln n$이므로, 둘의 차이는 $n$이 커져야 벌어진다.
반대로 군집의 차이(2.34배)는 $n$과 거의 무관하다 — 격자는 늘 0.6이고 무작위는 밀도(=0.261)에 가까운 값을 갖기 때문이다. 여기서 무작위 $C=0.2559$가 밀도 $p=72/\binom{24}{2}=0.2609$와 거의 같은 것도 4-3 §6의 $C=p$를 다시 확인해 준다.

연습문제 2 (a) — 격자 만들기 (Building the Lattice)

(이번엔 평균 차수가 정확히 짝수라 §13의 FMH 같은 문제가 없다.)

$C_0$:

검산으로 삼각형과 삼중쌍을 직접 세어 본다: