단원 4-1The Erdős–Rényi Random Graph

무작위 그래프 G(n,p) — 간선을 동전 던지기로 놓는다

SNA 이론 · 단계별 학습STAGED+ 스터디

오늘 배우는 것 한 줄 요약
3단계까지는 주어진 망을 쟀다. 오늘부터는 망을 만든다. 가장 단순한 제조법 — 모든 짝에 대해 똑같은 동전을 던져 나오면 선을 긋는다 — 을 정의하고, 그 제조법이 만드는 간선 수·밀도·차수 분포를 손으로 전부 전개한다.
오늘의 결론을 미리 말하면 — 이 모형은 가라테의 평균차수를 정확히 맞히지만 차수의 흩어짐은 3.8배 과소평가한다. 평균이 맞는데 분산이 틀리는 것, 그것이 4단계 전체가 쫓아갈 단서다.

차례

오늘의 질문: 재는 일에서 만드는 일로 (From Measuring to Generating)
정의 — $G(n,p)$ (Definition)
손 계산 ① 기대 간선 수와 기대 밀도 (Expected Number of Edges and Density)
손 계산 ② 간선 수의 분포 — 열한 항 전부 (The Distribution of $m$ )
손 계산 ③ 특정 그래프 하나가 나올 확률 (Probability of One Specific Graph)
손 계산 ④ 차수 분포 $B(n-1,p)$ — 다섯 항 전부 (The Degree Distribution)
차수들은 독립이 아니다 (Degrees Are Not Independent)
분산이 오늘의 주인공이다 (Variance Is the Point)
R 검증 (R Verification)
실제 망과 대조 ① 가라테 클럽 (The Karate Club)
실제 망과 대조 ② FMH 고교 (FMH High School)
무작위화 — 실제 값은 사정권 밖 (Randomization: The Real Value Is Out of Range)
$G(n,p)$ 와 $G(n,m)$ — 두 형제 모형 (Two Sibling Models)
교실 적용 (Classroom Application)
연습문제 (Exercises)
해설과 답 (Solutions)

1. 오늘의 질문: 재는 일에서 만드는 일로 (From Measuring to Generating)

1~3단계에서 한 일을 한 문장으로 줄이면 이렇다.

행렬 $A$ 가 주어져 있고, 우리는 거기서 숫자를 뽑아냈다.

중심성도, 밀도도, 모듈러리티도 전부 그랬다. $A$ 는 하늘에서 떨어진 것이고 우리는 그것을 읽는 사람이었다. 4단계는 화살표를 거꾸로 돌린다.

어떤 규칙으로 선을 그으면, 우리가 실제로 보는 것 같은 $A$ 가 나오는가?

이 질문이 중요한 이유는 두 가지다.

이유	뜻
① 기준선을 만든다	"우리 반 군집계수 0.31"은 그 자체로는 크지도 작지도 않다. 아무 규칙 없이 만들면 얼마가 나오는가를 알아야 0.31이 크다고 말할 수 있다.
② 메커니즘을 시험한다	"친구 많은 아이에게 친구가 더 몰린다"는 가설이다. 그 가설대로 망을 만들어 보고 실제와 닮았는지 보면, 가설을 시험할 수 있다.

회수되는 옛 이야기
사실 우리는 ①을 이미 두 번 했다. 3-3의 모듈러리티

Q

에 들어 있던

\dfrac{d_i d_j}{2m}

이 "무작위라면 몇 개 있어야 하는가"였고, 3-7의 E-I 기준선

EI^{\text{exp}}=1-2\sum a_k^2

도 똑같은 물음이었다. 그때는 공식 속에 숨어 있던 영 모형(null model)을, 오늘부터는 정면으로 다룬다.

그리고 규칙 중 가장 단순한 것부터 시작한다. 얼마나 단순하냐면 — 친구 관계에 대해 아무것도 가정하지 않는다.

2. 정의 — $G(n,p)$ (Definition)

$G(n,p)$ 모형 (Erdős–Rényi, 1959 / Gilbert, 1959)
정점

n

개를 놓는다. 가능한 모든 짝

\{i,j\}\;(i<j)

에 대해, 서로 독립으로 확률

p

의 동전을 던진다.
앞면이 나오면

A[i,j]=A[j,i]=1

, 뒷면이면

0

. 자기 자신과는 잇지 않으므로

A[i,i]=0

딱 두 개의 손잡이뿐이다.

기호	뜻	교실에서
$n$	정점 수	학급 인원
$p$	한 짝이 이어질 확률	아무 두 명을 골랐을 때 친구일 확률

동전의 개수는 짝의 개수와 같다. 무방향이므로 $\{i,j\}$ 와 $\{j,i\}$ 는 같은 짝이고, 자기 자신은 세지 않는다.

\text{동전 수} \;=\; \binom{n}{2} \;=\; \frac{n(n-1)}{2}

여기서 결정적인 가정 세 개 — 4단계 내내 이것들이 하나씩 깨진다.

모든 짝의 $p$ 가 같다 — 인기 있는 아이도 없고 소외되는 아이도 없다 (4-6에서 깨진다)
짝끼리 독립이다 — "내 친구의 친구"라서 이어질 확률이 오르는 일이 없다 (4-3·4-4에서 깨진다)
정점 수가 처음부터 $n$ 으로 고정 — 망이 자라지 않는다 (4-6에서 깨진다)

p가 다른 세 개의 G(20,p) — 그림 1. $n=20$ 에서 $p$ 만 바꾼 세 그래프. $p$ 는 **밀도 손잡이**다 — 다른 성질은 조절하지 못한다. 간선 수가 기대치(9.5 / 28.5 / 76.0) 주변에서 흔들리는 것도 눈여겨볼 것.

3. 손 계산 ① 기대 간선 수와 기대 밀도 (Expected Number of Edges and Density)

오늘 내내 쓸 작은 예제를 정한다.

