커뮤니티 탐지 알고리즘

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

단원 3-3에서 낸 두 문제의 답을 먼저 맞춰 보자.

문제 1 — 3분할에서도 두 항이 같을까? (Last Session's Exercise 1 — Does It Hold for Three Groups?)

분할 $P_5=\{S_1,S_3,S_5\}\mid\{S_2,S_4\}\mid\{S_6,S_7,S_8\}$에 대해:

세 항이 23, 12, 95로 전부 다르다. 모둠이 둘일 때는 $D_A+D_B=2m$이 성립해서 두 항이 언제나 같아졌지만, 셋이 되면 $D_A+D_B\neq 2m$이므로 그 증명이 무너진다. 오늘 §10에서 이 $P_5$가 Louvain 알고리즘이 실제로 도중에 만들어 내는 분할이라는 것을 보게 된다.

문제 2 — 아령 그래프에서 다리를 끊으면 (Last Session's Exercise 2 — Cutting the Bridge of a Barbell)

아령 그래프 $H$(삼각형 A와 B를 A1–B1 하나로 이은 6명 7간선):

손실 $\frac12-\frac5{14}=\frac{1}{7}$은 전부 $m_c/m$ 항에서 나왔다 ($\left(D_c/2m\right)^2$ 항은 다리가 있든 없든 $2\times\frac14$로 똑같다). 다리를 놓은 A1이 $Q$에게는 벌점이었다는 뜻이다.

2. 오늘의 질문: 4140개는 세어 봤지만 (Why We Need Algorithms)

단원 3-3에서 우리는 8명짜리 망 $W$의 모든 분할 4140개를 전수 조사해서 $Q$의 최댓값이 $190/576$임을 확인했다. 8명은 그렇게 할 수 있었다. 그러면 34명인 가라테 클럽은?

$2.1\times10^{28}$개는 1초에 10억 개씩 세어도 우주 나이보다 오래 걸린다. “두 모둠으로만 나눈다”고 제한을 걸어도 $2^{33}-1=8{,}589{,}934{,}591$가지다.

그런데 다행인 점이 하나 있다. 학급은 작다. 30명 규모라면 정수계획법으로 진짜 최댓값을 구하는 cluster_optimal()이 실제로 돌아간다 (§14에서 가라테 34명에 대해 실행해 볼 것이다). 즉 교사에게는 “최적을 알고 있는 상태에서 휴리스틱을 채점할 수 있는” 드문 상황이 주어진다.

3. 두 가지 방향 — 자를 것인가, 붙일 것인가 (Divisive vs Agglomerative)

커뮤니티를 찾는 방법은 크게 두 갈래다.

두 방향은 정반대의 실수를 한다. 분리형은 다리를 잘 찾지만 다리가 여러 개면 헤매고, 병합형은 촘촘한 덩어리를 잘 찾지만 한 번 붙인 것을 되돌리지 못한다. 오늘은 같은 망 $W$에 두 방향을 다 손으로 돌려서 그 차이를 눈으로 본다.

4. 간선 매개 중심성 — 손 계산 (Edge Betweenness by Hand)

단원 2-3에서 정점의 매개 중심성을 배웠다. 여기서는 대상이 간선이 된다.

망 $W$(8명, 12간선)로 계산한다. 정점 쌍은 $\binom{8}{2}=28$개. 28쌍을 하나도 빼지 않고 전부 적는다.

간선별로 모아 보기 (Collecting by Edge)

값이 말해 주는 것 (What the Values Tell Us)

• S5–S6 = 15: 이 간선을 끊으면 15쌍이 서로에게 못 간다. 이 망의 유일한 다리다.
• S7–S8 = 1: 삼각형 안쪽이라 “지나갈 일”이 없다. S7과 S8이 서로 갈 때뿐. 가까운 사이일수록 매개가 낮다는 것이 핵심 — 매개가 높은 간선은 친한 사이가 아니라 연결 담당이다.
• 13/3 vs 5/3: 같은 오각형 간선인데 S5에 붙은 것(13/3)이 붙지 않은 것(5/3)보다 2.6배 높다. S5가 바깥으로 나가는 유일한 문이라서, S1~S4가 밖으로 나갈 때 반드시 S5를 거치기 때문이다.

5. Girvan–Newman: 위에서 자르며 내려가기 (The Girvan–Newman Algorithm)

$W$에 그대로 돌려 보자. 동점이면 번호가 작은 간선을 먼저 제거한다.

단계 1에서 이미 끝났다 (The Split Is Already Done at Step 1)

$Q$의 최댓값 $190/576$이 첫 번째 간선을 자르자마자 나왔고, 그 뒤로는 계속 내려가기만 한다. $W$에서 GN은 사실상 “다리를 한 번 짚는 것”만으로 답을 냈다. 이것이 분리형의 장점이다 — 다리가 뚜렷하면 한 방에 찾는다.

6. 병합 이득 $\Delta Q$ 공식 (The Merge-Gain Formula)

이제 반대 방향, 병합형으로 간다. 병합형은 매 단계 “이 둘을 합치면 $Q$가 얼마나 오르나”를 물어야 한다. 단원 3-3의 모둠별 공식에서 바로 유도된다.

$W$는 $m=12,\ 2m=24,\ (2m)^2=576$이므로 전부 576분의 정수로 떨어진다:

$$\Delta Q=\frac{48\,m_{AB}-2\,D_A D_B}{576}$$

이 공식이 모듈러리티 행렬과 같은 것임을 확인하기 (The Formula Is the Modularity Matrix Again)

둘 다 혼자인 두 사람 $i,j$를 합칠 때는 $m_{AB}=A[i,j],\ D_A=d_i,\ D_B=d_j$이므로

$$\Delta Q=\frac{48A[i,j]-2d_id_j}{576}=\frac{2\left(24A[i,j]-d_id_j\right)}{576}=\frac{2\cdot\left(24B\right)[i,j]}{576}$$

단원 3-3의 $24B$ 표에서 대각선 밖 최댓값을 찾아보면:

7. fast greedy: 아래에서 붙이며 올라가기 (Fast Greedy / CNM)

손으로 끝까지 돌린다. 매 단계 후보를 전부 적는다 (같은 값이 여러 개면 하나만 대표로 적고 동점임을 밝힌다).

반복 1 — 전원이 혼자 (Iteration 1 — Everyone a Singleton)

후보는 $\binom82=28$쌍. 위 §6의 표가 그대로 이 단계의 계산이다. 간선이 있는 12쌍은 양수, 없는 16쌍은 전부 음수.

→ {S7,S8} 병합. $Q:\ -78+40=\mathbf{-38}/576$

반복 2 — {S7,S8}이 생겼다 (Iteration 2 — {S7,S8} Is Born)

S6은 {S7,S8}과 두 개의 간선을 갖는다(S6–S7, S6–S8). $m_{AB}=2$가 되면서 이득이 두 배로 뛰었다. → {S6,S7,S8} 병합. $Q:\ -38+72=\mathbf{34}/576$

반복 3~6 — 오각형 쪽이 뭉친다 (Iterations 3–6 — the Pentagon Side Gathers)

반복 7의 $\Delta Q$가 음수이므로 여기서 멈춘다. 최종 답은 $190/576$ — GN과 같은 답, 그리고 단원 3-3에서 전수 조사로 확인한 진짜 최적이다.

8. 두 길이 지나간 자리 (The Two Trajectories)

GN은 8모둠 쪽에서 2모둠 쪽으로 내려왔고, fast greedy는 8모둠에서 올라갔다. 같은 “모둠 수”에서 두 알고리즘이 만든 분할의 $Q$를 나란히 놓아 본다.

(단위: /576)

여덟 지점 중 일곱 곳에서 값이 같고, 5모둠에서만 갈린다:

GN이 오각형을 “S4–S5만 남기고 다 끊은” 모양으로 만든 반면, fast greedy는 “S1–S3만 붙인” 모양을 만들었다. 방향이 반대이니 당연히 다른 중간 상태다. 중간 과정이 다른데 최종 답은 같다 — 구조가 뚜렷한 망에서는 길이 달라도 도착지가 같다. §14에서 구조가 뚜렷하지 않으면 어떻게 되는지 볼 것이다.

9. Louvain ① 국소 이동 (Louvain: Local Moving)

Louvain(Blondel 외, 2008)은 현재 가장 널리 쓰이는 방법이다. 두 단계를 번갈아 반복한다.

정점 $v$를 모둠 $C$에 넣을 때의 이득은 §6 공식에서 $m_{AB}=k_{v,\text{in}}$(= $v$에서 $C$로 가는 간선 수), $D_A=d_v$, $D_B=D_C$로 놓은 것이다:

$$\Delta Q=\frac{48\,k_{v,\text{in}}-2\,d_v D_C}{576}$$

순서를 S1→S8로 두고 손으로 돌린다. 동점이면 번호가 작은 모둠을 택한다.

순회 1 (Sweep 1)

순회 2 (Sweep 2)

순회 3에서는 아무도 움직이지 않는다 → 1단계 종료.

왜 막혔는가 — 순회 2의 동점을 보라 (Why It Stalls — the Tie in Sweep 2)

S2에게 “{S1,S3,S5}로 옮길래?”라고 물으면 이득이 $+30$, 지금 있는 {S4}에 남는 것도 $+30$이다. 혼자 옮겨서는 아무 이득이 없다. S4도 마찬가지다. 그런데 S2와 S4가 함께 옮기면 이야기가 달라진다. 그것이 2단계다.

10. Louvain ② 집계 (Louvain: Aggregation)

1단계 결과의 각 모둠을 정점 하나로 압축한다. 모둠 안의 간선은 그 정점의 자기 고리가 되고, 모둠 사이의 간선은 가중치가 된다.

검산: 내부 $3+1+3=7$, 사이 $4+1+0=5$, 합 12 = $m$ ✓   $D$ 합 $11+6+7=24=2m$ ✓

초정점 3개로 다시 병합 이득 계산 (Merge Gains on the Three Super-Nodes)

A와 B를 합친다 → $Q = 130 + 60 = \mathbf{190}/576$. 최적 도달. 다시 집계해도 더 합칠 것이 없으므로(A∪B와 C를 합치면 $-190$) 여기서 끝난다.

11. Louvain은 왜 돌릴 때마다 다른가 (Why Louvain Is Unstable)

단원 3-3에서 “Louvain은 실행할 때마다 답이 달라진다”고만 하고 넘어갔다. 이제 이유를 정확히 짚을 수 있다.

실제로 순서만 바꿔서 1단계를 200번 돌려 봤다.

• S1→S8 순서(§9에서 손으로 돌린 것)는 $130/576$에서 끝났다.
• S8→S1 순서로 돌리면 1단계에서 바로 $190/576$이 나온다.
• 즉 순서만으로 답이 갈린다. 1단계만 놓고 보면 최적에 닿는 것은 28.5%뿐.

12. walktrap: 걸어서 재는 거리 (Walktrap: Random-Walk Distance)

지금까지의 방법은 전부 $Q$나 매개를 봤다. walktrap(Pons & Latapy, 2005)은 전혀 다른 발상이다.

한 걸음 전이행렬 $P$ (The One-Step Transition Matrix)

$P[i,j]=A[i,j]/d_i$ — $i$에 서 있을 때 다음 걸음에 $j$로 갈 확률. $W$의 차수는 $(3,3,3,3,5,3,2,2)$이므로 각 행을 자기 차수로 나눈다.

두 걸음 — 손으로 $P^2$의 한 행 구하기 (Two Steps — One Row of P² by Hand)

$P^2[1,k]=\sum_j P[1,j]\,P[j,k]$. S1의 이웃은 S3, S4, S5뿐이므로 세 항만 살아남는다.

같은 식으로 S7행도 구해 둔다(S7의 이웃은 S6, S8):

($P^2[7,7]$: S7→S6→S7 $=\frac12\cdot\frac13=\frac16$ 와 S7→S8→S7 $=\frac12\cdot\frac12=\frac14$의 합 $=\frac{2}{12}+\frac{3}{12}=\frac{5}{12}$.)

walktrap의 거리 (The Walktrap Distance)

손으로 $r(S_7,S_8)$을 구해 본다. 위 표에서 두 행은 S7·S8 칸에서만 다르다.

$$r(S_7,S_8)=\sqrt{\tfrac{1}{16}}=\tfrac14=0.25$$

거리를 다 재고 나면 (After Every Distance Is Measured)

walktrap은 이 거리로 가까운 모둠부터 병합(Ward 방식)한 뒤, 그 과정에서 $Q$가 가장 높은 지점을 고른다. $W$에서는 $t=2,3,4,5$ 어느 걸음 수로 해도 답이 $190/576$으로 같았다.

13. R로 검증 (Verification in R)

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")

## (1) 간선 매개 — §4
edge_betweenness(gW)
#  S1-S3  S1-S4  S1-S5  S2-S3  S2-S4  S2-S5  S3-S5  S4-S5  S5-S6 S6-S7 S6-S8 S7-S8
#  1.667  1.667  4.333  1.667  1.667  4.333  4.333  4.333 15.000 6.000 6.000 1.000
sum(edge_betweenness(gW)); sum(distances(gW))/2   # 검산
# [1] 52
# [1] 52

## (2) 병합 이득 공식 — §6
dQ <- function(A,B,g=gW){ d <- degree(g)
  (48*sum(W[A,B]) - 2*sum(d[A])*sum(d[B])) / 576 }
dQ(7,8)*576   # [1] 40   <- 첫 병합
dQ(6,c(7,8))*576  # [1] 72

## (3) 알고리즘 8개 — W에서는 전원 일치
show <- function(cl) c(Q576=round(modularity(gW,membership(cl))*576),
                       k=length(unique(membership(cl))))
sapply(list(GN=cluster_edge_betweenness(gW), FG=cluster_fast_greedy(gW),
            LV=cluster_louvain(gW),          WT=cluster_walktrap(gW),
            LE=cluster_leading_eigen(gW),    LP=cluster_label_prop(gW),
            IM=cluster_infomap(gW),          OPT=cluster_optimal(gW)), show)
#       GN  FG  LV  WT  LE  LP  IM OPT
# Q576 190 190 190 190 190 190 190 190
# k      2   2   2   2   2   2   2   2

## (4) walktrap 거리 — §12
P <- W / degree(gW);  P2 <- P %*% P
sqrt(sum((P2[7,]-P2[8,])^2 / degree(gW)))   # [1] 0.25
sqrt(sum((P2[1,]-P2[2,])^2 / degree(gW)))   # [1] 0        <- S1과 S2는 완전히 같은 자리

14. 가라테: 정답이 있는 시험 (Karate: A Test with a Known Answer)

가라테 클럽은 실제로 어떻게 갈라졌는지가 기록된 드문 자료다. Mr. Hi 편 16명 / John A. 편 18명. 알고리즘들에게 채점표를 줄 수 있다.

읽을 것 다섯 가지 (Five Things to Read Off)

1. Louvain(seed 4)이 정수계획법의 진짜 최댓값과 완전히 같은 분할을 찾았다. 명단까지 한 사람도 안 틀렸다. 다만 100번 중 30번만 그랬다(§11).
2. fast greedy는 $0.3807$에 갇혔다. 최적보다 0.039 낮다. §7에서 예고한 “되돌리지 못하는 탐욕”이 34명 규모에서 실제로 손해를 냈다.
3. GN은 1명짜리 모둠을 만들었다 — 10번 학생. 매개가 높은 간선을 계속 끊다 보면 다리 역할만 하는 학생이 홀로 남는다. 분리형의 전형적인 부작용이다.
4. walktrap이 $Q$ 기준으로는 꼴찌(0.3532)다. $Q$를 목적함수로 쓰지 않으니 당연하다 — walktrap은 “걸음이 갇히는가”를 보지 “$Q$가 오르는가”를 보지 않는다.
5. 세 방법(optimal, Louvain, leading eigen)은 파벌 경계를 한 명도 넘지 않았다. 이들은 정답을 어긴 것이 아니라 더 잘게 쪼갠 것이다.

갈린 학생 세 명 (The Three Students Who Get Split)

3번과 10번은 친구가 정확히 반반이다. 어느 알고리즘도 이들을 자신 있게 배치할 수 없는 것이 당연하다. 알고리즘이 갈리는 지점 = 실제로 경계에 서 있는 사람이다.

15. $Q$가 높다고 진실에 가까운 것은 아니다 (Higher Q Is Not Closer to the Truth)

위 표를 $Q$ 순서로 다시 보면 이상한 일이 벌어진다.

왜 그런가 — 세 가지를 구분하자 (Why — Three Things to Keep Apart)

$Q$ 최대화는 첫 번째 물음에만 답한다. 그리고 중요한 것은, optimal이 낸 4모둠이 실제 파벌을 어긴 것이 아니라 세분한 것이라는 점이다:

C1∪C2 = Mr. Hi 파벌 전체, C3∪C4 = John A. 파벌 전체다. 알고리즘은 틀린 것이 아니라 더 자세히 본 것이다. 단원 3-3에서 확인한 C2 = {5,6,7,11,17}(바깥 이웃이 1번 한 사람뿐인 다섯 명)이 여기서 다시 나온다.

16. 해상도 한계 (The Resolution Limit)

$Q$에는 더 근본적인 한계가 있다. 작은 모둠은 아예 보이지 않는다. 손으로 증명할 수 있는 깔끔한 예가 있다.

삼각형 $n$개를 고리로 이은 그래프 (A Ring of n Triangles)

삼각형 $n$개를 만들고, 각 삼각형에서 하나씩 뽑아 다음 삼각형과 간선 하나로 잇는다. 누가 봐도 모둠은 $n$개다.

삼각형 각각을 모둠으로 둘 때:

$$Q_{\text{정답}}=n\left[\frac{3}{4n}-\left(\frac{8}{8n}\right)^2\right]=\frac34-\frac{1}{n}$$

이웃한 두 삼각형을 한 모둠으로 묶으면 $m_c=3+3+1=7,\ D_c=8+8=16$이 되므로

$$\Delta Q=\underbrace{\left[\frac{7}{4n}-\left(\frac{16}{8n}\right)^2\right]}_{\text{합친 모둠}} -2\underbrace{\left[\frac{3}{4n}-\frac{1}{n^2}\right]}_{\text{원래 두 모둠}} =\frac{7}{4n}-\frac{4}{n^2}-\frac{6}{4n}+\frac{2}{n^2} =\boxed{\;\frac{1}{4n}-\frac{2}{n^2}\;}$$

$\sqrt{2m}$ 기준 (The Rule of Thumb)

Fortunato & Barthélemy(2007)의 경험칙: $D_c\lesssim\sqrt{2m}$인 모둠은 $Q$가 잘 못 본다. 우리 예에서 확인해 보자. $2m=8n$이고 $D_c=8$이므로

$$D_c=\sqrt{2m}\;\Longleftrightarrow\;8=\sqrt{8n}\;\Longleftrightarrow\;64=8n\;\Longleftrightarrow\;n=8$$

손으로 구한 경계 $n=8$과 정확히 일치한다.

알고리즘을 바꿔도 소용없다 (Changing the Algorithm Does Not Help)

17. 어떤 알고리즘을 쓸 것인가 (Choosing an Algorithm)

실무 지침 다섯 가지 (Five Practical Guidelines)

18. 연습문제 (Exercises)

19. 해설과 답 (Solutions)

문제 1 해설 — 아령 그래프의 간선 매개 (Solution 1 — Edge Betweenness on the Barbell)

(1) 15개 쌍을 전부 전개한다. $H$에서 A쪽 3명과 B쪽 3명은 반드시 A1–B1을 지난다.

갈림길이 하나도 없다(모든 $\sigma=1$) — 아령에는 우회로가 없으므로 분수가 안 나온다. 간선별로 모으면:

(2) 검산. 간선 매개 총합 $=9+4+4+4+4+1+1=\mathbf{27}$.

(3) 첫 제거. 최댓값은 A1–B1의 9. 끊는 순간 두 삼각형으로 갈라진다.

두 항이 35로 같은 것은 단원 3-3에서 증명한 두 모둠 항등식 그대로다 ($D_A=D_B=7$, $m_A=m_B=3$).

(4) 두 번째 제거. A1–B1이 사라진 뒤 매개를 다시 계산하면 남은 것은 삼각형 두 개뿐이고, 삼각형 안에서는 모든 간선의 매개가 1로 똑같다 (각 간선은 자기 양 끝 쌍에만 쓰인다). 그러므로 어느 하나가 임의로 제거된다. 그러면 삼각형 하나가 경로 3개짜리로 바뀌지만 덩어리 수는 그대로 2개이므로 $Q$는 원본망 기준으로 여전히 $5/14$다. 세 번째 제거에서 비로소 한 명이 떨어져 나가고 $Q$가 내려간다.

문제 2 해설 — 아령 그래프의 fast greedy (Solution 2 — Fast Greedy on the Barbell)

(1) 15쌍 전부. $\Delta Q=\dfrac{28\,m_{AB}-2D_AD_B}{196}$, 차수는 A1=3, A2=2, A3=2, B1=3, B2=2, B3=2.

쌍의 수 검산: 간선 있는 7쌍 + 없는 8쌍 = 15 = $\binom62$ ✓

(2) 첫 병합은 A2–A3 (또는 B2–B3), $+20/196$. 다리 A1–B1은 $+10/196$으로 꼴찌다. 같은 “간선 1개”인데도 값이 갈리는 이유는 공식의 $2d_id_j$ 때문이다. 차수가 3·3인 A1–B1은 영 모형에서도 $\frac{3\cdot3}{14}=0.64$개쯤 기대되는 반면, 차수 2·2인 A2–A3는 $\frac{2\cdot2}{14}=0.29$개만 기대된다. 있으리라 기대되지 않았는데 있는 간선일수록 증거가 세다.

(3) 끝까지. 시작값은 $Q=-\sum\left(\frac{d_i}{2m}\right)^2=-\frac{9+4+4+9+4+4}{196}=-\frac{34}{196}$.

반복 2에서 $m_{AB}=2$인 이유: A1은 A2와 A3 둘 다와 이어져 있다. 반복 5의 $\Delta Q$가 음수이므로 멈춘다.

검산: $-34+20+32+20+32=\mathbf{70}$ ✓   그리고 $70-70=0$ — 전원 한 모둠이면 $Q=0$ ✓

(4) 두 알고리즘의 다리 처리.