단원 5-2The Exponential Family and the Normalizing Constant

지수족과 정규화 상수

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

오늘 배우는 것 한 줄 요약
5-1에서

\kappa(\theta)=(1+e^{\theta})^{561}

이라는 닫힌 식이 나왔다. 그래프가

7.5\times10^{168}

개인데 그 합을 한 줄로 적을 수 있었다.
오늘은 그게 운이었다는 것을 보인다. 통계량이 간선 수 하나뿐이라 쌍들이 서로 독립이었고, 그래서

2^N

항의 합이

N

개의 짧은 합의 곱으로 접혔던 것이다.
항을 하나만 더 넣으면 — 삼각형 수 — 그 접힘이 깨진다.

n=3

의 그래프 8개를 손으로 다시 더해서 어디가 어떻게 깨지는지 눈으로 확인하고,

n=5

의 1024개는 R로 전부 더해 정확한 답을 구한 뒤 ergm이 내놓는 답과 비교한다.
결론은 하나다. $\kappa(\theta)$ 는 거의 언제나 계산할 수 없다. 그 사실이 5단계 나머지 전체(5-3의 의사가능도, 5-7의 MCMC)의 존재 이유다.

차례 (Contents)

오늘의 질문: 5-1의 닫힌 식은 왜 나왔는가 (Why Did 5-1 Have a Closed Form?)
정의 — 정규화 상수 $\kappa(\theta)$ (Defining the Normalizing Constant)
손 계산 ① $n=3$ , 항이 하나일 때 — 8개를 다 더한다 (Summing All Eight Graphs)
손 계산 ② 항을 하나 더 넣는다 — 삼각형 (Adding a Triangle Term)
손 계산 ③ 확률 8개를 전부 계산한다 (All Eight Probabilities)
인수분해가 깨지는 이유 (Why the Factorization Breaks)
$\kappa$ 가 약분되는 단 하나의 자리 — 확률의 비 (Where $\kappa$ Cancels)
항의 수는 얼마나 빨리 커지는가 (How Fast the Sum Explodes)
R 검증 ① $n=3$ 전수 합 (Exhaustive Sum for $n=3$ )
R 검증 ② $n=5$ 정확 MLE — 1024개를 다 더해서 최적화 (Exact MLE by Enumeration)
R 검증 ③ ergm은 다른 답을 준다 (What ergm Actually Reports)
세 가지 결과 — 5단계의 나머지가 왜 필요한가 (Three Consequences)
교실 적용 (Classroom Application)
연습문제 (Exercises)
해설과 답 (Solutions)

1. 오늘의 질문: 5-1의 닫힌 식은 왜 나왔는가 (Why Did 5-1 Have a Closed Form?)

5-1에서 우리는 이렇게 썼다.

P(Y=y\mid\theta)=\frac{\exp\{\theta\,m(y)\}}{\kappa(\theta)}, \qquad \kappa(\theta)=(1+e^{\theta})^{N},\qquad N=\frac{n(n-1)}{2}

가라테는 $N=561$ 이므로 표본 공간에 그래프가 $2^{561}\approx7.548\times10^{168}$ 개 있다. 그 $7.5\times10^{168}$ 개를 전부 더한 결과가 $(1+e^{\theta})^{561}$ 이다. 한 줄이다. 그래서 로그가능도를 미분할 수 있었고, $\hat\theta=\log\frac{78}{483}$ 이라는 닫힌 해가 나왔다.

여기서 멈추고 물어야 할 것

7.5\times10^{168}

개를 더했는데 어떻게 한 줄이 되는가? 그리고 — 항을 하나 더 넣어도 계속 그런가?
오늘 답한다. 첫 물음의 답은 "쌍들이 독립이라서", 둘째 물음의 답은 "아니다"이다.

비유를 하나 두자. 동전 $N$ 개를 던져서 나올 수 있는 결과가 $2^N$ 가지다. "앞면이 나온 개수"만 따지는 모형이라면 $2^N$ 가지를 일일이 볼 필요가 없다 — 동전 하나씩 따로 보고 곱하면 된다. 그런데 "연속으로 앞면이 세 번 나온 횟수"를 따지기 시작하면 동전 하나씩 떼어 볼 수 없다. 세 개를 한꺼번에 봐야 한다. 네트워크에서 간선 수가 앞의 경우이고, 삼각형 수가 뒤의 경우다.

2. 정의 — 정규화 상수 $\kappa(\theta)$ (Defining the Normalizing Constant)

ERGM의 일반형은 이렇다. $\mathbf g(y)=(g_1(y),\dots,g_q(y))^\top$ 를 통계량 벡터, $\boldsymbol\theta=(\theta_1,\dots,\theta_q)^\top$ 를 계수 벡터라 하면

P(Y=y\mid\boldsymbol\theta) =\frac{\exp\{\boldsymbol\theta^\top\mathbf g(y)\}}{\kappa(\boldsymbol\theta)}, \qquad \boxed{\;\kappa(\boldsymbol\theta)=\sum_{y'\in\mathcal Y}\exp\{\boldsymbol\theta^\top\mathbf g(y')\}\;}

세 가지를 확실히 해 두자.

헷갈리는 점	사실
$\kappa$ 는 모수인가?	아니다. $\boldsymbol\theta$ 를 정하면 자동으로 정해지는 값이다. 추정할 대상이 아니라 계산할 대상이다.
합은 무엇에 대해 도는가?	관측한 망 $y$ 가 아니라 표본 공간 $\mathcal Y$ 전체, 즉 있을 수 있는 모든 망 $y'$ 에 대해 돈다. 그래서 $\kappa$ 에는 데이터가 전혀 들어가지 않는다 — $\boldsymbol\theta$ 와 $n$ 만의 함수다.
왜 필요한가?	확률의 총합이 1이어야 하기 때문이다. $\sum_{y}P(Y=y)=\frac{1}{\kappa}\sum_{y}\exp\{\boldsymbol\theta^\top\mathbf g(y)\} =\frac{\kappa}{\kappa}=1$ . 정의상 반드시 성립한다.

"정규화(normalizing)"라는 말의 뜻

\exp\{\boldsymbol\theta^\top\mathbf g(y)\}

는 그냥 "이 망의 점수"다. 점수는 0보다 크지만 합이 1이라는 보장이 없다. 모든 망의 점수를 더한 값

\kappa

로 나누면 비로소 확률이 된다. 반 학생 30명의 시험 원점수를 총점으로 나눠서 "각자의 비중"을 만드는 것과 정확히 같은 조작이다. 총점을 모르면 비중을 모른다 — 오늘의 문제가 바로 이것이다.

3. 손 계산 ① $n=3$ , 항이 하나일 때 — 8개를 다 더한다 (Summing All Eight Graphs)

정점 3개짜리 무방향 망을 쓰자. 쌍은 $N=\binom{3}{2}=3$ 개다: $\{1,2\},\{1,3\},\{2,3\}$ . 각 쌍이 0 또는 1이므로 그래프는 $2^3=8$ 개. 전부 적는다. 통계량은 간선 수 $m(y)=A[1,2]+A[1,3]+A[2,3]$ 하나뿐이다.

