모듈러리티 Q — 분할에 점수를 매기는 법

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

단원 3-2의 연습문제 두 개를 먼저 맞춰 본다. 자세한 전개는 노트 17 §16에 있고, 여기서는 핵심만 확인한다.

2. 오늘의 질문 — 판정에서 채점으로 (From Detection to Scoring)

교실에서 실제로 필요한 것은 이런 질문이다.

“우리 반 26명을 이렇게 4모둠으로 나눴는데, 이 나눔이 좋은 나눔인가? 저쪽 나눔보다 나은가? 몇 점짜리인가?”

이건 “이 5명이 클리크인가?”와 종류가 다른 질문이다.

왜 이게 새로운 질문인가 — 가라테 4-코어의 충격 (Why This Is a New Question)

지난 시간에 우리는 가라테 클럽에서 4-코어 10명 $\{1,2,3,4,8,9,14,31,33,34\}$을 찾았다. 이 10명의 내부 밀도는 0.556으로 전체 밀도 0.139의 4배였다. 대단히 빽빽한 집단이다.

그렇다면 “4-코어 10명” 대 “나머지 24명”으로 반을 나누면 좋은 분할일까? 오늘 배울 $Q$로 채점하면 이렇다.

왜 4-코어 분할은 0점인가? 4-코어 10명 사이의 간선은 25개지만, 그 10명이 바깥 24명과 맺은 간선은 38개다. 안보다 밖으로 더 많이 나간다. 빽빽하긴 하지만 그들은 반의 중심이지 한쪽 진영이 아니다.