예제:

n=5

(학생 5명),

p=\dfrac{2}{5}=0.4

3-1. 동전이 몇 개인가 (How Many Coins)

짝을 하나도 빼지 않고 전부 적는다.

번호	짝	번호	짝
1	$\{1,2\}$	6	$\{2,4\}$
2	$\{1,3\}$	7	$\{2,5\}$
3	$\{1,4\}$	8	$\{3,4\}$
4	$\{1,5\}$	9	$\{3,5\}$
5	$\{2,3\}$	10	$\{4,5\}$

\binom{5}{2}=\frac{5\cdot 4}{2}=10 \quad\checkmark

3-2. 기대 간선 수 — 10개 항 전부 (Expected Edge Count: All Ten Terms)

각 짝 $e$ 에 대해 지시변수 $X_e$ 를 둔다: 이어졌으면 1, 아니면 0. 그러면 $m=\sum_e X_e$ 이고, $E[X_e]=1\cdot p+0\cdot(1-p)=p$ 이다.

기댓값은 독립이든 아니든 항상 더할 수 있다(선형성). 열 항을 전부 쓰면:

\begin{aligned} E[m] &= \underbrace{E[X_{12}]}_{2/5}+\underbrace{E[X_{13}]}_{2/5}+\underbrace{E[X_{14}]}_{2/5} +\underbrace{E[X_{15}]}_{2/5}+\underbrace{E[X_{23}]}_{2/5}\\[2pt] &\quad +\underbrace{E[X_{24}]}_{2/5}+\underbrace{E[X_{25}]}_{2/5} +\underbrace{E[X_{34}]}_{2/5}+\underbrace{E[X_{35}]}_{2/5}+\underbrace{E[X_{45}]}_{2/5}\\[4pt] &= 10\times\frac{2}{5} \;=\; \frac{20}{5} \;=\; \boxed{4} \end{aligned}

일반식은 그래서 이렇게 된다.

E[m]=\binom{n}{2}\,p

3-3. 기대 밀도 — $p$ 가 그대로 돌아온다 (Expected Density Returns p Itself)

1-5에서 무방향 밀도는 $\;\rho=\dfrac{m}{\binom n2}\;$ 였다. 기댓값을 넣으면:

E[\rho]=\frac{E[m]}{\binom n2}=\frac{\binom n2 p}{\binom n2}=\boxed{p}

$p$ 의 정체 —

p

는 "확률"이면서 동시에 기대 밀도다. 그래서 실제 망에

G(n,p)

를 맞출 때는 고민할 것이 없다: 관측 밀도를 그대로 $p$ 에 넣으면 된다. 가라테라면

p=78/561=0.1390

3-4. 간선 수의 분산 — 10개 항 전부 (Variance of the Edge Count: All Ten Terms)

여기서는 독립성이 필요하다. 서로 독립인 것들의 분산은 더할 수 있다. $X_e$ 는 0 아니면 1이므로 $X_e^2=X_e$ 이고,

\mathrm{Var}[X_e]=E[X_e^2]-(E[X_e])^2=p-p^2=p(1-p)=\frac25\cdot\frac35=\frac{6}{25}=0.24

열 항을 전부 더한다.

\mathrm{Var}[m]=\underbrace{0.24+0.24+0.24+0.24+0.24}_{\{1,2\}\sim\{2,3\}\;\text{다섯 짝}} +\underbrace{0.24+0.24+0.24+0.24+0.24}_{\{2,4\}\sim\{4,5\}\;\text{다섯 짝}} =10\times 0.24=\boxed{2.4}

\mathrm{Var}[m]=\binom n2 p(1-p),\qquad \mathrm{sd}[m]=\sqrt{2.4}=1.5492

즉 이 모형에서 간선은 4개 언저리에서 ±1.5개쯤 흔들린다. 그림 1의 세 그래프에서 실제 간선 수가 기대치를 빗나간 것이 바로 이 흔들림이다.

4. 손 계산 ② 간선 수의 분포 — 열한 항 전부 (The Distribution of $m$ )

기댓값과 분산만으로는 부족하다. 분포 전체를 보자. 동전 10개를 던져 앞면이 $j$ 개 나올 확률이므로 이항분포다.

P(m=j)=\binom{10}{j}\left(\frac25\right)^{j}\left(\frac35\right)^{10-j},\qquad j=0,1,\dots,10

분모를 $5^{10}=9{,}765{,}625$ 로 통일하면 분자는 $\binom{10}{j}\,2^j\,3^{10-j}$ 이다. 0인 항 없이 열한 항을 전부 쓴다.

$j$	$\binom{10}{j}$	$2^j$	$3^{10-j}$	분자 = 곱	$P(m=j)$	읽는 법
0	1	1	59049	59,049	0.006047	한 명도 안 이어짐 — 170번에 한 번
1	10	2	19683	393,660	0.040311
2	45	4	6561	1,180,980	0.120932
3	120	8	2187	2,099,520	0.214991
4	210	16	729	2,449,440	0.250823	최빈값 = 기댓값 4
5	252	32	243	1,959,552	0.200658
6	210	64	81	1,088,640	0.111477
7	120	128	27	414,720	0.042467
8	45	256	9	103,680	0.010617
9	10	512	3	15,360	0.001573
10	1	1024	1	1,024	0.000105	완전그래프 — 만 번에 한 번
합				9,765,625	1.000000	$=5^{10}$ ✓

분자를 실제로 더해 본다 — 검산은 반드시 한다.

59,049 + 393,660 = 452,709 → +1,180,980 = 1,633,689 → +2,099,520 = 3,733,209 → +2,449,440 = 6,182,649 → +1,959,552 = 8,142,201 → +1,088,640 = 9,230,841 → +414,720 = 9,645,561 → +103,680 = 9,749,241 → +15,360 = 9,764,601 → +1,024 = 9,765,625 = $5^{10}$ ✓