#	$A[1,2]$	$A[1,3]$	$A[2,3]$	$m(y)$	$\exp\{\theta m(y)\}$	모양
1	0	0	0	0	$e^{0}=1$	빈 그래프
2	1	0	0	1	$e^{\theta}$	간선 1개
3	0	1	0	1	$e^{\theta}$	간선 1개
4	0	0	1	1	$e^{\theta}$	간선 1개
5	1	1	0	2	$e^{2\theta}$	경로 (2–1–3)
6	1	0	1	2	$e^{2\theta}$	경로 (1–2–3)
7	0	1	1	2	$e^{2\theta}$	경로 (1–3–2)
8	1	1	1	3	$e^{3\theta}$	삼각형

여덟 줄을 전부 더한다. 하나도 빠뜨리지 않고 적으면

\begin{aligned} \kappa(\theta) &= \underbrace{1}_{\#1} + \underbrace{e^{\theta}}_{\#2} + \underbrace{e^{\theta}}_{\#3} + \underbrace{e^{\theta}}_{\#4} + \underbrace{e^{2\theta}}_{\#5} + \underbrace{e^{2\theta}}_{\#6} + \underbrace{e^{2\theta}}_{\#7} + \underbrace{e^{3\theta}}_{\#8}\\[4pt] &= 1 + 3e^{\theta} + 3e^{2\theta} + e^{3\theta} \end{aligned}

계수 $1,3,3,1$ 이 보이는가. 이항계수 $\binom{3}{0},\binom{3}{1},\binom{3}{2},\binom{3}{3}$ 이다. 간선 $m$ 개짜리 그래프가 $\binom{3}{m}$ 개 있으니 당연하다. 그러므로

\kappa(\theta)=\sum_{m=0}^{3}\binom{3}{m}\left(e^{\theta}\right)^{m}\cdot 1^{\,3-m} =\left(1+e^{\theta}\right)^{3}

이항정리다. 일반적인 $N$ 에 대해서도 똑같이 $\kappa(\theta)=(1+e^\theta)^N$ .

3-1. 곱으로 접히는 과정을 한 번 더, 이번엔 반대 방향으로 (Factorization Once More, in Reverse)

이항정리를 몰라도 같은 결과를 얻는 길이 있고, 그 길이 오늘의 핵심이다. $(1+e^{\theta})^3$ 을 전개해 보자. 괄호 세 개에서 각각 $1$ 또는 $e^\theta$ 를 하나씩 고른다:

첫째 괄호 (쌍 $\{1,2\}$ )	둘째 괄호 (쌍 $\{1,3\}$ )	셋째 괄호 (쌍 $\{2,3\}$ )	곱	대응하는 그래프
$1$	$1$	$1$	$1$	#1 빈 그래프
$e^\theta$	$1$	$1$	$e^{\theta}$	#2
$1$	$e^\theta$	$1$	$e^{\theta}$	#3
$1$	$1$	$e^\theta$	$e^{\theta}$	#4
$e^\theta$	$e^\theta$	$1$	$e^{2\theta}$	#5
$e^\theta$	$1$	$e^\theta$	$e^{2\theta}$	#6
$1$	$e^\theta$	$e^\theta$	$e^{2\theta}$	#7
$e^\theta$	$e^\theta$	$e^\theta$	$e^{3\theta}$	#8 삼각형

전개항 ↔ 그래프의 일대일 대응
괄호 하나가 쌍 하나에 대응하고, 그 괄호에서

1

을 고르면 "간선 없음",

e^\theta

를 고르면 "간선 있음"이다. 그러니

(1+e^\theta)^3

을 전개하는 일과 그래프 8개를 열거하는 일은 글자 그대로 같은 작업이다.
기호로 쓰면 — 이게 오늘 기억해야 할 한 줄이다 —

\sum_{y\in\mathcal Y}\ \prod_{i<j}e^{\theta A[i,j]} \;=\;\prod_{i<j}\ \Big(\sum_{a\in\{0,1\}}e^{\theta a}\Big) \;=\;\prod_{i<j}\big(1+e^{\theta}\big)=(1+e^{\theta})^{N}

왼쪽은 $2^N$ 개를 더한 것, 오른쪽은 2개짜리 합을 $N$ 번 곱한 것이다.

2^{561}

이

561

로 줄었다. 이 맞바꿈이 5-1의 전부였다.

4. 손 계산 ② 항을 하나 더 넣는다 — 삼각형 (Adding a Triangle Term)

이제 통계량을 두 개로 늘린다.

\mathbf g(y)=\big(m(y),\ t(y)\big),\qquad m(y)=\sum_{i<j}A[i,j],\qquad t(y)=\sum_{i<j<k}A[i,j]\,A[i,k]\,A[j,k]

$t(y)$ 는 삼각형의 개수다. $n=3$ 에서는 삼각형이 될 수 있는 정점 조합이 $\binom{3}{3}=1$ 가지( $\{1,2,3\}$ )뿐이므로 $t(y)$ 는 0 아니면 1이다. 세 간선이 모두 있을 때만 1이 된다.

같은 그래프 8개에 $t$ 열을 하나 더 붙인다.

#	$A[1,2]$	$A[1,3]$	$A[2,3]$	$m$	$t$	$\boldsymbol\theta^\top\mathbf g=\theta_1 m+\theta_2 t$	$\exp\{\boldsymbol\theta^\top\mathbf g\}$
1	0	0	0	0	0	$0$	$1$
2	1	0	0	1	0	$\theta_1$	$e^{\theta_1}$
3	0	1	0	1	0	$\theta_1$	$e^{\theta_1}$
4	0	0	1	1	0	$\theta_1$	$e^{\theta_1}$
5	1	1	0	2	0	$2\theta_1$	$e^{2\theta_1}$
6	1	0	1	2	0	$2\theta_1$	$e^{2\theta_1}$
7	0	1	1	2	0	$2\theta_1$	$e^{2\theta_1}$
8	1	1	1	3	1	$3\theta_1+\theta_2$	$e^{3\theta_1+\theta_2}$

여덟 항을 전부 더한다.

\begin{aligned} \kappa(\theta_1,\theta_2) &= 1 + e^{\theta_1} + e^{\theta_1} + e^{\theta_1} + e^{2\theta_1} + e^{2\theta_1} + e^{2\theta_1} + e^{3\theta_1+\theta_2}\\[4pt] &= 1 + 3e^{\theta_1} + 3e^{2\theta_1} + e^{3\theta_1+\theta_2} \end{aligned}

4-1. 이 식은 인수분해되는가? (Does This Expression Factor)

5-1의 식과 나란히 놓는다.

\begin{aligned} (1+e^{\theta_1})^{3} &= 1 + 3e^{\theta_1} + 3e^{2\theta_1} + e^{3\theta_1}\\ \kappa(\theta_1,\theta_2) &= 1 + 3e^{\theta_1} + 3e^{2\theta_1} + e^{3\theta_1}\cdot e^{\theta_2} \end{aligned}

앞의 세 항은 똑같고, 마지막 항만 $e^{\theta_2}$ 배가 되었다. 차를 구하면

\kappa(\theta_1,\theta_2)-(1+e^{\theta_1})^{3} = e^{3\theta_1}e^{\theta_2}-e^{3\theta_1} = e^{3\theta_1}\left(e^{\theta_2}-1\right)

\boxed{\;\kappa(\theta_1,\theta_2)=(1+e^{\theta_1})^{3}+e^{3\theta_1}\left(e^{\theta_2}-1\right)\;}

검산 — $\theta_2=0$ 이면 5-1로 돌아가야 한다

\theta_2=0

이면

e^{\theta_2}-1=1-1=0

이므로 보정항이 사라지고

\kappa=(1+e^{\theta_1})^3

. ✔
"삼각형 계수가 0"이라는 말은 "삼각형을 신경 쓰지 않는다"는 뜻이고, 그러면 정확히 간선만 있는 5-1 모형이 된다. 모형이 서로 포개진다(nested)는 것을 식이 보여 준다.

속지 말 것 — $n=3$ 이라서 짧게 끝난 것이다
위의 "보정항 하나"는

n=3

에서 삼각형이 될 수 있는 자리가 단 한 군데라서 생긴 특수 사정이다.

n=4

만 되어도 삼각형 자리가

\binom{4}{3}=4

군데이고,

t(y)

가 0·1·2·4의 값을 갖는 그래프가 뒤섞여 이런 깔끔한 보정항으로 정리되지 않는다. 직접 확인하는 것이 §14 연습문제 2다.

5. 손 계산 ③ 확률 8개를 전부 계산한다 (All Eight Probabilities)

숫자를 넣자. $\theta_1=-0.5$ , $\theta_2=1$ 로 둔다. "간선은 드물게, 그런데 삼각형은 좋아하는" 모형이다. 필요한 지수함수 값 세 개를 먼저 구한다.

필요한 값	계산	값
$e^{\theta_1}$	$e^{-0.5}$	0.6065307
$e^{2\theta_1}$	$e^{-1.0}$	0.3678794
$e^{3\theta_1+\theta_2}$	$e^{-1.5+1.0}=e^{-0.5}$	0.6065307

$\kappa$ 를 항별로 쌓는다.

\begin{aligned} \kappa(-0.5,\,1) &= 1 \;+\; 3(0.6065307) \;+\; 3(0.3678794) \;+\; 0.6065307\\[3pt] &= 1 \;+\; 1.8195920 \;+\; 1.1036383 \;+\; 0.6065307\\[3pt] &= 4.5297610 \end{aligned}

이제 여덟 그래프의 확률을 하나씩 낸다. 각각 점수를 $\kappa$ 로 나누면 된다.

#	$m$	$t$	점수 $\exp\{\boldsymbol\theta^\top\mathbf g\}$	$P=$ 점수 $/\kappa$	$\theta_2=0$ 일 때 $P$ (5-1 모형)
1	0	0	$1$	$1/4.5297610=$ 0.2207622	0.2411754
2	1	0	$0.6065307$	$0.6065307/4.5297610=$ 0.1338990	0.1462803
3	1	0	$0.6065307$	0.1338990	0.1462803
4	1	0	$0.6065307$	0.1338990	0.1462803
5	2	0	$0.3678794$	$0.3678794/4.5297610=$ 0.0812139	0.0887235
6	2	0	$0.3678794$	0.0812139	0.0887235
7	2	0	$0.3678794$	0.0812139	0.0887235
8	3	1	$0.6065307$	0.1338990	0.0538135

합이 1인지 확인한다. 무리별로 묶어서

\begin{aligned} \sum_{y}P(Y=y) &= 0.2207622 + 3(0.1338990) + 3(0.0812139) + 0.1338990\\[3pt] &= 0.2207622 + 0.4016971 + 0.2436416 + 0.1338990\\[3pt] &= 1.0000000\ \checkmark \end{aligned}

정점 3개 위의 그래프 8개와 두 모형에서의 확률 — 그림 1. 정점 3개 위의 그래프 8개 전부. 각 그림 아래 두 숫자는 순서대로 $\theta_2=0$ (간선만)과 $\theta_2=1$ (간선+삼각형)에서의 확률. 삼각형만 확률이 **올라가고** 나머지 일곱은 전부 조금씩 내려간다.

5-1. 삼각형 확률은 몇 배가 되었나 — 그리고 왜 $e^{1}$ 배가 아닌가 (How Much the Triangle Probability Grew, and Why Not by e)

표의 마지막 두 열을 비교하면 삼각형의 확률이 $0.0538135\to0.1338990$ 으로 올랐다. 배율은

\frac{0.1338990}{0.0538135}=2.4882055

그런데 우리가 곱한 것은 $e^{\theta_2}=e^{1}=2.7182818$ 이었다. 왜 2.718배가 아니라 2.488배인가? 분모도 같이 커졌기 때문이다.

\frac{P_{\theta_2=1}(\triangle)}{P_{\theta_2=0}(\triangle)} =\frac{e^{3\theta_1}e^{\theta_2}/\kappa_{1}}{e^{3\theta_1}/\kappa_{0}} =e^{\theta_2}\cdot\frac{\kappa_{0}}{\kappa_{1}} =2.7182818\times\frac{4.1463605}{4.5297610} =2.7182818\times0.9153589=2.4882055\ \checkmark

ERGM 계수를 읽을 때 가장 흔한 오독
"삼각형 계수가

1

이니 삼각형이 하나 늘면 확률이

e^1=2.72

배" — 틀렸다.

\kappa

가 같이 움직이므로 실제 배율은 그보다 작다.
확률이 아니라 확률의 비로 말해야 정확해진다(§7). 5-1에서 "

\theta

는 확률이 아니라 로그오즈"라고 했던 경고의 다항 모형판이다.

5-2. 우연이 아닌 우연 — 삼각형과 간선 1개의 확률이 정확히 같다 (A Coincidence That Isn't One)

표를 다시 보면 $\theta_2=1$ 일 때 #8(삼각형)과 #2~#4(간선 1개)의 확률이 모두 0.1338990으로 똑같다. 간선이 세 배나 많은 그래프인데도. 왜 그런가? 점수를 비교하면 된다.

e^{3\theta_1+\theta_2}=e^{\theta_1} \iff 3\theta_1+\theta_2=\theta_1 \iff \boxed{\,2\theta_1+\theta_2=0\,}

여기서 $2(-0.5)+1=-1+1=0$ 이다. 조건에 정확히 걸렸다. 우연이 아니라 고른 숫자가 그 선 위에 있었을 뿐이다.

교실로 옮기면

2\theta_1+\theta_2=0

은 "간선 하나를 더 그을 비용

2|\theta_1|

과 그 결과로 삼각형이 완성될 때 받는 보상

\theta_2

가 정확히 맞아떨어지는 지점"이다. 교실로 옮기면 — 새 친구를 사귀는 부담이, 그렇게 해서 "친구의 친구와도 친구가 되는" 이득과 정확히 상쇄되는 상태. 이보다

\theta_2

가 크면 학급은 뭉치고, 작으면 흩어진다.

6. 인수분해가 깨지는 이유 (Why the Factorization Breaks)

§3-1의 맞바꿈이 왜 성립했는지 한 단계씩 되짚고, 어디서 무너지는지 짚는다.

6-1. 성립할 때 (간선 항만) (When It Holds: Edges Only)

\exp\{\theta\,m(y)\} =\exp\Big\{\theta\sum_{i<j}A[i,j]\Big\} =\prod_{i<j}e^{\theta A[i,j]}

지수의 합이 곱이 되었다. 여기서 결정적인 것은 $e^{\theta A[i,j]}$ 라는 각 인수가 단 하나의 칸 $A[i,j]$ 에만 의존한다는 점이다. 그래서 $\mathcal Y$ 전체에 대한 합을 칸별로 분배할 수 있다.

\sum_{y\in\mathcal Y}\prod_{i<j}e^{\theta A[i,j]} =\prod_{i<j}\sum_{a=0}^{1}e^{\theta a} =\prod_{i<j}(1+e^{\theta}) =(1+e^{\theta})^{N}

6-2. 무너질 때 (삼각형 항) (When It Breaks: Adding Triangles)

\exp\{\theta_2\,t(y)\} =\exp\Big\{\theta_2\sum_{i<j<k}A[i,j]A[i,k]A[j,k]\Big\} =\prod_{i<j<k}e^{\theta_2 A[i,j]A[i,k]A[j,k]}

여기까지는 똑같이 곱이 된다. 그러나 이번 인수 $e^{\theta_2 A[i,j]A[i,k]A[j,k]}$ 는 칸 세 개를 동시에 본다. 칸 $A[1,2]$ 는 $\{1,2,3\}$ 뿐 아니라 $\{1,2,4\},\{1,2,5\},\dots$ 인수에도 들어간다. 그래서 "쌍마다 따로 합을 매긴다"는 분배가 불가능하다. $\sum$ 과 $\prod$ 을 맞바꿀 수 없다.

$n=3$ 의 여덟 항에서 직접 확인
§4의 여덟 항 중

e^{\theta_2}

를 가진 항은 #8 하나뿐이다. 곱

(\square)(\square)(\square)

형태로 쓰려면 세 괄호에서 하나씩 골라 만든 8가지 조합이 전부 항이 되어야 하는데,

\theta_2

는 여덟 개 중 딱 한 조합에만 붙어 있다. 어떤 세 괄호로도 이런 비대칭을 만들 수 없다 — 그래서 인수분해가 없다.

같은 사실의 다른 표현: 쌍 독립성(dyadic independence)이 깨진다
5-1의 모형에서는 "1–2가 친구인가"와 "1–3이 친구인가"가 서로 무관했다. 그래서 5-1 §9에서 glm(y ~ 1, family=binomial)이 ergm과 같은 답을 냈던 것이다 — 561개 쌍을 독립 관측치로 취급해도 됐으니까.
삼각형 항이 들어오는 순간 그게 깨진다. 1–2와 1–3이 이미 있으면 2–3이 생길 확률이 달라진다. 더 이상 로지스틱 회귀가 아니다. 5-3에서 이 붕괴를 정면으로 다룬다.

7. $\kappa$ 가 약분되는 단 하나의 자리 — 확률의 비 (Where $\kappa$ Cancels)

$\kappa$ 를 모르면 아무것도 못 하는가? 그렇지 않다. 두 망의 확률을 나누면 $\kappa$ 가 사라진다.

\frac{P(Y=y_1)}{P(Y=y_2)} =\frac{\exp\{\boldsymbol\theta^\top\mathbf g(y_1)\}\big/\kappa(\boldsymbol\theta)} {\exp\{\boldsymbol\theta^\top\mathbf g(y_2)\}\big/\kappa(\boldsymbol\theta)} =\exp\big\{\boldsymbol\theta^\top\left(\mathbf g(y_1)-\mathbf g(y_2)\right)\big\}

분자와 분모에 같은 $\kappa$ 가 있으니 약분된다. 남는 것은 통계량의 차이뿐이다. 손으로 확인하자. $y_1=$ #8(삼각형), $y_2=$ #5(경로 2–1–3)로 두면

	$m$	$t$
$\mathbf g(y_1)$ — 삼각형	3	1
$\mathbf g(y_2)$ — 경로	2	0
차 $\mathbf g(y_1)-\mathbf g(y_2)$	1	1

\frac{P(\triangle)}{P(\text{경로})} =\exp\{\theta_1\cdot 1+\theta_2\cdot 1\} =e^{-0.5+1}=e^{0.5}=1.6487213

표의 값으로 검산하면 $0.1338990/0.0812139=1.6487213$ . 완전히 일치한다.

왜 이 계산이 5-3의 씨앗인가
방금 고른 두 그래프는 칸 하나만 다르다 — 경로 #5에

A[2,3]=1

을 더하면 삼각형 #8이 된다. 그러니 위의 비는 그냥 두 그래프의 비가 아니라 "나머지를 다 고정했을 때 2–3 칸에 간선이 있을 오즈"다.

\theta_1

은 "간선 하나가 늘어서" 붙고,

\theta_2

는 "그 간선 때문에 삼각형이 하나 생겨서" 붙는다. 통계량의 이 차이 벡터 $(1,1)$ 가 5-3에서 배울 변화 통계량(change statistic)이다.

\kappa

를 몰라도 계산되는 유일한 양이고, 그래서 ERGM 계수 해석은 전부 여기에 기댄다.

8. 항의 수는 얼마나 빨리 커지는가 (How Fast the Sum Explodes)

$\kappa$ 를 정직하게 계산한다는 것은 그래프를 전부 열거한다는 뜻이다. 몇 개인가.

$n$	쌍 개수 $N=\binom n2$	그래프 수 $2^N$	초당 1억 개를 처리한다면
3	3	8	손으로 (오늘 했다)
4	6	64	손으로 (연습문제 2)
5	10	1,024	R로 즉시 — 오늘의 §10
6	15	32,768	즉시
7	21	2,097,152	0.02초
8	28	268,435,456	2.7초 — 현실적 한계
10	45	35,184,372,088,832	97.7 시간
20	190	$1.57\times10^{57}$	$1.6\times10^{49}$ 초 = 우주 나이의 $3.6\times10^{31}$ 배
34 (가라테)	561	$7.55\times10^{168}$	—
1461 (FMH)	1,066,530	321,058자리 수	—

가라테 정도의 크기를 감각으로 잡아 보자
관측 가능한 우주의 원자 수가 대략

10^{80}

개다. 가라테 클럽 34명의 표본 공간은

7.55\times10^{168}

개 — 원자 하나마다 우주를 하나씩 통째로 배정해도 아직

7.5\times10^{8}

배 모자란다.
학생 34명짜리 한 학급에서 이렇다. 30명 학급이면

N=435

2^{435}\approx8.9\times10^{130}

.
그러니 "정확히 계산하되 조금 오래 걸린다"가 아니다. 영원히 불가능하다.

9. R 검증 ① $n=3$ 전수 합 (Exhaustive Sum for $n=3$ )

손 계산이 맞는지 8개를 실제로 열거해 확인한다.

## 정점 3개 위의 그래프 8개를 전부 만들고 (간선 수, 삼각형 수) 계산
prs <- rbind(c(1,2), c(1,3), c(2,3))
mm  <- sapply(0:7, function(cd) sum(as.integer(intToBits(cd))[1:3]))
tt  <- ifelse(mm == 3, 1, 0)          # n=3 에서 삼각형 자리는 한 군데뿐
t1 <- -0.5; t2 <- 1

sum(exp(t1*mm + t2*tt))                            # kappa 전수 합
[1] 4.529760962
1 + 3*exp(t1) + 3*exp(2*t1) + exp(3*t1 + t2)       # 손 계산 식
[1] 4.529760962
(1 + exp(t1))^3 + exp(3*t1)*(exp(t2) - 1)          # 보정항 형태
[1] 4.529760962

pr <- exp(t1*mm + t2*tt) / sum(exp(t1*mm + t2*tt))
sum(pr)
[1] 1
pr[mm == 3]                                        # 삼각형
[1] 0.1338990434
pr[mm == 1][1]                                     # 간선 1개 — 같은 값!
[1] 0.1338990434

세 가지 형태가 소수점 아래 아홉 자리까지 일치하고, 확률의 합이 정확히 1이며, $2\theta_1+\theta_2=0$ 이라 삼각형과 간선 1개의 확률이 같다는 것까지 확인된다.

10. R 검증 ② $n=5$ 정확 MLE — 1024개를 다 더해서 최적화 (Exact MLE by Enumeration)

이제 진짜 추정을 해 보자. $n=5$ 면 그래프가 1024개뿐이니 $\kappa$ 를 근사 없이 정확히 계산할 수 있다. 이런 크기는 흔치 않다 — "정답을 아는 상태"에서 ergm을 채점할 수 있는 거의 유일한 기회다.

관측 망은 5-1 연습문제 1의 5명 모둠을 그대로 쓴다: 간선 S1–S2 S1–S3 S2–S3 S3–S4, S5는 외톨이. 통계량은 $m(y_{\text{obs}})=4$ , $t(y_{\text{obs}})=1$ (삼각형 S1–S2–S3 하나).

## 1024개 전수 열거 -> 정확한 로그가능도 -> optim
e5 <- enumerate(5)          # 1024 x 2 행렬, 열은 (m, t)
mo <- 4; to <- 1            # 관측 통계량

negll <- function(th) {
  lin <- th[1]*e5[,"m"] + th[2]*e5[,"t"]
  M   <- max(lin)                                  # 넘침 방지
  -(th[1]*mo + th[2]*to - (M + log(sum(exp(lin - M)))))
}
op <- optim(c(0,0), negll, method = "BFGS", control = list(reltol = 1e-14))
op$par
[1] -0.7757745245  0.6579263060
-op$value                                          # 최대 로그가능도
[1] -6.60005759

## 적률 일치 확인 — 근사가 아니라 정확한 기댓값
lin <- op$par[1]*e5[,"m"] + op$par[2]*e5[,"t"]
w   <- exp(lin - max(lin)); w <- w/sum(w)
c(sum(w*e5[,"m"]), sum(w*e5[,"t"]))
[1] 3.999999977 0.999998867     # 관측 (4, 1) 과 일치

## 간선만 넣으면 5-1 의 손 계산으로 돌아가는가?
edges-only 정확 MLE = -0.40546513   ,   log(4/6) = -0.4054651081

두 가지가 확인되었다
① 적률 일치가 다항 모형에서도 성립한다. 5-1에서

m=Np(\theta)

하나였던 조건이

E_{\hat\theta}[m(Y)]=4

E_{\hat\theta}[t(Y)]=1

두 개로 늘었다. 통계량이

q

개면 조건도

q

개다. 이건 모든 ERGM에서 참이다.
② 간선 항만 남기면 5-1의 닫힌 해로 정확히 돌아온다.

\log\frac{4}{6}=-0.4054651

. 전수 열거로 얻은 값과 소수점 일곱 자리까지 같다. 5-1의 손 계산이 옳았다는 독립적인 증거다.

n=5 정확 로그가능도 등고선 — 그림 2. $n=5$ 그래프 1024개를 전부 더해 그린 로그가능도 등고선. 가운데 빨간 점이 정확한 MLE. 초록 네모는 삼각형 항을 뺀 5-1 모형의 답이고, 보라 삼각형은 `ergm`이 MCMC로 내놓은 답이다(§11).

10-1. 삼각형 항을 넣으니 간선 계수가 더 음수가 되었다 (Adding Triangles Pushes the Edge Coefficient Down)

모형	$\hat\theta_1$ (간선)	$\hat\theta_2$ (삼각형)
`y ~ edges` (5-1)	$-0.4055$	—
`y ~ edges + triangle`	$-0.7758$	$+0.6579$

간선 계수가 $-0.4055\to-0.7758$ 로 더 내려갔다. 왜 그런가?

이 변화를 읽는 법 — 회귀의 통제와 같다
간선만 있던 모형에서

\theta_1

은 "이 망에 간선이 4개나 있다"는 사실을 혼자 설명해야 했다. 삼각형 항이 들어오자, 4개 중 삼각형을 이루는 3개는

\theta_2

가 설명해 준다. 그러면

\theta_1

이 남겨 받는 몫은 "삼각형과 무관하게 그냥 생긴 간선"뿐이고, 그건 훨씬 드무므로 계수가 더 음수가 된다.
교실 언어로: "우리 반은 아무하고나 친구가 되는 경향은 오히려 약하다. 다만 친구의 친구와는 친구가 되는 경향이 뚜렷하다." 앞의 단순 모형은 이 두 힘을 하나로 뭉뚱그려 평균 낸 것이었다.
회귀에서 변수를 추가하면 기존 계수가 움직이는 것과 정확히 같은 현상이며, 그래서 ERGM 계수는 그 모형에 무엇이 같이 들어 있는지를 밝히지 않으면 뜻이 없다.

11. R 검증 ③ `ergm`은 다른 답을 준다 (What `ergm` Actually Reports)

같은 자료에 ergm을 그대로 돌려 보자.

nw5 <- network(A5, directed = FALSE)
ergm(nw5 ~ edges + triangle)

Starting maximum pseudolikelihood estimation (MPLE): ...
Starting Monte Carlo maximum likelihood estimation (MCMLE):
Iteration 1 of at most 60: ... Convergence test p-value: 0.0014. Converged with 99% confidence.
Evaluating log-likelihood at the estimate. Fitting the dyad-independent submodel...
Bridging between the dyad-independent submodel and the full model...
Using 16 bridges: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 .

              Estimate  Std. Error  z value  Pr(>|z|)
edges        -0.9074695   0.9011879  -1.0070    0.3139
triangle      0.8410930   0.9598360   0.8763    0.3809

정확한 답은 $(-0.7758,\ 0.6579)$ 였다. ergm은 $(-0.9075,\ 0.8411)$ 을 준다. 차이가 각각 $0.13$ , $0.18$ 이다. 난수 씨앗을 바꾸면 답도 바뀐다.

방법	$\hat\theta_1$	$\hat\theta_2$	비고
전수 열거 (정답)	$-0.775775$	$0.657926$	1024개를 다 더함. 난수 없음
`ergm`, `seed=7`	$-0.907469$	$0.841093$	MCMC
`ergm`, `seed=101`	$-0.826759$	$0.778033$	MCMC
`ergm`, `seed=2026`	$-0.818927$	$0.689058$	MCMC

이것은 ergm의 버그가 아니다 — 오늘 배운 사실의 직접적 귀결이다

\kappa(\theta_1,\theta_2)

를 계산할 수 없으므로 ergm은 모의실험으로 근사한다(MCMLE). 근사이므로 실행마다 값이 흔들린다.
흔들림 폭(약 0.09~0.13)을 표준오차(0.90, 0.96)와 견주면 작지만 0은 아니다. 소수점 셋째 자리를 논문에 적을 때는 이 사실을 기억해야 한다.
4단계 §4-8에서 cluster_louvain()의

Q

가 실행마다 달랐던 것과 같은 종류의 문제다. "난수를 쓰는 알고리즘의 출력은 값 하나가 아니라 분포"라는 점에서.
결정적으로 — $n=34$ 에서는 위 표의 첫 줄이 없다. 대조할 정답이 존재하지 않는다. 그래서 5-7에서 수렴 진단(mcmc.diagnostics())을 반드시 배워야 한다.

출력 로그의 Using 16 bridges도 이제 읽힌다. 로그가능도 값 (모형 비교와 AIC에 필요하다)을 내려면 $\kappa$ 를 알아야 하는데 알 수 없으므로, ergm은 계산 가능한 쌍 독립 모형에서 출발해 목표 모형까지 중간 모형 16개를 놓고 다리를 놓듯 차이를 누적한다(bridge sampling). $\kappa$ 를 우회하는 또 하나의 장치다.

12. 세 가지 결과 — 5단계의 나머지가 왜 필요한가 (Three Consequences)

$\kappa$ 를 모르면 못 하는 것	그래서 어떻게 하는가	어디서
가능도 $P(Y=y_{\text{obs}})$ 를 직접 계산하고 최대화하기	① 의사가능도(MPLE) — 쌍마다의 조건부 확률만 곱한다. 조건부에서는 $\kappa$ 가 약분된다(§7) ② MCMC 최대가능도(MCMLE) — 모형에서 망을 잔뜩 뽑아 $\kappa$ 의 비를 추정	5-3 / 5-7
로그가능도·AIC·우도비 검정으로 모형 비교하기	다리 표본(bridge sampling)으로 두 모형의 $\log\kappa$ 차이를 근사. 절댓값은 끝내 모르지만 차이면 비교에 충분하다	5-6
"우리 반 관계망이 나올 확률은 0.003입니다" 같은 절대 확률 말하기	포기한다. 대신 확률의 비(조건부 오즈)로 말한다. 실무에서 필요한 것도 대개 이쪽이다	5-3

한 줄로 줄이면
5-1은 "ERGM은 이렇게 생겼다"였고, 5-2는 "그런데 그대로는 계산이 안 된다"이다. 5-3부터 5-8까지는 전부 $\kappa$ 를 피해 가는 방법과 피해 간 대가로 생기는 문제(퇴화, 수렴 실패)에 관한 이야기다.

13. 교실 적용 (Classroom Application)

13-1. 우리 반에서 실제로 무엇이 계산되고 무엇이 안 되는가 (What Can and Cannot Be Computed for Your Class)

단위	$n$	$N$	$2^N$	$\kappa$ 계산
모둠 하나	4	6	64	연필로 가능 — 오늘 연습문제 2
모둠 하나 (5명)	5	10	1,024	R로 즉시 — 오늘 §10
분단	8	28	2.7억	몇 초. 여기가 끝
한 학급	30	435	$8.9\times10^{130}$	불가능 — MCMC로 근사
한 학년 6학급	180	16,110	$10^{4849}$	불가능

주목할 점은 모둠 하나는 정확히 계산된다는 것이다. "교사가 직접 손으로 확인해 볼 수 있는 규모"가 실재한다는 뜻이고, 4명 모둠에서 $\kappa$ 를 직접 조립해 보는 경험은 30명 학급에서 ergm이 무엇을 근사하고 있는지를 이해하는 가장 빠른 길이다.

13-2. 동료 교사에게 말할 수 있는 것과 없는 것 (What to Say to a Colleague, and What Not To)

말	가능?	이유
"우리 반 교우관계도가 이렇게 나올 확률은 0.0003입니다"	✗	$\kappa$ 를 모르므로 절대 확률은 계산 불가. 게다가 $8.9\times10^{130}$ 가지 중 하나이므로 어떤 망이든 확률은 사실상 0이다
"이미 공통 친구가 있는 두 학생이 서로 친구일 오즈는, 공통 친구가 없을 때보다 $e^{\hat\theta_2}$ 배 높습니다"	✓	비이므로 $\kappa$ 가 약분된다(§7). 다만 "다른 조건이 모두 같을 때"를 반드시 붙여야 한다
"삼각형 계수가 0.66이니 뭉침 경향이 $e^{0.66}=1.93$ 배 강합니다"	△	방향은 맞지만 무엇의 1.93배인지를 말해야 한다. 확률이 아니라 오즈이고, 그것도 간선 하나를 추가할 때의 조건부 오즈다 (§5-1의 2.488배 vs 2.718배 차이)
"작년 반은 $\hat\theta_2=0.4$ , 올해는 $0.8$ 이니 올해가 두 배 잘 뭉칩니다"	✗	두 가지 이유로 안 된다. ① $e^{0.8}/e^{0.4}=e^{0.4}=1.49$ 배지 두 배가 아니다. ② 학급 크기가 다르면 계수를 직접 비교할 수 없다(5-1 §13, 단원 1-5의 학급 규모 함정)
"`ergm`을 두 번 돌렸는데 계수가 달라요. 뭔가 잘못됐나요?"	✓ 정상	MCMC 근사이므로 당연하다(§11). 단, 흔들림이 표준오차에 육박하면 수렴을 의심해야 한다(5-7)

수업에서 그대로 쓸 수 있는 활동 — "4명 모둠, 64가지"
학생 4명(A·B·C·D)을 세우고 "친하다/아니다"를 정할 짝이 6쌍임을 세게 한다. 가능한 경우가

2^6=64

가지임을 확인한 뒤, 64장을 조별로 나눠 그려 보게 한다.
그리고 묻는다 — "이 중 삼각형이 하나라도 있는 그림은 몇 장일까?" (답: 삼각형 수가 1 이상인 것

4+12+6+1=23

장. §15 연습문제 2 참조)
학생들이 실제로 세어 보면 "가능한 관계 지도가 이렇게 많다"와 "그중 뭉친 모양은 일부다"를 동시에 체감한다. 30명 학급이면 이 64가

8.9\times10^{130}

이 된다는 말을 덧붙이면 충분하다.

14. 연습문제 (Exercises)

연습문제 1 — $n=3$ 에서 계수를 바꿔 본다
같은 정점 3개 모형에서 이번에는

\theta_1=-1

\theta_2=2

로 둔다. "간선은 더 드물게, 삼각형은 더 좋아하는" 모형이다.

(가)

\kappa(-1,2)

를 네 항을 모두 적어 계산하라. (

e^{-1}=0.3678794

e^{-2}=0.1353353

e^{-3}=0.0497871

)
(나) 그래프 8개의 확률을 전부 구하고 합이 1인지 확인하라.
(다)

\theta_2=0

일 때(=5-1 모형)의 삼각형 확률과 비교해 배율을 구하라. 그 배율이

e^{2}=7.3891

이 아닌 이유를 식으로 설명하라.
(라) 이번에도 삼각형과 간선 1개짜리 그래프의 확률이 정확히 같다. 우연인가? §5-2의 조건식으로 답하라.
먼저 풀고 나서 §15 해설과 맞춰 볼 것.

연습문제 2 — $n=4$ 에서 $\kappa$ 를 직접 조립한다 (오늘의 본 문제)
정점 4개짜리 무방향 망. 쌍은

N=\binom42=6

개, 그래프는

2^6=64

개다.

(가) 간선

m

개짜리 그래프가 몇 개인지

m=0,1,\dots,6

에 대해 적고, 합이 64인지 확인하라.
(나) 삼각형 수

t

를 센다. 다음 표의 빈칸(?)을 채워라. 힌트를 붙여 둔다.

$m$	그래프 수	$t$ 별 개수	힌트
0, 1, 2	1, 6, 15	전부 $t=0$	삼각형에는 간선 3개가 필요하다
3	20	`?`개가 $t=1$ , `?`개가 $t=0$	간선 3개로 만들 수 있는 모양은 삼각형·별·경로 셋뿐이다. 삼각형은 정점 3개를 고르는 $\binom43$ 가지
4	15	`?`개가 $t=1$ , `?`개가 $t=0$	뺀 간선 2개로 세는 게 쉽다. 뺀 두 간선이 정점을 공유하는가 아닌가로 갈린다
5	6	전부 $t=$ `?`	$K_4$ 에는 삼각형이 4개. 간선 하나를 빼면 그 간선이 든 삼각형이 몇 개 죽는가?
6	1	$t=$ `?`	$K_4$ . $\binom43$

(다) (가)·(나)를 합쳐

\kappa(\theta_1,\theta_2)

를 아홉 항으로 적어라. 그리고

\theta_2=0

을 넣으면

(1+e^{\theta_1})^{6}

이 되는지 검산하라.
(라)

\theta_1=-0.5,\ \theta_2=0.8

에서

\kappa

의 값을 구하고,

P(K_4)

와

P(\text{4-사이클 하나})

를 계산하라. 또 paw(삼각형에 꼬리가 하나 붙은 모양,

m=4,t=1

) 하나와 4-사이클 하나의 확률 비가

e^{0.8}

임을 §7의 공식으로 계산 없이 설명하라.
먼저 풀고 나서 §15 해설과 맞춰 볼 것.

15. 해설과 답 (Solutions)

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

(가) $\kappa(-1,2)$ — 항이 네 개다. $\kappa=1+3e^{\theta_1}+3e^{2\theta_1}+e^{3\theta_1+\theta_2}$ 에 $\theta_1=-1,\theta_2=2$ 를 넣는다. 마지막 지수를 먼저 정리하면 $3(-1)+2=-1$ 이므로 $e^{3\theta_1+\theta_2}=e^{-1}$ 이다.

항	무엇의 합인가	지수	지수함수 값	개수	기여
1	빈 그래프	$0$	$1$	1	1.0000000
2	간선 1개	$\theta_1=-1$	0.3678794	3	1.1036383
3	간선 2개 (경로)	$2\theta_1=-2$	0.1353353	3	0.4060058
4	삼각형	$3\theta_1+\theta_2=-1$	0.3678794	1	0.3678794

\kappa(-1,2)=1.0000000+1.1036383+0.4060058+0.3678794=2.8775236

답 (가)

\kappa(-1,2)=1+3e^{-1}+3e^{-2}+e^{-1}=2.8775236

(나) 확률 8개 — 각 점수를 $\kappa=2.8775236$ 으로 나눈다.

#	$m$	$t$	점수	$P=$ 점수 $/\kappa$	개수	소계
1	0	0	1	$1/2.8775236=$ 0.3475210	1	0.3475210
2–4	1	0	0.3678794	$0.3678794/2.8775236=$ 0.1278458	3	0.3835375
5–7	2	0	0.1353353	$0.1353353/2.8775236=$ 0.0470319	3	0.1410956
8	3	1	0.3678794	0.1278458	1	0.1278458

0.3475210+0.3835375+0.1410956+0.1278458=1.0000000\ \checkmark

답 (나) 빈 그래프 0.3475210, 간선 1개짜리 각각 0.1278458(셋), 간선 2개짜리 각각 0.0470319(셋), 삼각형 0.1278458. 합은 정확히 1.

(다) 배율 — $\theta_2=0$ 이면 $\kappa_0=(1+e^{-1})^3=(1.3678794)^3=2.5594312$ 이고 삼각형 점수는 $e^{3\theta_1}=e^{-3}=0.0497871$ 이다.

P_{\theta_2=0}(\triangle)=\frac{0.0497871}{2.5594312}=0.0194524, \qquad \text{배율}=\frac{0.1278458}{0.0194524}=6.5722418

왜 $e^{2}=7.3890561$ 이 아닌가. 분자는 $e^{\theta_2}$ 배가 되었지만 분모 $\kappa$ 도 커졌다.

\frac{P_{\theta_2=2}(\triangle)}{P_{\theta_2=0}(\triangle)} =\frac{e^{3\theta_1}e^{\theta_2}/\kappa_{2}}{e^{3\theta_1}/\kappa_{0}} =e^{\theta_2}\cdot\frac{\kappa_{0}}{\kappa_{2}} =7.3890561\times\frac{2.5594312}{2.8775236} =7.3890561\times0.8894577=6.5722418\ \checkmark

답 (다) 배율은 6.5722배.

e^2=7.3891

이 아닌 이유는

\kappa

가

2.5594\to2.8775

로 함께 커졌기 때문이며, 정확한 배율은

e^{\theta_2}\cdot\kappa_0/\kappa_2

이다.
확률의 총합이 1로 묶여 있으므로, 한 그래프의 확률을 올리면 나머지의 확률은 반드시 내려간다. 실제로 빈 그래프는

1/2.5594312=0.3907\to0.3475

로 내려갔다.

(라) 삼각형과 간선 1개의 확률이 같은 이유 — §5-2의 조건은 $2\theta_1+\theta_2=0$ 이었다. 여기서

2\theta_1+\theta_2=2(-1)+2=-2+2=0

답 (라) 우연이 아니다.

2\theta_1+\theta_2=0

이라는 조건에 정확히 걸렸기 때문이다. 이때 삼각형의 지수

3\theta_1+\theta_2

가 간선 1개의 지수

\theta_1

과 같아지므로 (

3\theta_1+\theta_2=\theta_1+(2\theta_1+\theta_2)=\theta_1+0=\theta_1

) 점수가 같고, 같은

\kappa

로 나누니 확률도 같다.
해석: 간선 하나를 더 긋는 대가

2|\theta_1|=2

와 삼각형이 완성될 때의 이득

\theta_2=2

가 정확히 상쇄되는 지점이다. 이 선 위에서는 "혼자 뻗은 관계 하나"와 "완전히 뭉친 삼인조"가 똑같이 그럴듯하다.

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

(가) $m$ 별 그래프 수 — 쌍 6개 중 $m$ 개를 고르는 것이므로 $\binom6m$ 이다.

$m$	0	1	2	3	4	5	6	합
$\binom6m$	1	6	15	20	15	6	1	64

답 (가)

1,6,15,20,15,6,1

. 합

=64=2^6

✔

(나) 삼각형 수 세기 — 한 줄씩 간다.

$m=0,1,2$ : 삼각형에는 간선이 3개 필요하다. 간선이 2개 이하면 불가능하므로 전부 $t=0$ . 그래프 $1+6+15=22$ 개.

$m=3$ : 간선 3개로 만들 수 있는 모양은 세 가지뿐이다.

모양	개수	세는 법	$t$
삼각형	4	삼각형을 이룰 정점 3개를 고르는 $\binom43=4$ 가지. 남은 정점 1개는 외톨이	1
별 $K_{1,3}$	4	중심이 될 정점을 고르는 4가지. 나머지 셋이 전부 중심에 붙는다	0
경로 $P_4$	12	나머지. $20-4-4=12$ . (직접 세면: 정점 4개의 배열 $4!=24$ 가지, 뒤집으면 같으니 $24/2=12$ )	0

따라서 $t=1$ 이 4개, $t=0$ 이 16개. 검산 $4+4+12=20$ ✔

$m=4$ : 힌트대로 뺀 간선으로 센다. $K_4$ (간선 6개)에서 2개를 빼는 $\binom62=15$ 가지. 뺀 두 간선의 관계가 두 경우로 갈린다.

뺀 두 간선	개수	세는 법	남는 모양	$t$
정점을 공유하지 않음 (완전 매칭)	3	$K_4$ 의 완전 매칭은 $\{12,34\},\{13,24\},\{14,23\}$ 의 3가지	4-사이클 $C_4$	0
정점을 공유함	12	$15-3=12$	paw (삼각형 + 꼬리)	1

왜 그런가. 4-사이클에는 삼각형이 없다(사이클 길이가 4). paw는 삼각형 하나와 거기 붙은 간선 하나이므로 $t=1$ . 따라서 $t=1$ 이 12개, $t=0$ 이 3개.

$m=5$ : $K_4$ 에서 간선 하나를 뺀 것. 6가지. $K_4$ 에는 삼각형이 $\binom43=4$ 개 있고, 임의의 한 간선은 그중 2개에 들어 있다(그 간선의 두 끝점 + 나머지 두 정점 각각). 그 2개가 죽으므로 $t=4-2=2$ . 6개 모두 $t=2$ .

$m=6$ : $K_4$ 하나. $t=\binom43=4$ .

답 (나)

$m$	0	1	2	3		4		5	6
$t$	0	0	0	0	1	0	1	2	4
개수	1	6	15	16	4	3	12	6	1

검산:

1+6+15+16+4+3+12+6+1=64

✔
삼각형이 하나라도 있는 그래프는

4+12+6+1=

23개 (§13-2 활동의 답).

(다) $\kappa$ 아홉 항 — 위 표의 각 칸이 항 하나가 된다.

\begin{aligned} \kappa(\theta_1,\theta_2) ={}& 1 + 6e^{\theta_1} + 15e^{2\theta_1} + 16e^{3\theta_1} + 4e^{3\theta_1+\theta_2}\\ &+ 3e^{4\theta_1} + 12e^{4\theta_1+\theta_2} + 6e^{5\theta_1+2\theta_2} + e^{6\theta_1+4\theta_2} \end{aligned}

$\theta_2=0$ 을 넣으면 $e^{\theta_2}$ 꼴이 전부 1이 되므로 같은 $m$ 끼리 합쳐진다.

\begin{aligned} \kappa(\theta_1,0) &= 1 + 6e^{\theta_1} + 15e^{2\theta_1} + \underbrace{(16+4)}_{20}e^{3\theta_1} + \underbrace{(3+12)}_{15}e^{4\theta_1} + 6e^{5\theta_1} + e^{6\theta_1}\\[3pt] &= \sum_{m=0}^{6}\binom6m\left(e^{\theta_1}\right)^m = \left(1+e^{\theta_1}\right)^{6}\ \checkmark \end{aligned}

답 (다) 위의 아홉 항 식.

\theta_2=0

에서 계수가

1,6,15,20,15,6,1

로 합쳐져 정확히

(1+e^{\theta_1})^6

이 된다. 이 검산은 반드시 해 볼 것 — (나)에서 개수를 하나라도 잘못 셌으면 여기서 이항계수가 어긋난다.

(라) 수치 — $\theta_1=-0.5,\ \theta_2=0.8$ . 항별로 쌓는다.

$m$	$t$	개수	지수 $m\theta_1+t\theta_2$	지수함수 값	기여 (개수×값)
0	0	1	$0$	1.0000000	1.0000000
1	0	6	$-0.5$	0.6065307	3.6391840
2	0	15	$-1.0$	0.3678794	5.5181916
3	0	16	$-1.5$	0.2231302	3.5700826
3	1	4	$-1.5+0.8=-0.7$	0.4965853	1.9863412
4	0	3	$-2.0$	0.1353353	0.4060058
4	1	12	$-2.0+0.8=-1.2$	0.3011942	3.6143305
5	2	6	$-2.5+1.6=-0.9$	0.4065697	2.4394180
6	4	1	$-3.0+3.2=+0.2$	1.2214028	1.2214028
$\kappa(-0.5,\ 0.8)$					23.3949565

P(K_4)=\frac{e^{0.2}}{\kappa}=\frac{1.2214028}{23.3949565}=0.0522080, \qquad P(C_4\ \text{하나})=\frac{e^{-2}}{\kappa}=\frac{0.1353353}{23.3949565}=0.0057848

paw 하나는 $P=e^{-1.2}/\kappa=0.3011942/23.3949565=0.0128743$ . 그 비를 $\S7$ 의 공식으로 계산 없이 보면 — paw와 4-사이클은 둘 다 $m=4$ 이고 $t$ 만 1과 0으로 다르므로

\mathbf g(\text{paw})-\mathbf g(C_4)=(4,1)-(4,0)=(0,1) \quad\Longrightarrow\quad \frac{P(\text{paw})}{P(C_4)}=\exp\{\theta_1\cdot0+\theta_2\cdot1\}=e^{0.8}=2.2255409

검산: $0.0128743/0.0057848=2.2255409$ ✔

답 (라)

\kappa(-0.5,0.8)=\mathbf{23.3949565}

P(K_4)=\mathbf{0.0522080}

P(C_4\ \text{하나})=\mathbf{0.0057848}

P(\text{paw 하나})=\mathbf{0.0128743}

. paw와 4-사이클의 비는

e^{0.8}=\mathbf{2.2255}

.
왜 계산 없이 알 수 있었나: 두 그래프는 간선 수가 같다. 그래서

\theta_1

이 약분되고,

\kappa

도 약분된다. 남는 것은 삼각형 수의 차

1-0=1

뿐이므로 비는 정확히

e^{\theta_2}

다.
의미: "간선 4개를 같은 개수로 쓰되 뭉쳐 놓느냐 둥글게 펴 놓느냐"의 선호가 정확히

e^{\theta_2}

배다. 삼각형 계수는 바로 이것을 재는 값이다.

교실 해석 — 모둠 4명, 간선 4개를 어떻게 놓을 것인가
4명 모둠에서 "친한 짝이 4쌍"이라는 사실은 같은데 모양이 다를 수 있다.
• 4-사이클: A–B–C–D–A. 모두가 두 명씩과 친하지만 삼인조가 하나도 없다. 고리형이라 관계가 얇게 퍼져 있다.
• paw: A–B–C가 뭉치고 D가 그중 한 명에게만 붙어 있다. 단단한 삼인조 + 주변부 한 명이다.
간선 수만 세는 지표(밀도·평균차수)로는 이 둘이 완전히 같다.

\theta_2=0.8

짜리 모형은 후자를 2.23배 더 그럴듯하게 본다.
현장에서 중요한 것도 대개 후자다 — D가 소외될 위험은 paw에서 훨씬 크다. 모둠 편성을 볼 때 "몇 쌍이 친한가"가 아니라 "어떤 모양으로 친한가"를 봐야 하는 이유이고, ERGM에 삼각형 항을 넣는다는 것은 정확히 그 모양을 모형에 넣는다는 뜻이다.

다음 단원 예고 — 5-3. 조건부 로그오즈와 변화 통계량 (Change Statistics)
오늘

\kappa

가 약분되는 자리를 딱 하나 찾았다 — 확률의 비다(§7). 5-3에서는 그 비를 칸 하나만 다른 두 망 사이에서 계산해,

\operatorname{logit}P\big(A[i,j]=1\mid \text{나머지 전부}\big) =\boldsymbol\theta^\top\boldsymbol\delta_{ij}(y)

라는 식을 손으로 유도한다.

\boldsymbol\delta_{ij}(y)

가 변화 통계량이고, 오늘 §7에서 구한

(1,1)

이 바로 그 예다.
이 식이 ERGM 계수 해석의 전부이며, 동시에

\kappa

없이 추정하는 첫 번째 방법 (의사가능도 MPLE)의 출발점이다. 가라테에서 삼각형 항의 변화 통계량을 실제로 손으로 세어 볼 것이다.