실전 — 가라테 분열 예측과 FMH 고교 하위집단

1. 지난 시간 연습문제 확인 (Review of Last Session's Exercises)

연습문제 1 — 12명 학급의 E-I와 $r$ (Exercise 1: E-I and Assortativity in a Class of 12)

남 S1–S5, 여 S6–S12, 간선 14개였습니다.

연습문제 2 — 30명 학급의 전학생 3명 (Exercise 2: Three Transfer Students in a Class of 30)

내부 1개, 외부 14개 → 관측 $EI = 13/15 = +0.8667$. 그런데 3명 집단의 기대값은

관측이 기대보다 낮습니다. 담임의 “양수니까 잘 융화됐다”는 해석은 틀렸고, 안쪽 밀도 $1/3$이 바깥쪽 $14/81$의 약 1.9배라 오히려 더 뭉쳐 있습니다. 기대 E-I가 0이 되는 지점은 $k=(2\cdot 30+1)/3 = 20.33$ — $k=20$까지는 $+0.0256$로 양수, $k=21$부터 $-0.0526$으로 음수입니다.

2. 오늘의 질문: 정답지가 있는 네트워크 (Today's Question: A Network with an Answer Key)

3단계에서 우리는 하위집단을 찾는 도구를 여덟 개쯤 만들었습니다.

여기엔 한 가지가 통째로 빠져 있습니다. 이 도구들이 맞기는 하는가?

지금까지는 답을 낼 수 없었습니다. 우리 반 무리 구조에 “정답지”가 없으니까요. 알고리즘이 “S1~S3이 한 무리”라고 해도, 그게 맞는지 틀린지 검증할 외부 기준이 없습니다. $Q$는 알고리즘이 스스로 매기는 점수이지, 정답과의 거리가 아닙니다.

3. 데이터와 정답지 (The Data and the Answer Key)

정점 34개, 간선 78개. 정답지는 다음과 같습니다.

1번이 사범, 34번이 관리자입니다(차수도 각각 16, 17로 1·2위). 78개 간선 중 진영을 넘는 간선은 10개뿐입니다.

단원 3-7의 도구를 이 정답지에 그대로 적용하면:

두 진영의 차수합이 76 : 80으로 거의 같아서 기준선 $EI^{\text{exp}}$이 사실상 0입니다. 그래서 이 데이터에서만은 E-I의 크기와 $r$이 거의 같은 값이 됩니다(0.7436 vs 0.7434). 단원 3-7 §12의 항등식

4. 예측 도구 ① 최소절단 — Zachary의 원래 방법 (Minimum Cut)

Zachary 자신이 1977년 논문에서 쓴 방법은 커뮤니티 탐지가 아니었습니다(그런 건 아직 없었습니다). 그는 최대유량–최소절단을 썼습니다. 발상은 단순합니다.

정보(혹은 갈등)가 간선을 따라 흐른다고 보면, 1번에서 34번으로 흘려보낼 수 있는 최대유량은 그 둘을 갈라놓는 최소절단의 크기와 같습니다(최대유량–최소절단 정리).

max_flow(gk, source=1, target=34)$value
[1] 10

10. 그리고 실제 분열의 교차 간선도 정확히 10개였습니다. 즉 실제 분열은 1번–34번을 가르는 최소절단 중 하나입니다. Zachary의 방법은 몇 개를 끊어야 하는가는 정확히 맞혔습니다.

그런데 R이 실제로 돌려준 절단은 이것입니다.

차이는 딱 한 줄, 10번을 어느 쪽에 두는가입니다. R은 10번을 Mr. Hi 쪽에 두었고, 실제로 10번은 Officer를 따라갔습니다. 정확도 33/34.

5. 예측 도구 ② Fiedler 벡터 (Spectral Bisection and the Fiedler Vector)

두 번째 방법은 대수적입니다. 라플라시안 행렬을 만듭니다.

즉 $L[i,i]=\deg(i)$, $i\neq j$면 $L[i,j]=-A[i,j]$. 이 행렬의 성질:

• 모든 행의 합이 0 → $\mathbf{1}=(1,1,\dots,1)$이 고유값 0의 고유벡터. 항상 있습니다.
• 고유값 0의 중복도가 컴포넌트 개수. 가라테는 연결되어 있으니 0이 하나뿐.
• 두 번째로 작은 고유값 $\lambda_2$를 대수적 연결도라 하고, 그 고유벡터를 Fiedler 벡터라 합니다.

L <- diag(degree(gk)) - as_adjacency_matrix(gk, sparse=FALSE)
sort(eigen(L, symmetric=TRUE)$values)[1:5]
[1] 0.000000 0.468525 0.909248 1.125011 1.259404

$\lambda_2 = 0.4685$. Fiedler 벡터는 34명에게 실수 하나씩을 붙여 줍니다. 부호로 나누면 이분할이 됩니다.

부호 분할의 정확도도 33/34. 다만 이번에 틀린 것은 10번이 아니라 3번입니다.

6. 예측 도구 ③ 커뮤니티 탐지 (Community Detection)

단원 3-4의 알고리즘들을 그대로 돌립니다. 이들은 진영을 2개로 나누라는 말을 듣지 않았으므로 자기가 좋다고 생각하는 개수로 나눕니다.

계층적 알고리즘(GN, walktrap, fast greedy)은 cut_at(no=2)로 2집단에서 잘라 정답과 1:1로 대조할 수 있습니다. 그 결과는 §10 채점표에 모았습니다.

7. 손 계산 — 실제 분할의 모듈러리티 (Modularity of the True Split)

단원 3-3에서 쓴 형태를 그대로 씁니다.

$m_c$ = 집단 $c$ 안쪽 간선 수, $d_c$ = 집단 $c$ 구성원의 차수 합, $m=78$, $2m=156$.

부품 세기 (Counting the Pieces)

항을 전부 전개 (Every Term Expanded)

이 축약형을 쓰면 검산이 한 줄입니다.

8. 손 계산 — 10번을 옮기면 $Q$가 오른다 (Moving Node 10 Raises Q)

이제 §4에서 R이 고른 오답(10번을 진영 1로)의 $Q$를 같은 방식으로 계산합니다. 10번의 이웃은 3번(진영 1)과 34번(진영 2), 딱 둘입니다.

축약형에 넣습니다. 차수합이 78 : 78로 정확히 반반이 되었다는 데 주목하세요.

9. 채점 도구: ARI 손 계산 (Adjusted Rand Index by Hand)

지금까지 compare(..., method="adjusted.rand")를 여러 단원에서 그냥 써 왔습니다. 오늘은 손으로 계산합니다. 정답지가 있는 오늘이 적기입니다.

9-1. 발상: 쌍(pair)을 세는 것 (The Idea: Counting Pairs)

두 분할이 얼마나 비슷한지를 재는 방법은 여러 가지지만, ARI는 학생 쌍을 셉니다. 34명이면 쌍은 $\binom{34}{2}=561$개. 각 쌍마다 묻습니다 — 두 분할이 이 쌍을 같은 취급 했는가?

“같은 취급”은 둘 다 같은 집단에 넣었다 또는 둘 다 다른 집단에 넣었다입니다. 그 비율이 랜드 지수 $RI$. 문제는 $RI$가 우연히도 높게 나온다는 것 — 단원 3-7의 기준선 문제가 그대로 반복됩니다. 그래서 ARI는 관측 − 기대를 최대 − 기대로 나눕니다.

9-2. 교차표 만들기 — Girvan-Newman(2집단) vs 정답 (Building the Contingency Table)

GN을 2집단에서 자른 결과와 정답을 표로 교차시킵니다. $n_{ij}$ = 예측 $i$이면서 실제 $j$인 사람 수.

빨간 칸의 1명이 3번입니다(GN은 3번을 Officer 쪽으로 보냄).

9-3. 세 개의 합을 0인 항까지 전부 전개 (Three Sums, Every Term Included)

① 칸별 합 — 4개 칸 전부, $\binom{0}{2}=0$과 $\binom{1}{2}=0$도 생략하지 않습니다.

② 행 합 — 예측 분할이 같이 묶은 쌍의 총수.

③ 열 합 — 정답 분할이 같이 묶은 쌍의 총수.

④ 전체 쌍: $\binom{34}{2}=\dfrac{34\cdot 33}{2}=561$.

9-4. 조립 (Putting It Together)

compare(gn2, truth, method="adjusted.rand")
[1] 0.882302

10. 채점표 — 여덟 가지 방법 전면 대조 (The Scoreboard)

참고로 정답 분할이 형편없는 것은 아닙니다. 무작위 2분할 20,000개를 만들어 $Q$를 재면 평균 $-0.0248$, 최댓값 $0.301$이고, 정답 분할의 $0.3715$는 20,000개 전부보다 높습니다. “$Q$가 의미 없다”가 아니라 “$Q$의 최댓값이 곧 진실은 아니다”입니다.

11. 함정 ①: ARI는 ‘세분’을 벌준다 (ARI Penalizes Refinement)

채점표에서 가장 이상한 줄은 Louvain입니다. ARI 0.5414로 꼴찌인데 진영 복원은 34/34, 만점입니다. 어떻게 둘 다 참일 수 있을까요?

$C_1\cup C_2$는 정확히 진영 1 16명 전원, $C_3\cup C_4$는 정확히 진영 2 18명 전원. Louvain은 진영 경계를 단 한 번도 넘지 않았습니다. 다만 각 진영을 둘로 더 쪼갰을 뿐입니다. 이런 관계를 세분(refinement)이라고 합니다.

그래서 채점은 두 가지를 해야 합니다.

12. 틀린 정점들의 정체 (Who the Misclassified Nodes Are)

여덟 가지 방법이 틀린 정점은 딱 세 개뿐입니다 — 3번, 10번, 14번. 누구인지 봅시다.

13. 함정 ②: 같은 알고리즘이 매번 다른 답을 준다 (Stochastic Algorithms)

여기서 실무에서 제일 자주 사고가 나는 지점을 짚습니다. 단원 3-4에서 배운 알고리즘 중 일부는 난수를 씁니다. 같은 데이터, 같은 함수인데 실행할 때마다 결과가 달라집니다.

가라테 클럽에 100번씩 돌린 결과입니다.

결정적(deterministic)인 것들 — Girvan-Newman, walktrap, fast greedy, Fiedler, 최소절단 — 은 몇 번을 돌려도 같은 답입니다. 문제는 Louvain과 label propagation입니다.

실무 지침은 셋입니다.

14. 3단계 도구 전부로 본 가라테 (All Stage-3 Tools on the Karate Club)

커뮤니티 탐지 말고 나머지 도구들은 진영에 대해 무엇을 말하는지 훑습니다.

14-1. 클리크 (3-1) (Cliques)

극대 클리크 36개(크기 2:11개, 3:21개, 4:2개, 5:2개). 이 중 진영이 섞인 것은 9개:

{3,10} {3,28} {3,29} {1,32} {20,34} {14,34} {2,31} {3,9,33} {1,3,9}

9개 중 5개에 3번이 들어 있습니다. 크기 5인 두 클리크 $\{1,2,3,4,8\}$, $\{1,2,3,4,14\}$는 둘 다 진영 1 안에 완전히 들어 있습니다.

14-2. $k$-코어 (3-2) (k-Cores)

최대 코어는 4-코어 10명: 1 2 3 4 8 9 14 31 33 34. 진영 1이 6명, 진영 2가 4명으로 양쪽이 섞여 있습니다. $k$-코어는 “누가 중심에 있는가”를 말하지 “어느 편인가”는 말하지 않습니다. 당연합니다 — 코어는 차수 기반이라 진영과 무관합니다.

14-3. 구조적 등위성 (3-5) (Structural Equivalence)

인접행렬 행·열을 붙여 유클리드 거리로 묶으면(단원 3-5 방식):

14-4. 매개 중심성 (2-3) — 다리는 누구인가 (Betweenness: Who Is the Bridge)

1번·34번이 1·2위인 건 차수가 압도적이라 당연합니다. 주목할 것은 3번이 4위인데 차수는 10으로 3위라는 점 — 즉 차수 대비 매개가 큽니다. 32번은 차수 6으로 중위권인데 매개 5위. 이 둘이 진짜 다리입니다.

15. 정답지가 없는 네트워크: FMH 고교 (A Network Without an Answer Key)

가라테는 34명이고 정답지가 있습니다. 이제 현실에 가까운 쪽으로 갑니다 — faux.magnolia.high, 1,461명 고등학교 친구관계망입니다.

거대 컴포넌트 439명만 떼어 보면 간선 573개, 밀도 0.00596, 지름 40, 평균거리 16.88입니다.

클리크와 코어를 먼저 봅니다(단원 3-1, 3-2).

16. FMH 하위집단 — 21개 집단은 학년의 세분인가 (Are the 21 Communities a Refinement of Grade?)

커뮤니티 탐지를 돌립니다. 먼저 전체 망에 그대로 돌리면 이런 일이 벌어집니다.

거대 컴포넌트(439명)만 떼어 다시 돌립니다.

ARI(학년)가 0.19밖에 안 됩니다. 가라테에서 배운 대로, ARI가 낮다고 곧바로 틀린 건 아닙니다. 세분인지 확인해야 합니다. 21개 집단의 학년 구성을 봅니다.

단원 3-7의 도구를 세 분할에 나란히 적용하면 순위가 명확해집니다(거대 컴포넌트 기준).

$r$은 assortativity_nominal과 정확히 일치합니다(학년 0.8190 ✓). 단원 3-7 §16의 경고 — “집단 수가 다른 분할끼리 E-I를 직접 비교하지 말라” — 가 여기서도 그대로 적용됩니다. Louvain의 E-I가 $-0.906$으로 가장 음수인 건 집단이 21개라 기준선이 $+0.888$까지 올라갔기 때문입니다. $r$로 비교해야 합니다.

17. 정답지가 없을 때 무엇을 믿는가: 합의 (Consensus)

FMH엔 정답지가 없습니다. ARI를 계산할 상대가 없습니다. 무엇을 믿어야 할까요?

답은 질문을 바꾸는 것입니다. “이 학생은 몇 번 집단인가?”는 실행마다 달라집니다. 집단 번호 자체가 임의니까요. 대신 이렇게 묻습니다 — “이 두 학생은 늘 같은 집단에 들어가는가?”

Louvain을 100번 돌려(시드 1~100) 거대 컴포넌트의 간선 573개마다 양 끝 두 사람이 같은 집단에 들어간 횟수를 셉니다.

평균 합의도는 0.951. 한편 서로 다른 두 실행끼리의 ARI는 평균 0.8247 (범위 0.6558~0.9610)에 불과합니다.

18. 가장 중요한 발견은 집단 밖에 있었다 (The Most Important Finding Was Outside the Groups)

3단계 내내 우리는 “누가 누구와 뭉치는가”를 물었습니다. FMH에서 그 질문에 답하다 보면 놓치는 사실이 하나 있습니다.

1,461명 중 524명(35.9%)이 아무와도 연결되어 있지 않습니다. 거기에 “단짝 한 명뿐”인 2인 컴포넌트가 64쌍(128명) 더 있습니다. 커뮤니티 탐지는 이 652명에 대해 아무 말도 하지 않았습니다 — 1인·2인 집단으로 처리하고 $Q$만 0.95로 부풀렸을 뿐입니다.

(다시 한 번 — 이 수치들은 모의 생성된 데이터의 것입니다. 실제 학교의 고립률로 인용하면 안 됩니다. 읽어야 할 것은 숫자가 아니라 “고립률을 속성별로 쪼개 보는 절차”입니다.)

19. R 검증 (R Verification)

library(igraph)

## --- 데이터: karate_net.txt 의 오류를 반드시 복원 (CLAUDE.md 참조) ---
kel <- as.matrix(read.table("karate_net.txt"))
gk  <- add_edges(simplify(graph_from_edgelist(kel, directed=FALSE)), c(9,31))
std <- c(16,9,10,6,3,4,4,4,5,2,3,1,2,5,2,2,2,2,2,3,2,2,2,5,3,3,2,4,3,4,4,6,12,17)
all(igraph::degree(gk) == std)
[1] TRUE

## --- 정답지 ---
f1    <- c(1,2,3,4,5,6,7,8,11,12,13,14,17,18,20,22)
truth <- ifelse(1:34 %in% f1, 1, 2)

## --- §7 실제 분할의 Q ---
modularity(gk, truth)
[1] 0.371466

## --- §8 10번을 옮기면 ---
v10 <- truth; v10[10] <- 1
modularity(gk, v10)
[1] 0.3717949          # 정답보다 +0.000329 높다

## --- §4 최소절단 ---
mf <- max_flow(gk, source=1, target=34); mf$value
[1] 10
mcp <- ifelse(1:34 %in% as.integer(mf$partition1), 1, 2)
sum(mcp == truth)
[1] 33

## --- §5 Fiedler 벡터 ---
L  <- diag(igraph::degree(gk)) - as_adjacency_matrix(gk, sparse=FALSE)
ev <- eigen(L, symmetric=TRUE)
fv <- ev$vectors[, order(ev$values)][, 2]
sum(ifelse(fv < 0, 1, 2) == truth)     # 부호 방향에 따라 33 또는 1
[1] 33

## --- §9 ARI ---
gn2 <- as.integer(cut_at(cluster_edge_betweenness(gk), no=2))
compare(gn2, truth, method="adjusted.rand")
[1] 0.882302

## --- §11 세분 검사: 어떤 집단도 진영 경계를 넘지 않는가? ---
isref <- function(p) all(sapply(unique(p),
           function(c) length(unique(truth[p == c])) == 1))
set.seed(1); bestL <- as.integer(membership(cluster_louvain(gk)))
isref(bestL)                            # 최대 Q 분할일 때
[1] TRUE

## --- §16 FMH ---
library(ergm); library(intergraph)
data(faux.magnolia.high); fm <- faux.magnolia.high
G     <- asIgraph(fm)
grade <- network::get.vertex.attribute(fm, "Grade")   # igraph가 가리므로 명시
gcv   <- which(components(G)$membership == which.max(components(G)$csize))
gc    <- induced_subgraph(G, gcv)
set.seed(42); mb <- as.integer(membership(cluster_louvain(gc)))
tb  <- table(mb, grade[gcv])
sum(apply(tb, 1, max)) / sum(tb)        # 가중평균 순도
[1] 0.7129841
assortativity_nominal(gc, as.integer(factor(grade[gcv])))
[1] 0.8190

20. 교실 적용 (Classroom Application)

21. 연습문제 (Exercises)

22. 해설과 답 (Solutions)

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

(1) 세 개의 합 — 0인 항까지 전부

① 칸별 — 6개 칸 전부입니다.

② 행 합 (알고리즘이 같이 묶은 쌍)

③ 열 합 (담임이 같이 묶은 쌍)

④ $\binom{20}{2}=\dfrac{20\cdot 19}{2}=\boxed{190}$

(2) 기대·최대·ARI

(3) 보정하지 않은 랜드 지수

$RI$는 “같이 묶은 쌍이 일치” + “따로 묶은 쌍이 일치”를 전체 쌍으로 나눈 것입니다.

(4) 세분인가? 다수결 복원은?

(5) 두 숫자가 다른 이유

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

(1) 간선과 차수

(2) 정답 분할 $Q$

A = {S1,S2,S3,S4}, B = {S5,…,S10}. S10이 B이므로 S5–S10은 B 안쪽, S1–S10만 교차입니다.

(3) S10을 A로 옮긴 분할

이제 S1–S10이 A 안쪽, S5–S10이 교차가 됩니다.

(4) 알고리즘은 무엇을 고르는가

(5) S10의 개인 E-I와 §8과의 관계

S10의 이웃은 S1(A, 진영 밖)과 S5(B, 진영 안), 각 1명입니다.