같은 $n$ 과 $p$ 여도 매번 다른 그래프가 나온다.

G(n,p)

는 그래프 하나가 아니라 그래프들의 확률분포다. "무작위 그래프와 비교했다"는 말은 반드시 여러 번 뽑아 평균과 범위를 봤다는 뜻이어야 한다. 한 번 뽑아 비교하는 것은 비교가 아니다.

5. 손 계산 ③ 특정 그래프 하나가 나올 확률 (Probability of One Specific Graph)

앞 절은 "간선이 4개일 확률"이었다. 이번엔 더 좁은 질문이다 — 정확히 이 그림이 나올 확률은?

목표 그림: 간선이

\{1,2\},\{1,3\},\{2,3\},\{4,5\}

네 개인 그래프 (삼각형 하나 + 외딴 짝 하나)

동전 10개의 결과가 전부 지정되었다. 앞면 4개, 뒷면 6개. 독립이므로 곱한다 — 열 항 전부:

\begin{aligned} P &= \underbrace{p}_{\{1,2\}}\cdot\underbrace{p}_{\{1,3\}}\cdot\underbrace{(1-p)}_{\{1,4\}} \cdot\underbrace{(1-p)}_{\{1,5\}}\cdot\underbrace{p}_{\{2,3\}}\\ &\quad\cdot\underbrace{(1-p)}_{\{2,4\}}\cdot\underbrace{(1-p)}_{\{2,5\}} \cdot\underbrace{(1-p)}_{\{3,4\}}\cdot\underbrace{(1-p)}_{\{3,5\}}\cdot\underbrace{p}_{\{4,5\}}\\[4pt] &= p^4(1-p)^6=\left(\frac25\right)^4\left(\frac35\right)^6 = \frac{16\cdot 729}{5^{10}}=\frac{11{,}664}{9{,}765{,}625}=\boxed{0.001194394} \end{aligned}

핵심 성질 — 이 확률에는 어느 짝인지가 전혀 들어 있지 않다. 간선 수만 같으면 어떤 그림이든 확률이 똑같다.

P(\text{특정 그래프 }G)=p^{m}(1-p)^{\binom n2-m}

그래서 $G(n,p)$ 는 구조에 대한 취향이 전혀 없는 모형이다. 삼각형을 좋아하지도, 별 모양을 좋아하지도 않는다. 오직 간선 수만 본다.

§4의 표와 이어 붙이면 검산이 된다. 간선 4개짜리 라벨 붙은 그래프는 $\binom{10}{4}=210$ 개 있고, 각각의 확률이 위와 같으므로

210\times 0.001194394=0.2508227 \;=\; P(m=4)\ \checkmark

표의 분자로 봐도 $210\times 11{,}664=2{,}449{,}440$ — §4의 $j=4$ 행과 정확히 같다. ✓

6. 손 계산 ④ 차수 분포 $B(n-1,p)$ — 다섯 항 전부 (The Degree Distribution)

이제 한 학생의 시점으로 내려간다. 1번 학생의 차수는?

1번이 관여하는 동전은 $\{1,2\},\{1,3\},\{1,4\},\{1,5\}$ — 정확히 $n-1=4$ 개다. ( $\{2,3\}$ 같은 동전은 1번의 차수와 무관하다.) 그래서

d_1=A[1,2]+A[1,3]+A[1,4]+A[1,5]\;\sim\;B(n-1,\,p)=B(4,\,0.4)

P(d=k)=\binom{n-1}{k}p^k(1-p)^{n-1-k}

분모를 $5^4=625$ 로 통일하고 다섯 항 전부:

$k$	전개	분자	$P(d=k)$	5명 중 기대 인원 $5\times P$	뜻
0	$\binom40(2/5)^0(3/5)^4=1\cdot1\cdot81$	81	0.1296	0.648	고립 학생 — 5명 중 0.65명
1	$\binom41(2/5)^1(3/5)^3=4\cdot2\cdot27$	216	0.3456	1.728	최빈값
2	$\binom42(2/5)^2(3/5)^2=6\cdot4\cdot9$	216	0.3456	1.728	최빈값 (동률)
3	$\binom43(2/5)^3(3/5)^1=4\cdot8\cdot3$	96	0.1536	0.768
4	$\binom44(2/5)^4(3/5)^0=1\cdot16\cdot1$	16	0.0256	0.128	모두와 친구 — 5명 중 0.13명
합		625	1.0000	5.000	$=5^4$ ✓

검산 — 분자 더하기: $81+216=297$ , $+216=513$ , $+96=609$ , $+16=\mathbf{625}$ ✓

6-1. 평균 차수 — 다섯 항 전부 (Mean Degree: All Five Terms)

E[d]=\frac{0\cdot 81+1\cdot 216+2\cdot 216+3\cdot 96+4\cdot 16}{625} =\frac{0+216+432+288+64}{625}=\frac{1000}{625}=\boxed{1.6}

공식으로도 $E[d]=(n-1)p=4\times 0.4=1.6$ ✓

6-2. 차수의 분산 — 다섯 항 전부 (Variance of Degree: All Five Terms)

E[d^2]=\frac{0^2\cdot81+1^2\cdot216+2^2\cdot216+3^2\cdot96+4^2\cdot16}{625} =\frac{0+216+864+864+256}{625}=\frac{2200}{625}=3.52

\mathrm{Var}[d]=E[d^2]-(E[d])^2=3.52-1.6^2=3.52-2.56=\boxed{0.96}

공식으로도 $\mathrm{Var}[d]=(n-1)p(1-p)=4\times0.4\times0.6=0.96$ ✓

6-3. 두 분포의 관계 검산 (Checking How the Two Distributions Relate)

차수를 전부 더하면 간선을 두 번씩 세는 것이다(1-4의 악수 정리).

E\!\left[\sum_i d_i\right]=5\times 1.6=8 \;=\; 2\times E[m]=2\times 4=8 \quad\checkmark