오늘의 네트워크 — 단원 3-2의 $W$를 그대로 (Today's Network)

같은 8명 네트워크 $W$를 쓴다. 간선 12개, 차수는 $(3,3,3,3,5,3,2,2)$, $\sum_i d_i = 24$.

지난 시간에 3-코어이자 2-플렉스로 나온 $\{S1,\dots,S5\}$와, 삼각형 $\{S6,S7,S8\}$. 이 분할을 P1이라 부르고, 오늘 이것이 몇 점인지 손으로 계산한다.

3. 첫 시도와 그 실패 — 내부 간선 비율 (First Attempt: Internal Edge Fraction)

가장 먼저 떠오르는 채점법은 이것이다.

여기서 $m_c$는 모둠 $c$ 안쪽 간선 수, $m=12$는 전체 간선 수다. $W$에서 몇 개 분할에 대해 계산해 보자.

무엇이 빠졌나 (What Is Missing)

$f$는 “모둠 안에 간선이 몇 개 있나”만 센다. 물어야 할 것은 “모둠 안에 간선이 많은 편인가”다. 많고 적음을 말하려면 비교 대상이 있어야 한다.

“S6, S7, S8 사이에 간선이 3개 있다”는 사실 자체로는 아무 뜻도 없다.
“아무 관계도 없이 우연히 이었어도 3개쯤 나왔을 것인가?”를 물어야 뜻이 생긴다.

그 “우연히 나왔을 값”을 만드는 것이 다음 절의 영 모형이다.

4. 기준선을 만든다 — 영 모형 (The Null Model: Configuration Model)

반쪽 간선(스터브) 그림 (The Stub Picture)

네트워크의 간선 12개를 전부 가위로 반씩 자른다고 상상하자. 간선 하나가 반쪽 2개가 되므로 반쪽은 총 $2m = 24$개다. 그리고 반쪽은 각 정점에 차수만큼 붙어 있다.

이제 이 24개의 반쪽을 눈을 감고 아무렇게나 두 개씩 짝지어 다시 이어 붙인다. 그러면 차수는 그대로인데 연결 상대는 완전히 무작위인 네트워크가 만들어진다. 이것을 배열 모형(configuration model)이라 한다.

기대 간선 수의 손 계산 (Expected Edge Count by Hand)

정점 $i$의 반쪽 하나를 집었다고 하자. 남은 $2m-1$개 중 정점 $j$의 반쪽은 $d_j$개이므로, 그 하나가 $j$로 갈 확률은 $d_j/(2m-1)$이다. $i$의 반쪽이 $d_i$개이므로

$m$이 커지면 $2m-1 \approx 2m$이므로, 관례상 $d_i d_j / 2m$을 쓴다. 이 근사가 좋은 이유는 다음 절에서 확인할 깔끔한 성질들 때문이다.

검산 — 기대값의 총합은 $m$이어야 한다 (Check — the Expected Values Must Sum to m)

영 모형이 만든 그래프도 간선이 12개여야 말이 된다. 확인해 보자.

$W$에서는 $\tfrac12 \cdot 24^2/24 = 12 = m$. ✓ (R로도 확인했다 — §14.)

5. 모듈러리티 행렬 $B$ (The Modularity Matrix)

모든 쌍에 대해 “실제 − 기대”를 계산해 행렬로 만든다.

$W$는 $2m=24$이므로 모든 값이 24분의 몇으로 딱 떨어진다. 아래 표는 $24 \times B[i,j]$, 즉 분자만 적은 것이다 (예: $-9$는 $-9/24 = -0.375$를 뜻한다).

파란 칸 = 모둠 1 $\{S1,\dots,S5\}$ 블록, 초록 칸 = 모둠 2 $\{S6,S7,S8\}$ 블록 (§8에서 씀).

대각선은 왜 음수인가 (Why the Diagonal Is Negative)

$A[i,i] = 0$(자기 자신과는 친구가 아니다)이므로 $B[i,i] = 0 - d_i^2/2m = -d_i^2/2m$으로 항상 음수다. S5는 $-25/24 \approx -1.04$로 가장 큰 음수인데, 차수가 가장 크기 때문이다. 이건 결함이 아니라 영 모형이 자기 고리(self-loop)를 허용하기 때문에 생기는 정직한 대가다. 반쪽 24개를 무작위로 짝지으면 S5의 반쪽 두 개가 서로 만나는 일도 생긴다.

행합이 0이다 — 가장 좋은 검산 도구 (Row Sums Are Zero — the Best Check)

손으로 확인해 보자.

6. 정의 — $Q$ (Definition of Modularity)

이제 정의를 쓸 수 있다. 각 정점 $i$의 소속 모둠 번호를 $c_i$라 하고, 같은 모둠이면 1, 아니면 0인 표시 함수를 $\delta(c_i,c_j)$라 하자.

말로 옮기면 이렇다.

같은 값을 모둠별로 묶어 쓴 공식이 계산에는 훨씬 편하다. 모둠 $c$에 대해 $m_c$ = 모둠 안 간선 수, $D_c = \sum_{i \in c} d_i$ = 모둠 구성원 차수의 합이라 하면

$\left(D_c/2m\right)^2$의 직관 (The Intuition)

간선 하나를 무작위로 만든다고 하자. 반쪽 두 개를 뽑는데,

• 첫 번째 반쪽이 모둠 $c$에 속할 확률 $\approx D_c/2m$
• 두 번째 반쪽도 모둠 $c$에 속할 확률 $\approx D_c/2m$
• 둘 다 $c$에 떨어져 모둠 안 간선이 될 확률 $\approx (D_c/2m)^2$

모둠 1은 $17/24 = 0.708$, 즉 반쪽의 70.8%를 차지한다. 그러니 아무렇게나 이어도 간선의 $0.708^2 = 0.502$, 약 절반은 저절로 모둠 1 안에 떨어진다. 실제는 $8/12 = 0.667$이므로 초과분은 $0.667 - 0.502 = 0.165$뿐이다.

7. 두 공식이 같다는 증명 (Equivalence of the Two Formulas)

$\delta$ 형태와 모둠별 형태가 같은 값임을 확인한다. 두 줄이면 끝난다.

8. 손 계산 ① — 분할 P1의 $Q$ (Hand Calculation: Q of P1)

P1 $= \{S1,S2,S3,S4,S5\} \,|\, \{S6,S7,S8\}$. 두 가지 길로 각각 계산해 답을 맞춰 본다.

길 A — $B$ 행렬의 블록을 통째로 더한다 (Route A — Summing Blocks of B)

§5 표에서 파란 블록 25칸과 초록 블록 9칸의 값을 전부 더한다. 0인 항은 하나도 없다. 모든 칸을 다 쓴다 (단위: $1/24$).

블록 합을 24로 나눠 실제 값으로 되돌리고, $2m=24$로 한 번 더 나눈다.

길 B — 모둠별 공식 (Route B — the Per-Community Formula)

값 하나하나의 뜻 (What Each Value Means)

9. 두 항이 같았던 것은 우연이 아니다 (The Two-Community Identity)

§8에서 두 모둠의 항이 정확히 $95/576$로 같았다. 신기한 우연처럼 보이지만 모둠이 2개일 때는 언제나 그렇다. 증명해 보자.

모둠 A, B의 항을 각각 $T_A, T_B$라 하고 교차 간선 수를 $x$라 하자.

$W$에서 숫자로 확인 (Checking the Numbers on W)

10. 손 계산 ② — 극단 분할과 $Q$의 범위 (Extreme Partitions and the Range of Q)

극단 ① — 전원 한 모둠 $\Rightarrow Q = 0$ (항상) (Extreme 1 — Everyone in One Community)

모둠이 하나뿐이면 $m_c = m$, $D_c = 2m$이다.

§3에서 이 분할은 $f=1$로 만점이었다. $Q$에서는 정확히 0점이다. 게다가 이건 $W$만의 성질이 아니라 어떤 네트워크에서도 반드시 0이다. $Q$가 $f$의 실패를 정확히 겨냥해 고쳤음을 보여준다.

극단 ② — 8명 각자 따로 $\Rightarrow$ 음수 (Extreme 2 — All Singletons)

모든 모둠이 1명이면 $m_c = 0$이고 $D_c = d_i$다.

(마지막 줄은 $576$분의 값의 분자다.)

음수다. “아무도 같은 모둠이 아니다”는 우연히 나눈 것보다도 나쁘다. 당연하다 — 실제로 존재하는 12개 간선을 전부 모둠 밖으로 내보냈으니.

가장 나쁜 분할 (The Worst Partition)

$W$의 8명을 나누는 방법은 벨 수 $B_8 = 4140$가지다. 전부 계산해 보면(§14)

최저 분할을 보면 무슨 짓을 한 것인지 알 수 있다. 세 모둠 모두 안쪽 간선이 0개다. 서로 친구가 아닌 S1·S2를 굳이 묶고, 이웃이 아닌 S5와 S8을 묶었다. 즉 기대보다 적은 쌍만 골라 같은 모둠으로 만든 것이다. $B$ 행렬로 말하면 음수 칸만 블록 안에 가두는 나눔이다. 실제로

로, 세 모둠의 차수합 $D_c = (9, 8, 7)$의 제곱만 남아 전부 벌점이 된다.

11. 손 계산 ③ — 분할 비교표 (Comparing Partitions)

이제 $W$의 여러 분할을 같은 자로 잰다. 모둠이 2개인 것은 §9의 항등식 덕에 한쪽만 계산하고 2배했다. 분수는 전부 $576$분의 값이다.

P2가 왜 P1보다 나쁜지 — 한 줄로 보기 (Why P2 Loses to P1)

P2는 S6를 왼쪽 모둠에 넣었다. 얻은 것과 잃은 것을 재 보자.

12. 한 사람을 옮기면 (Moving One Node)

P1에서 한 명씩 반대편 모둠으로 옮겨 보면, 그 사람이 지금 자리에 얼마나 확실히 속해 있는지가 숫자로 나온다.

13. $Q$를 읽는 법 (Interpreting Q)

중요한 경고 — 무작위 그래프도 $Q$가 0이 아니다 (A Warning — Random Graphs Have Nonzero Q)

“전원 한 모둠”은 $Q=0$이지만, 그건 주어진 분할 하나의 값이다. 무작위 네트워크라도 4140가지를 다 뒤져 가장 좋은 분할을 고르면 $Q$는 꽤 커진다. $W$와 차수열이 똑같은($3,3,3,3,5,3,2,2$) 무작위 그래프 300개를 만들어 각각 최적 분할을 찾아 봤다.

또 하나의 함정 — 분할끼리만 비교할 것 (Another Pitfall — Compare Partitions Only)

$Q$는 $m$과 $d_i$로 정규화되어 있지만, 다른 네트워크끼리의 $Q$를 비교하는 것은 위험하다. 크기·밀도가 다르면 $Q$가 도달할 수 있는 최댓값 자체가 다르기 때문이다. $Q$는 같은 네트워크 위의 여러 분할을 줄 세울 때 가장 믿을 만하다.

14. R로 검증 (R Verification)

library(igraph)
nm <- paste0("S",1:8)
W  <- matrix(0,8,8,dimnames=list(nm,nm))
el <- rbind(c(1,3),c(1,4),c(1,5),c(2,3),c(2,4),c(2,5),c(3,5),c(4,5),
            c(5,6),c(6,7),c(6,8),c(7,8))
for(i in 1:nrow(el)){ W[el[i,1],el[i,2]] <- 1; W[el[i,2],el[i,1]] <- 1 }
gW <- graph_from_adjacency_matrix(W, mode="undirected")
d  <- degree(gW); m <- ecount(gW)          # d = 3 3 3 3 5 3 2 2 ,  m = 12

## --- 모듈러리티 행렬 B (24를 곱해 정수로 보기) ---
B <- W - outer(d,d)/(2*m)
24*B
#     S1  S2  S3  S4  S5  S6  S7  S8
#  S1 -9  -9  15  15   9  -9  -6  -6
#  S2 -9  -9  15  15   9  -9  -6  -6
#  S3 15  15  -9  -9   9  -9  -6  -6
#  S4 15  15  -9  -9   9  -9  -6  -6
#  S5  9   9   9   9 -25   9 -10 -10
#  S6 -9  -9  -9  -9   9  -9  18  18
#  S7 -6  -6  -6  -6 -10  18  -4  20
#  S8 -6  -6  -6  -6 -10  18  20  -4
rowSums(B)                                  # 0 0 0 0 0 0 0 0   (행합 = 0)
sum(B)                                      # 0
sum(outer(d,d))/(2*(2*m))                   # 12   (= m, 기대 간선 총합)

## --- 블록 합 (§8 길 A) ---
24*sum(B[1:5,1:5]); 24*sum(B[6:8,6:8])      # 95   95

## --- P1의 Q: 세 가지 방법 ---
P1 <- c(1,1,1,1,1,2,2,2)
modularity(gW, P1)                          # 0.3298611   ( = 190/576 )
sum(B[outer(P1,P1,"==")]) / (2*m)           # 0.3298611   (정의 그대로)
sum(sapply(1:2, function(c){ v <- which(P1==c)
  sum(W[v,v])/2/m - (sum(d[v])/(2*m))^2 }))  # 0.3298611   (모둠별 공식)

## --- 다른 분할들 ---
modularity(gW, c(1,1,1,1,1,1,2,2))          # 0.1111111   P2  = 64/576
modularity(gW, c(1,1,1,1,2,2,2,2))          # 0.1666667   P6  = 96/576
modularity(gW, rep(1,8))                    # 0           전원 한 모둠
modularity(gW, 1:8)                         # -0.1354167  전원 각자 = -78/576

## --- 전수 탐색: 8명을 나누는 4140가지 모두 ---
# 최대 Q = 0.3298611 = 190/576  →  {S1,S2,S3,S4,S5} | {S6,S7,S8}   (유일)
# 최소 Q = -0.3368056 = -194/576 →  {S1,S2,S6}|{S3,S4,S7}|{S5,S8} 등 4가지
# Q > 0 인 분할은 4140개 중 372개 (9.0%)

## --- 2-분할 항등식: 두 항이 늘 같은가 (126개 전수) ---
# 검사한 2-분할 126개, 두 항이 다른 경우 0개

## --- 완전 분리된 삼각형 K개: Q = 1 - 1/K ---
for(K in 2:5){
  g <- disjoint_union(replicate(K, make_full_graph(3), simplify=FALSE))
  cat(K, modularity(g, rep(1:K, each=3)), 1-1/K, "\n") }
# 2 0.5       0.5
# 3 0.6666667 0.6666667
# 4 0.75      0.75
# 5 0.8       0.8

가라테 클럽(§15) 부분은 이렇다.

kel <- as.matrix(read.table("karate_net.txt"))
gk  <- add_edges(simplify(graph_from_edgelist(kel, directed=FALSE)), c(9,31))   # 78개 교정판
hi  <- c(1,2,3,4,5,6,7,8,11,12,13,14,17,18,20,22)      # Mr.Hi 파벌 16명
fac <- ifelse(1:34 %in% hi, 1, 2)

modularity(gk, fac)                          # 0.3714661   실제 분열
modularity(gk, ifelse(coreness(gk)>=4, 1, 2))# 0.0046021   4-코어 | 나머지
modularity(gk, rep(1,34))                    # 0           전원 한 덩어리
modularity(gk, 1:34)                         # -0.0498       전원 각자

## 4-코어는 왜 0점인가: 안쪽 25개 vs 바깥으로 38개
c4 <- which(coreness(gk)>=4)
sum(as.matrix(as_adjacency_matrix(gk))[c4,c4])/2               # 25  (안쪽)
sum(degree(gk)[c4]) - 2*25                                     # 38  (교차)

## Louvain은 실행마다 결과가 달라진다 (100회)
set.seed(4); modularity(cluster_louvain(gk))                   # 0.4198  (관측 최댓값)
# 100회: Q 최소 0.3886 / 중앙값 0.4188 / 최대 0.4198,  모둠 수 4개가 99번·3개가 1번
#        최댓값 0.4198에 도달한 경우 30/100
#        실제 파벌 경계를 한 명도 넘지 않은 경우 43/100

## 결정적 방법 셋 (3회 돌려도 같은 값)
modularity(cluster_edge_betweenness(gk))     # 0.4013   크기 12-10-6-5-1
modularity(cluster_fast_greedy(gk))          # 0.3807   크기 17-9-8
modularity(cluster_walktrap(gk))             # 0.3532   크기 9-9-7-5-4

15. 실전 — 가라테 클럽의 실제 분열 (Karate Club: The Real Split)

가라테 클럽은 실제로 두 쪽으로 갈라졌다. 사범 Mr. Hi 편 16명, 회장 John A 편 18명. 이 실제로 일어난 분열이 몇 점인지 재 본다. (간선 78개짜리 교정판 데이터 — CLAUDE.md 참조.)

손 계산 — $m = 78$, $2m = 156$ (The Hand Calculation)

검산 ①: $33 + 35 + \underbrace{10}_{\text{교차}} = 78 = m$ ✓
검산 ②: $D_c = 2m_c + x$ → $2(33)+10 = 76$ ✓, $2(35)+10 = 80$ ✓
검산 ③: $76 + 80 = 156 = 2m$ ✓
검산 ④ (§9 항등식): 두 항이 같다 ✓

지난 단원의 4-코어와 비교 (Compared with the 4-Core)

기계는 사람보다 높은 점수를 낸다 (The Machine Scores Higher Than the Truth)

단원 3-4에서 배울 알고리즘들을 미리 돌려 봤다.

Louvain은 돌릴 때마다 답이 달라진다 (Louvain Answers Differently Each Run)

위 표의 Louvain 행에 set.seed(4)를 적어 둔 이유가 있다. Louvain은 정점을 훑는 순서를 무작위로 정하므로 실행할 때마다 결과가 바뀐다. 100번 돌려 봤다.

즉 “Louvain이 파벌을 정확히 세분한다”는 것은 절반도 안 되는 경우에만 참이다. 다른 결정적(deterministic) 방법 셋은 매번 같은 답을 내지만, 그 답도 모두 파벌이 섞인 모둠을 정확히 1개씩 갖고 있다.

가장 좋았던 Louvain 결과 ($Q = 0.4198$) (The Best Louvain Result)

이 결과에서는 Louvain이 실제 파벌을 틀리게 나눈 것이 아니라 더 잘게 쪼갰다: $C1 \cup C2 =$ Mr.Hi 파벌 16명, $C3 \cup C4 =$ John A 파벌 18명. $Q$가 0.3715에서 0.4198로 오른 것은 각 파벌 안에도 하위 그룹이 실제로 있기 때문이다.

C2 = $\{5, 6, 7, 11, 17\}$이 특히 선명한 예다. 이 다섯 명은 코어 번호가 $(3,3,3,3,2)$로 4-코어에 못 든 주변부인데, 그들끼리는 6개 간선(밀도 0.6, 전체 밀도 0.139의 4배)으로 촘촘히 얽혀 있다. 그리고 결정적으로 — 이 다섯 명의 바깥 이웃은 1번(Mr. Hi) 단 한 사람뿐이다. 바깥으로 나가는 간선 4개가 전부 1번을 향한다. 사범 한 명에게만 매달린, 자기들끼리 완결된 작은 무리인 것이다. $Q$는 이런 구조를 놓치지 않는다.

16. 교실 적용 (Classroom Application)

17. 연습문제 (Exercises)

    A2 ---- A3            B2 ---- B3
      \    /                \    /
       \  /                  \  /
        A1 ---------------- B1
     간선: A1-A2, A1-A3, A2-A3, B1-B2, B1-B3, B2-B3, A1-B1  (총 7개)

18. 해설과 답 (Solutions)

문제 1 해설 — P5의 $Q$ (Solution 1 — Q of P5)

① 무엇을 세는가. 각 모둠 안에 들어간 간선을 $W$의 간선 목록에서 하나씩 확인한다. 12개 간선을 하나도 빠뜨리지 않고 어디에 속하는지 분류한다.

검산: $3+1+3+5 = 12 = m$ ✓

② 차수합 $D_c$. 모둠 밖으로 나간 간선도 포함해서 전체 차수를 더한다.

③ 세 항 전개. 분모를 $576 = 24^2$로 통일한다. $m_c/m = m_c/12 = 48m_c/576$임에 주의.