B(4,2/5) 차수 분포와 B(10,2/5) 간선 수 분포 — 그림 2. 왼쪽 = §6의 차수 분포(분모 625), 오른쪽 = §4의 간선 수 분포. 같은 모형에서 나온 **두 개의 다른 이항분포**다 — 던지는 동전 수가 4개냐 10개냐의 차이.

7. 차수들은 독립이 아니다 (Degrees Are Not Independent)

여기서 흔한 오해를 하나 잡고 간다. "각 차수가 $B(n-1,p)$ 를 따른다"는 말은 맞지만, $n$ 개의 차수가 서로 독립이라는 뜻은 아니다.

이유는 단순하다 — $d_1$ 과 $d_2$ 는 동전 $\{1,2\}$ 를 공유한다. 그 동전이 앞면이면 둘 다 +1을 받는다.

손으로 확인해 보자. 두 방식으로 $\mathrm{Var}\!\left[\sum_i d_i\right]$ 를 계산한다.

방법	계산	값
① $\sum d_i=2m$ 이므로	$\mathrm{Var}[2m]=4\,\mathrm{Var}[m]=4\times 2.4$	9.6
② 만약 독립이라면	$\sum_i \mathrm{Var}[d_i]=5\times 0.96$	4.8

같지 않다. 차이 $9.6-4.8=4.8$ 이 공분산의 총합이다. 순서쌍 $(i,j),\,i\neq j$ 는 $5\times4=20$ 개이므로

\mathrm{Cov}[d_i,d_j]=\frac{4.8}{20}=0.24=p(1-p)

정확히 공유하는 동전 하나의 분산이다. 상관계수로 바꾸면

\mathrm{Corr}[d_i,d_j]=\frac{p(1-p)}{(n-1)p(1-p)}=\frac{1}{n-1}=\frac14=0.25

읽는 법 —

n

이 커지면

1/(n-1)\to 0

이므로 큰 망에서는 차수들이 사실상 독립이다. 하지만 5명·10명짜리 소집단에서는 아니다. 모둠 단위 분석에서 "각자 독립적으로 친구를 사귄다"고 가정하면 안 되는 수학적 이유가 이것이다.

8. 분산이 오늘의 주인공이다 (Variance Is the Point)

지금까지 나온 네 공식을 한 자리에 모은다.

양	기댓값	분산	예제 ( $n=5,p=2/5$ )
간선 수 $m$	$\binom n2 p$	$\binom n2 p(1-p)$	4 / 2.4
밀도 $\rho$	$p$	$\dfrac{p(1-p)}{\binom n2}$	0.4 / 0.024
차수 $d_i$	$(n-1)p$	$(n-1)p(1-p)$	1.6 / 0.96
고립자 수	$n(1-p)^{n-1}$	—	$5\times 0.6^4=0.648$

왜 분산에 밑줄을 긋는가

p

는 손잡이가 하나뿐이다. 그래서 기댓값을 맞추면 분산은 자동으로 결정된다 — 따로 조절할 수가 없다.

(n-1)p=\bar d

로 맞추는 순간

\mathrm{Var}[d]=\bar d(1-p)

가 강제된다.

p

가 작으면

\;\mathrm{Var}[d]\approx\bar d\;

이다.
즉 $G(n,p)$ 는 "차수의 분산은 평균과 거의 같다"고 주장하는 모형이다. 실제 망이 그렇지 않다면, 그것이 바로 이 모형이 틀린 지점이다.

9. R 검증 (R Verification)

library(igraph)

# --- 손 계산 검증: n=5, p=2/5 ---
choose(5,2) * 0.4            # 4        기대 간선 수
choose(5,2) * 0.4 * 0.6      # 2.4      간선 수 분산
dbinom(0:4, 4, 0.4) * 625    # 81 216 216 96 16   차수 분포 분자
sum(dbinom(0:4, 4, 0.4))     # 1        ✓
0.4^4 * 0.6^6                # 0.001194394   특정 그래프 하나
choose(10,4) * 0.4^4 * 0.6^6 # 0.2508227
dbinom(4, 10, 0.4)           # 0.2508227     ✓ 일치

# --- 몬테카를로 10000회 ---
set.seed(1)
r <- replicate(10000, ecount(sample_gnp(5, 0.4)))
mean(r); var(r)              # 3.9915 (이론 4) / 2.3991 (이론 2.4)

$m$	0	1	2	3	4	5	6	7	8	9	10
이론	.0060	.0403	.1209	.2150	.2508	.2007	.1115	.0425	.0106	.0016	.0001
10000회 관측	.0061	.0410	.1222	.2142	.2531	.1969	.1118	.0431	.0103	.0013	.0000

소수 둘째 자리까지 일치한다. §4의 손 계산은 옳다.

구현 주의
· sample_gnp(n, p)는

G(n,p)

, sample_gnm(n, m)은

G(n,m)

이다 (§13).
· 구식 교재의 erdos.renyi.game(n, p, type="gnp")도 동작하지만 폐기 예정 경고가 뜬다.
· igraph와 sna를 함께 올리면 degree가 서로 가려지므로 igraph::degree(g)처럼 패키지명을 붙인다.

10. 실제 망과 대조 ① 가라테 클럽 (The Karate Club)

이제 손잡이를 맞춘다. 가라테는 $n=34$ , $m=78$ 이므로

\binom{34}{2}=\frac{34\cdot 33}{2}=561,\qquad p=\frac{78}{561}=0.1390374

항목	실제 가라테	$G(34,\,0.1390)$	판정
간선 수	78	78 (기댓값)	맞춰 넣었으니 당연 ✓
밀도	0.1390	0.1390	당연 ✓
평균 차수	$2\cdot78/34=4.5882$	$33\times0.1390=4.5882$	소수점까지 일치 ✓
차수의 분산	15.0374	3.9503	3.81배 과소평가 ✗
최대 차수	17	기대 인원 0.00007명	사실상 불가능 ✗

평균이 소수점까지 맞는 것은 맞춰 넣었기 때문이지 모형이 옳아서가 아니다. 모형의 진짜 예측은 분포의 모양이고, 거기서 갈라진다.

10-1. 34명을 어디에 배치하는가 — 실제 대 이론 (Placing 34 Students: Observed vs Theory)

차수 $k$	0	1	2	3	4	5	6	7	8	9	10	12	16	17
실제 인원	0	1	11	6	6	3	2	0	0	1	1	1	1	1
$34\times P(k)$	0.24	1.30	3.35	5.59	6.77	6.34	4.78	2.98	1.56	0.70	0.27	0.03	0.000	0.000
차이	−0.2	−0.3	+7.7	+0.4	−0.8	−3.3	−2.8	−3.0	−1.6	+0.3	+0.7	+1.0	+1.0	+1.0

불일치의 정체가 정확히 보인다.

가운데가 텅 비었다 — 모형은 차수 4~7에 21명을 놓으라 하는데 실제는 11명뿐
바닥이 두껍다 — 차수 2인 학생이 이론 3.35명인데 실제 11명
꼭대기가 존재한다 — 차수 16·17인 두 명(교사 1번, 관장 34번). 이 모형에서 그런 사람이 나올 확률은 $P(K\ge16)=2.12\times10^{-6}$ , 34명 중 기대 인원 0.00007명

이 한 줄이 4단계 전체의 출발점이다.
가라테에서 "차수 16 이상인 사람이 한 명이라도 있을" 법하려면 이런 동아리가 대략 1만 4천 개 있어야 한다. 그런데 실제 동아리 하나에 두 명이 있다.
평균을 맞추는 것은 쉽다. 허브를 만드는 것이 어렵고, 그 방법을 찾는 것이 4-6(선호적 연결)까지 이어지는 이야기다.

11. 실제 망과 대조 ② FMH 고교 (FMH High School)

규모가 전혀 다른 망에서도 같은 일이 벌어지는지 본다.

n=1461,\quad m=974,\quad \binom{1461}{2}=1{,}066{,}530,\quad p=\frac{974}{1066530}=0.000913242

항목	실제 FMH	$G(1461,\,0.000913)$	판정
평균 차수	$2\cdot974/1461=1.3333$	$1460\times0.000913=1.3333$	일치 ✓
차수의 분산	2.0498	1.3321	1.54배 과소평가 ✗
최대 차수	8	—	가라테(17)보다 훨씬 얌전

$p$ 가 작으면 분산 ≈ 평균

\mathrm{Var}[d]=(n-1)p(1-p)=1.3333\times(1-0.000913)=1.3321

. 평균 1.3333과 거의 같다 — 이것이 푸아송 분포의 표식이고, 다음 단원 4-2의 주제다.
실제 FMH의 분산 2.0498은 평균의 1.54배다. 어긋남의 방향은 가라테와 같지만 정도가 훨씬 약하다. 큰 학교에는 압도적 허브가 없다 — 1461명 중 최대 차수가 8명뿐.

같은 방향, 다른 크기 — 두 망 모두 "실제 분산 > 이론 분산"이지만 가라테는 3.81배, FMH는 1.54배다. 34명 동아리는 한 사람을 중심으로 돌지만, 1461명 학교는 그럴 수 없다는 지극히 상식적인 사실이 숫자에 그대로 찍혔다.

12. 무작위화 — 실제 값은 사정권 밖 (Randomization: The Real Value Is Out of Range)

"3.81배 차이"가 우연일 수 있을까? 같은 $n$ ·같은 $m$ 의 무작위 그래프를 여러 개 만들어 차수 분산을 재 봤다.

set.seed(2)
v <- replicate(1000, var(igraph::degree(sample_gnm(34, 78))))   # 가라테
mean(v); range(v); mean(v >= 15.0374)

set.seed(3)
vf <- replicate(200, var(igraph::degree(sample_gnm(1461, 974)))) # FMH (n이 커서 200회)

망	무작위 표본 수	차수 분산의 무작위 평균	관측 범위 (최소 ~ 최대)	실제 값	실제보다 큰 무작위 표본 비율
가라테	1000	3.8559	1.643 ~ 6.916	15.0374	0 / 1000
FMH	200	1.3305	1.192 ~ 1.443	2.0498	0 / 200

읽는 법
가라테에서 1000번을 던져 가장 흩어진 무작위 그래프도 분산 6.92였다. 실제는 15.04 — 최대치의 두 배가 넘는다. FMH는 더 극적이다: 200개가 1.192~1.443이라는 좁은 띠 안에 갇혀 있는데 실제는 2.05로 그 밖에 있다 (

n

이 크면 무작위 표본끼리의 흔들림이 작아지므로 표본 수가 적어도 결론이 흔들리지 않는다).

p<0.001

이라는 말로는 부족하다. 이 모형이 도달할 수 있는 영역 자체가 아니다.

중요한 구별 — 우리는 지금 "

G(n,p)

가 틀렸다"를 증명한 것이 아니라 "차수의 흩어짐이라는 축에서 틀렸다"를 확인한 것이다. 평균 거리 같은 다른 축에서는 이 모형이 꽤 잘 맞는다 (4-3에서 확인한다). 모형은 통째로 맞거나 틀리는 것이 아니라, 축마다 채점된다.

13. $G(n,p)$ 와 $G(n,m)$ — 두 형제 모형 (Two Sibling Models)

§12의 R 코드에서 sample_gnp가 아니라 sample_gnm을 썼다. 둘은 다른 모형이다.

	$G(n,p)$ — Gilbert	$G(n,m)$ — Erdős–Rényi
규칙	모든 짝에 확률 $p$ 의 동전	가능한 $\binom n2$ 개 짝에서 정확히 $m$ 개를 제비뽑기
간선 수	변한다 (평균 $\binom n2 p$ )	항상 정확히 $m$
R 함수	`sample_gnp(n, p)`	`sample_gnm(n, m)`
쓰는 곳	이론 계산 (독립이라 손 계산이 쉽다)	실제 망과의 대조 (간선 수를 고정해야 공정)

실전 규칙 — 실제 망과 비교할 때는 $G(n,m)$ 을 쓴다. 간선 수가 흔들리면 "군집계수가 낮은 게 모형 탓인지 간선이 적어서인지" 알 수 없기 때문이다. 손 계산과 이론 유도에는

G(n,p)

를 쓴다 — 동전이 독립이라 곱셈이 되기 때문.

n

이 크면 둘은 사실상 같은 모형이다 (

m

의 상대 흔들림이

1/\sqrt{\binom n2}

로 줄어든다).

이름 주의 — 흔히 "Erdős–Rényi 그래프"라고 하면 둘 다 가리킨다. 논문에서 ER 모형이라 쓰여 있으면 어느 쪽인지 확인해야 한다. 그리고 4-8에서 만날 배열 모형(configuration model)은 여기서 한 걸음 더 나아가 차수 하나하나까지 고정한다 — §10에서 본 "차수 분산이 안 맞는다"는 문제를 아예 논점에서 빼 버리는 영 모형이다.

14. 교실 적용 (Classroom Application)

① 우리 반 밀도 0.14는 큰가 작은가 — 이 질문은 틀렸다

G(n,p)

에서

p

는 맞춰 넣는 값이지 예측하는 값이 아니다. 밀도는 모형이 맞히는 것이 아니라 모형에 알려 주는 것이다. 그러니 밀도만 놓고 "무작위보다 높다/낮다"고 말할 수 없다. 비교는 밀도를 맞춘 뒤 다른 축에서 해야 한다.

② 차수 분산은 반드시 평균과 함께 본다
평균 차수 4.6인 두 학급이 있다고 하자.

학급 A: 분산 4.0 → 골고루. 무작위와 구별되지 않는다.
학급 B: 분산 15.0 → 중심 인물 몇 명 + 주변부 다수.

평균만 보면 두 반은 똑같아 보인다. 분산이 학급의 성격을 가른다. 가라테는 B형이었다.
간단한 지침:

\;\mathrm{Var}[d]\;/\;\bar d\;

를 계산해서 1 근처면 무작위형, 2를 넘으면 중심 인물형. (가라테

15.04/4.59=3.28

, FMH

2.05/1.33=1.54

)

③ "차수 2인 학생이 11명"이 진짜 발견이다
§10의 표에서 가장 큰 불일치는 최대 차수(+1명)가 아니라 차수 2에 몰린 인원(+7.7명)이었다. 허브는 눈에 띄어서 저절로 발견되지만, 바닥에 얇게 깔린 다수는 평균만 보면 보이지 않는다. 교사가 실제로 개입해야 하는 대상은 대개 이쪽이다.

④ 소집단에서는 "각자 독립적으로" 가정하지 말 것
§7에서 두 학생의 차수 상관이

1/(n-1)

임을 봤다. 5명 모둠이면 0.25 — 무시할 수 없다. 모둠 안에서 한 명이 활발해지면 다른 한 명의 연결도 같이 올라간다는 뜻이고, 이것은 관계의 심리학이 아니라 "선은 두 사람이 공유한다"는 산수에서 나온다.

⑤ 한 번 뽑아 비교하지 말 것
"무작위 그래프를 만들어 봤더니 군집계수가 0.09였습니다"는 근거가 아니다. §12처럼 수백 번 만들어 평균과 범위를 내야 한다. 학급 규모(

n=25\sim30

)에서는 흔들림이 특히 크다 — 가라테 무작위 1000개의 차수 분산이 1.64에서 6.92까지 벌어졌다.

15. 연습문제 (Exercises)

연습문제 1 — 6명 모둠, $p=1/3$
학생 6명, 모든 짝이 확률

p=\frac13

로 이어지는

G(6,\,1/3)

을 생각한다.

동전은 몇 개인가? 기대 간선 수 $E[m]$ 과 분산 $\mathrm{Var}[m]$ 은?
차수 분포 $B(5,1/3)$ 의 여섯 항을 분모 243으로 통일해 전부 쓰고, 합이 1임을 확인하라.
$E[d]$ 와 $\mathrm{Var}[d]$ 를 분포에서 직접 계산하고 공식과 대조하라.
이 모둠에서 고립 학생의 기대 인원은 몇 명인가?
간선이 정확히 $\{1,2\},\{2,3\},\{3,1\},\{4,5\},\{5,6\}$ 다섯 개인 바로 그 그래프가 나올 확률은? 그리고 $P(m=5)$ 와의 관계를 검산하라.

§16 해설 — 먼저 풀고 맞춰 볼 것.

연습문제 2 — 25명 학급의 채점
25명 학급에서 교우관계를 조사했더니 간선 60개가 나왔다. 그리고 차수의 (표본)분산은 12.0, 최대 차수는 15였다.

$p$ 와 평균 차수를 구하고, $(n-1)p$ 와 일치하는지 확인하라.
$G(25,p)$ 가 예측하는 차수 분산은? 실제 12.0은 그 몇 배인가?
모형이 예측하는 고립 학생 기대 인원은?
차수 15인 학생이 한 명이라도 있으려면 이런 학급이 대략 몇 개 필요한가?
이 학급에 대해 교사에게 무엇이라고 보고하겠는가? — 모형이 맞은 것과 틀린 것을 나눠서.

§16 해설 — 먼저 풀고 맞춰 볼 것.

16. 해설과 답 (Solutions)

연습문제 1 해설 (Solution to Exercise 1)

(1) 무엇을 세는가 — 6명에서 만들 수 있는 짝의 개수다.

\binom62=\frac{6\cdot 5}{2}=15

15개 짝을 전부 적으면 $\{1,2\}\{1,3\}\{1,4\}\{1,5\}\{1,6\}\;\{2,3\}\{2,4\}\{2,5\}\{2,6\}\;\{3,4\}\{3,5\}\{3,6\}\;\{4,5\}\{4,6\}\;\{5,6\}$ — 5+4+3+2+1 = 15 ✓

E[m]=15\times\frac13=\boxed{5},\qquad \mathrm{Var}[m]=15\times\frac13\times\frac23=\frac{30}{9}=\boxed{3.3333}

답 (1) 동전 15개,

E[m]=5

\mathrm{Var}[m]=10/3=3.3333

(표준편차 1.826 — 간선이 5개 언저리에서 ±1.8개 흔들린다).

(2) 무엇을 곱하는가 — 한 학생이 관여하는 동전은 $n-1=5$ 개이므로 $B(5,1/3)$ . 분모는 $3^5=243$ , 분자는 $\binom5k\,1^k\,2^{5-k}$ 이다. 여섯 항 전부:

$k$	$\binom5k$	$(1/3)^k$ 의 분자	$2^{5-k}$	분자	$P(d=k)$	왜 그 값인가
0	1	1	32	32	0.131687	다섯 동전 모두 뒷면 $(2/3)^5$
1	5	1	16	80	0.329218	어느 동전이 앞면인지 5가지
2	10	1	8	80	0.329218	$\binom52=10$ , $2^3=8$ → $k=1$ 과 동률
3	10	1	4	40	0.164609
4	5	1	2	10	0.041152
5	1	1	1	1	0.004115	다섯 명 전부와 친구 — 243번에 한 번
합				243	1.000000	$=3^5$ ✓

분자 검산: $32+80=112$ , $+80=192$ , $+40=232$ , $+10=242$ , $+1=\mathbf{243}$ ✓

답 (2)

\frac{32}{243},\frac{80}{243},\frac{80}{243},\frac{40}{243},\frac{10}{243},\frac{1}{243}

— 합

243/243=1

✓. $k=1$ 과 $k=2$ 가 동률 최빈값이다 (

p=1/3

일 때

(n-1)p=5/3

이 1과 2 사이에 있기 때문).

(3) 분포에서 직접 계산 — 여섯 항을 전부 전개한다.

E[d]=\frac{0\cdot32+1\cdot80+2\cdot80+3\cdot40+4\cdot10+5\cdot1}{243} =\frac{0+80+160+120+40+5}{243}=\frac{405}{243}=\frac53=\boxed{1.6667}

E[d^2]=\frac{0\cdot32+1\cdot80+4\cdot80+9\cdot40+16\cdot10+25\cdot1}{243} =\frac{0+80+320+360+160+25}{243}=\frac{945}{243}=\frac{35}{9}=3.8889

\mathrm{Var}[d]=\frac{35}{9}-\left(\frac53\right)^2=\frac{35}{9}-\frac{25}{9}=\frac{10}{9}=\boxed{1.1111}

답 (3)

E[d]=5/3=1.6667

\mathrm{Var}[d]=10/9=1.1111

.
공식과 대조:

(n-1)p=5\cdot\frac13=\frac53

✓,

(n-1)p(1-p)=5\cdot\frac13\cdot\frac23=\frac{10}{9}

✓
악수 정리 검산:

6\times\frac53=10=2\times 5=2E[m]

✓
분산/평균 $=\frac{10/9}{5/3}=\frac23=1-p$ — §8에서 예고한 대로

p

가 정하면 분산도 끝난다.

(4) 고립 학생 — 한 학생이 고립될 확률은 $P(d=0)=32/243$ . 6명 각각에 대해 기댓값을 더한다(독립이 아니어도 기댓값은 더해진다).

E[\#\text{고립}]=6\times\frac{32}{243}=\frac{192}{243}=\boxed{0.7901}

답 (4) 약 0.79명.
값의 의미: 6명 모둠을 무작위로 이어 놓으면 10번 중 8번꼴로 아무하고도 안 이어진 학생이 나온다.

교실 해석 — 모둠 활동에서 "자유롭게 짝을 지어 보라"고 했을 때 누구와도 짝이 안 되는 학생이 생기는 것은 그 학생의 문제이기 전에 산수다.

p

를 올리는(=활동 밀도를 높이는) 것만으로 이 값은 빠르게 줄지만 (

p=1/2

이면

6\times(1/2)^5=0.1875

명), 0이 되지는 않는다. 고립을 없애려면 확률에 맡기지 말고 구조를 지정해야 한다.

(5) 특정 그래프 하나 — 15개 동전의 결과가 전부 지정된다. 앞면 5개(지정된 간선), 뒷면 10개(나머지 짝).

P=\left(\frac13\right)^{5}\left(\frac23\right)^{10} =\frac{1}{243}\cdot\frac{1024}{59049}=\frac{1024}{14{,}348{,}907}=\boxed{7.1364\times10^{-5}}

검산 — 간선 5개짜리 라벨 그래프는 $\binom{15}{5}=3003$ 개:

3003\times 7.1364\times10^{-5}=0.2143071 \;=\; P(m=5)\;\checkmark

R로도 dbinom(5, 15, 1/3) $=0.2143071$ — 소수 일곱째 자리까지 일치.

답 (5)

P=1024/14{,}348{,}907=7.1364\times10^{-5}

\binom{15}{5}=3003

을 곱하면

P(m=5)=0.214307

이 되어 이항분포와 일치한다 ✓
값의 의미: 이 그래프에는 삼각형 1개(1-2-3)와 경로(4-5-6)가 들어 있지만, 모형은 그 사실을 전혀 모른다. 확률은 오직

p^5(1-p)^{10}

— 간선 5개짜리 3003개 그래프가 전부 똑같은 확률이다.

교실 해석 — "우리 반에 삼각형(세 명이 서로 친구)이 12개 있다"가 많은지 적은지를 이 모형으로 판정할 수 있는 이유가 여기 있다. 모형은 삼각형을 선호하지도 기피하지도 않으므로, 무작위로 만들었을 때 나오는 삼각형 수가 곧 공정한 기준선이 된다. 실제가 그보다 훨씬 많다면 그것은 우연이 아니라 "친구의 친구와 친구가 된다"는 메커니즘의 흔적이다 (4-3에서 정면으로 다룬다).

연습문제 2 해설 (Solution to Exercise 2)

(1) 무엇을 나누는가 — 밀도는 실제 간선 수 ÷ 가능한 짝의 수.

\binom{25}{2}=\frac{25\cdot 24}{2}=300,\qquad p=\frac{60}{300}=\boxed{0.2}

\bar d=\frac{2m}{n}=\frac{120}{25}=4.8,\qquad (n-1)p=24\times 0.2=4.8\;\checkmark

답 (1)

p=0.2

, 평균 차수 4.8. 두 방식이 정확히 일치한다.
왜 항상 일치하는가:

\frac{2m}{n}=\frac{2}{n}\binom n2 p=\frac{2}{n}\cdot\frac{n(n-1)}{2}p=(n-1)p

— 항등식이다. 그래서 "평균 차수가 맞았다"는 것은 모형의 성공이 아니다.

(2) 예측 분산

\mathrm{Var}[d]=(n-1)p(1-p)=24\times 0.2\times 0.8=\boxed{3.84}

항목	모형	실제	비	왜 그 값인가
평균 차수	4.80	4.80	1.00	맞춰 넣었으므로 항등식
차수 분산	3.84	12.00	3.125	$p$ 가 정해지면 분산은 자동 — 조절 불가
분산/평균	0.80 $(=1-p)$	2.50	3.125	1 근처면 무작위형, 2 초과면 중심인물형

답 (2) 예측 3.84, 실제 12.0 — 3.125배. 가라테(3.81배)와 거의 같은 급의 어긋남이다.

(3) 고립 학생 — 한 학생이 24개 동전에서 모두 뒷면이 나올 확률.

P(d=0)=(1-p)^{n-1}=0.8^{24}=0.00472237

E[\#\text{고립}]=25\times 0.00472237=\boxed{0.118}\ \text{명}

답 (3) 약 0.12명 — 즉 이런 학급 8~9개에 한 명꼴.
값의 의미: 밀도 0.2는 학급으로서 꽤 촘촘하다. 만약 실제로 고립 학생이 2명 있었다면 그것은 우연으로 설명되지 않는다 (기대 0.12명의 17배). 고립자 수도 분산과 나란히 놓고 봐야 할 채점 항목이다.

(4) 차수 15는 얼마나 있을 법하지 않은가 — $K\sim B(24,\,0.2)$ 에서 꼬리를 본다.

$k$	8	9	10	11	12
$P(K=k)$	0.052996	0.023554	0.008833	0.002810	0.000761
25명 중 기대 인원	1.325	0.589	0.221	0.070	0.019

P(K\ge 15)=6.6643\times 10^{-6},\qquad E[\#\{d\ge15\}]=25\times 6.6643\times10^{-6}=1.666\times10^{-4}

\text{필요한 학급 수}=\frac{1}{1.666\times10^{-4}}\approx\boxed{6002}

답 (4) 약 6000개 학급에 한 명꼴. 25명 학급 6000개면 학생 15만 명 — 웬만한 광역시 전체 초등학생 수다.
그런데 이 학급에는 지금 그 한 명이 앉아 있다.

(5) 보고 — 맞은 것과 틀린 것을 반드시 나눈다.

답 (5) 보고문 예시
모형이 맞힌 것 — 평균 친구 수 4.8명. (단, 이것은 밀도를 맞춰 넣은 결과라 모형의 예측력이 아니다.)
모형이 틀린 것 세 가지

흩어짐: 예측 분산 3.84 대 실제 12.0 (3.1배). "친구 수가 골고루"가 아니라 편중되어 있다.
꼭대기: 차수 15인 학생은 우연으로는 6000개 학급에 한 명. 이 학생은 구조적 허브이며, 그 한 명이 빠지면 학급 연결이 크게 흔들릴 수 있다 (2-3 매개 중심성으로 확인할 것).
바닥: 분산이 3배라는 것은 위쪽만 두꺼운 게 아니라 아래쪽도 두껍다는 뜻이다. 개별 차수 명단을 확인해 차수 0~1인 학생을 찾아야 한다 (모형은 고립 0.12명을 예측한다 — 실제가 그보다 많으면 반드시 보고).

덧붙일 한 문장: "무작위보다 편중되어 있다"는 진단이지 평가가 아니다. 편중 자체는 나쁜 것이 아니며(리더가 있는 학급은 대개 그렇다), 문제는 허브에 대한 의존도와 바닥에 깔린 학생 수다.

교실 해석 — 이 두 문제가 보여 준 4-1의 실전 절차는 결국 세 줄이다.
① 관측 밀도를

p

에 넣는다 → ②

(n-1)p

와

(n-1)p(1-p)

를 계산한다 → ③ 평균은 무시하고 분산·최대 차수·고립자 수만 채점한다.
엑셀로도 5분이면 끝나고, 그 세 숫자가 "우리 반은 어떤 모양인가"에 대한 첫 번째 객관적 답이 된다.

다음 단원 예고 — 4-2에서는

n

이 크고

p

가 작을 때 이항분포가 푸아송 분포로 바뀌는 것을 손으로 확인하고, 평균 차수가 1을 넘는 순간 망 전체를 관통하는 거대 컴포넌트가 갑자기 생겨나는 현상을 다룬다. FMH의 고립 학생 524명(35.9%)이 우연으로 설명되는지가 그 자리에서 판가름 난다.