클리크 — 극대와 최대

1. 오늘의 질문 — 중심에서 집단으로 (Today's Question)

2단계 여섯 단원 동안 우리가 던진 질문은 하나였다 — "누가 중심인가?" 연결정도·근접·매개·고유벡터·페이지랭크는 모두 정점 하나에 숫자 하나를 붙이는 지표였다. 34명 학급이면 34개의 숫자가 나오고, 그걸 크기순으로 줄 세우는 것이 분석의 끝이었다.

그런데 담임 교사가 실제로 알고 싶은 것은 그것만이 아니다.

가장 엄격하고 가장 오래된 답이 클리크(clique)다. 1949년 루스와 페리(Luce & Perry)가 제안했고, 정의가 단 한 줄이다 — "서로 전부 연결된 사람들의 모임." 오늘은 이 한 줄을 손으로 끝까지 밀어붙인다.

오늘 쓸 네트워크 (Today's Networks)

1·2단계 내내 쓴 7명 무방향 네트워크 $U$로 손 계산을 하고, 그다음 Zachary 가라테 클럽(34명)으로 실전 확인을 한다. 가라테 클럽은 SNA에서 가장 유명한 자료다 — 1970년대 미국의 한 가라테 동아리가 사범(node 1, Mr. Hi)과 관장(node 34, John A)의 갈등으로 실제로 두 쪽으로 쪼개진 기록이 남아 있기 때문이다. "네트워크 구조만 보고 분열을 맞힐 수 있는가"를 시험할 수 있는 드문 자료다.

$U$의 인접행렬을 다시 적어 둔다(대칭, 간선 8개).

2. 정의 — 완전 부분그래프 (Definition: Complete Subgraph)

정점 집합 $S \subseteq V$가 클리크라는 것은:

$$S \text{ is a clique} \iff A[i,j] = 1 \quad \text{for all } i,j \in S,\; i \neq j$$

즉 $S$ 안의 모든 순서 없는 쌍이 간선으로 이어져 있어야 한다. $|S| = k$이면 확인해야 할 쌍의 개수는

$$\binom{k}{2} = \frac{k(k-1)}{2}$$

이고, 이 $\binom{k}{2}$개가 전부 1이어야 한다. 하나라도 0이면 클리크가 아니다.

클리크가 되는 조건을 합으로 쓰면 (The Condition as a Sum)

부분행렬의 원소를 전부 더하면 검사가 한 줄이 된다. 무방향이므로 각 간선이 두 번 세어진다:

$$S \text{ is a clique} \iff \sum_{i \in S}\sum_{j \in S} A[i,j] \;=\; k(k-1)$$

또는 순서 없는 쌍으로만 세면 $\binom{k}{2}$와 같아야 한다. 아래에서는 쌍 단위로 세겠다 — 손으로 하기엔 그쪽이 훨씬 편하다.

3. 손 계산 ① — 35개 삼중항 전부 (Hand Calculation ①: All 35 Triples)

가장 작은 "흥미로운" 클리크는 삼각형이다. $U$의 7명에서 3명을 뽑는 방법은

$$\binom{7}{3} = \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} = \frac{210}{6} = 35$$

가지. 35개를 전부 검사한다. 각 삼중항 $\{i,j,k\}$마다 세 항

$$A[i,j] + A[i,k] + A[j,k]$$

을 더하고, 합이 3이면 삼각형이다. 0인 항도 하나도 빼지 않고 적는다.

합을 도수분포로 정리하면:

4. 검산 — $U^3$의 대각합 (Cross-check with the Trace)

단원 1-3에서 $(A^3)[i,i]$가 $i$에서 출발해 3걸음 만에 자기에게 돌아오는 걷기의 수라는 걸 배웠다. 무방향 그래프에서 길이 3의 닫힌 걷기는 삼각형을 도는 것밖에 없으므로:

$$(\text{삼각형의 수}) = \frac{1}{6}\operatorname{tr}(A^3) = \frac{1}{6}\sum_{i=1}^{n} (A^3)[i,i]$$

왜 6으로 나누는가? 삼각형 하나가 $(A^3)$ 대각에 여섯 번 기록되기 때문이다 — 출발점 3가지 × 도는 방향 2가지 = 6.

$$\frac{\operatorname{tr}(U^3)}{6} = \frac{12}{6} = 2 \quad \checkmark$$

§3에서 손으로 센 2개와 정확히 일치한다. S4만 대각 원소가 0이라는 것도 §3의 관찰과 맞물린다 — S4는 어떤 삼각형에도 속하지 않는다.

5. 손 계산 ② — 4명짜리 클리크는 없다 (Hand Calculation ②: No 4-Clique)

삼각형이 2개 있으니 다음 질문은 자연스럽다 — 4명이 서로 전부 친한 조는 있는가? 후보는 $\binom{7}{4} = 35$가지이고, 각 후보마다 $\binom{4}{2} = 6$개 쌍을 검사해야 한다. 35개 후보의 간선 수 분포부터 보자.

완전한 4인 조는 0개다. 가장 근접한 두 후보(간선 4개, 완전까지 2개 부족)를 6개 쌍 전부 전개해서 확인한다.

후보 A — {S1,S2,S3,S4} (Left Group Plus the Bridge)

$$1 + 1 + 0 + 1 + 0 + 1 = 4 \;\neq\; 6 \quad \Rightarrow \quad \text{클리크 아님}$$

빠진 쌍은 S1–S4와 S2–S4. S4는 S3하고만 친하다.

후보 B — {S4,S5,S6,S7} (Right Group Plus the Bridge)

$$1 + 0 + 0 + 1 + 1 + 1 = 4 \;\neq\; 6 \quad \Rightarrow \quad \text{클리크 아님}$$

35개를 다 세지 않고 끝내는 논증 (A One-Line Proof)

이 논증에는 보너스가 있다 — 같은 이유로 5-클리크, 6-클리크도 없다. 5-클리크는 삼각형 $\binom{5}{3} = 10$개를 품어야 하니 더더욱 불가능하다. 그래서 $U$에서 만들 수 있는 가장 큰 클리크의 크기는 3이다.

6. 극대와 최대는 다르다 (Maximal vs Maximum)

여기가 이 단원에서 가장 많이 헷갈리는 지점이다. 두 단어가 한국어로도 비슷하고 영어로도 비슷하다.

왜 이 구분이 중요한가 (Why the Distinction Matters)

클리크를 전부 나열하면 쓸모없이 많아진다. $U$의 클리크를 크기별로 세면(정점 하나짜리 포함):

17개를 다 보고할 수는 없다. 그리고 대부분은 다른 클리크에 통째로 먹힌다 — {S1,S2}는 {S1,S2,S3} 안에 이미 들어 있으니 따로 보고할 이유가 없다. 극대만 남기면 그런 중복이 전부 사라진다. $U$는 17개 → 4개로 줄어든다.

7. 손 계산 ③ — {S3,S4}가 극대인 이유 (Hand Calculation ③: Why {S3,S4} Is Maximal)

"크기 2짜리 극대 클리크"라는 말이 처음에는 이상하게 들린다. 간선 하나가 어떻게 "더 이상 키울 수 없는 집단"인가? 정의대로 바깥 정점 5명 전부를 하나씩 넣어 보면 답이 나온다.

$\{S3,S4\}$에 정점 $v$를 추가하려면 두 조건이 동시에 만족돼야 한다: $A[v,S3] = 1$ 그리고 $A[v,S4] = 1$.

대조 — {S1,S2}는 왜 극대가 아닌가 (Contrast: Why {S1,S2} Is Not Maximal)

단 하나(S3)만 통과해도 극대가 아니다. $\{S1,S2\}$는 $\{S1,S2,S3\}$에 흡수된다.

8. U의 극대 클리크 네 개 (The Four Maximal Cliques of U)

최대 클리크의 크기(클리크 수, clique number)는

$$\omega(U) = 3$$

이고, 그 크기를 달성하는 최대 클리크는 {S1,S2,S3}과 {S5,S6,S7} 두 개다.

9. 클리크 공동소속 행렬 (Clique Co-membership Matrix)

극대 클리크 목록만으로는 "누구와 누구가 자주 같이 묶이는가"가 한눈에 안 들어온다. 그래서 공동소속 행렬 $K$를 만든다:

$$K[i,j] = (\text{정점 } i \text{와 } j \text{를 동시에 포함하는 극대 클리크의 수})$$

손으로는 극대 클리크 4개를 하나씩 훑으며 그 안의 모든 쌍(자기 자신 포함)에 1씩 더하면 된다.

다 더하면:

보라색 대각선이 이 행렬의 핵심이다:

$$K[i,i] = (\text{정점 } i \text{가 속한 극대 클리크의 수})$$

10. R 검증 (R Verification)

library(igraph)

## 7명 네트워크 U
nm <- paste0("S", 1:7)
U  <- matrix(0, 7, 7, dimnames = list(nm, nm))
el <- rbind(c(1,2), c(1,3), c(2,3), c(3,4), c(4,5), c(5,6), c(5,7), c(6,7))
for (i in 1:nrow(el)) { U[el[i,1], el[i,2]] <- 1; U[el[i,2], el[i,1]] <- 1 }
g <- graph_from_adjacency_matrix(U, mode = "undirected")

## ── 삼각형 (§3, §4) ──────────────────────────────
sum(count_triangles(g)) / 3        # 2
sum(diag(U %*% U %*% U)) / 6       # 2   ← 대각합 검산
count_triangles(g)                 # 1 1 1 0 1 1 1   ← S4만 0

## ── 극대 클리크 (§8) ─────────────────────────────
max_cliques(g)                     # 4개: {S4,S5} {S3,S4} {S1,S2,S3} {S5,S6,S7}
length(max_cliques(g))             # 4

## ── 최대 클리크 (§6) ─────────────────────────────
clique_num(g)                      # 3   ← ω(U)
largest_cliques(g)                 # 2개: {S1,S2,S3} {S5,S6,S7}

## ── 모든 클리크의 크기 분포 (§6) ─────────────────
table(sapply(cliques(g, min = 1), length))
#  1  2  3
#  7  8  2      ← 정점 7, 간선 8, 삼각형 2

## ── 공동소속 행렬 K (§9) ─────────────────────────
K <- matrix(0, 7, 7, dimnames = list(nm, nm))
for (k in max_cliques(g)) {
  v <- as.integer(k)
  for (a in v) for (b in v) K[a, b] <- K[a, b] + 1
}
diag(K)                            # 1 1 2 2 2 1 1

11. 실전 준비 — 2010년 교재 파일의 오류 (A Data Error in the 2010 File)

이제 34명짜리 실제 자료로 넘어간다. 그런데 R_SNA_2010/karate_net.txt를 읽자마자 숫자가 표준값과 다르다. 확인 절차를 남겨 둔다 — 남의 자료 파일은 항상 먼저 의심하는 것이 SNA의 기본기다.

kel <- as.matrix(read.table("karate_net.txt"))
nrow(kel)                          # 78   ← 줄 수는 맞다

g <- simplify(graph_from_edgelist(kel, directed = FALSE))
ecount(g)                          # 77   ← 하나가 사라졌다!

## 중복된 무방향 쌍 찾기 — 각 줄을 정렬한 뒤 중복 검사
k2 <- t(apply(kel, 1, sort))
k2[duplicated(k2), , drop = FALSE]
#      V1 V2
# [1,]  9 33      ← 9-33이 두 번 적혀 있다

## 표준 Zachary 차수와 대조
known <- 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)
which(degree(g) != known)          # 9 31
degree(g)[c(9, 31)]                # 4 3   (표준값은 5 4)

## → 9-31 간선이 누락되고 그 자리에 9-33이 중복 기재된 것
gk <- add_edges(g, c(9, 31))
ecount(gk)                         # 78
all(degree(gk) == known)           # TRUE  ← 34개 차수가 전부 일치

수정 후의 기본 지표(이제부터 나오는 모든 수치는 수정본 기준이다):

12. 가라테 클럽의 극대 클리크 36개 (36 Maximal Cliques of the Karate Club)

mck <- max_cliques(gk)
length(mck)                              # 36
table(sapply(mck, length))
#  2  3  4  5
# 11 21  2  2
clique_num(gk)                           # 5
largest_cliques(gk)                      # {1,2,3,4,8} {1,2,3,4,14}

table(sapply(cliques(gk, min = 1), length))
#  1  2  3  4  5
# 34 78 45 11  2

크기 4 이상의 극대 클리크 4개만 뽑으면:

13. 두 개의 5-클리크와 빠진 한 쌍 (Two 5-Cliques and One Missing Pair)

최대 클리크 두 개를 나란히 놓으면 이상하리만치 닮았다.

$$A = \{1,2,3,4,\mathbf{8}\}, \qquad B = \{1,2,3,4,\mathbf{14}\}$$

$$A \cap B = \{1,2,3,4\} \quad (\text{크기 } 4), \qquad A \cup B = \{1,2,3,4,8,14\} \quad (\text{크기 } 6)$$

다섯 명 중 네 명이 같다. 그렇다면 합집합 6명이 6-클리크가 되지 않을까? $\binom{6}{2} = 15$개 쌍을 전부 검사한다.

$$\underbrace{1+1+1+1+1+1+1+1+1+1+1+1+1+1}_{14 \text{개}} + \underbrace{0}_{8\text{–}14} = 14 \;\neq\; 15$$

8번과 14번은 누구와 친한가 (The Neighbourhoods of 8 and 14)

둘 다 {1,2,3,4} 전원과 친한데 서로는 모른다. 그래서 {1,2,3,4}에 8을 붙이거나 14를 붙일 수는 있어도 둘 다는 못 붙인다.

그렇다면 $\{1,2,3,4\}$는 어떤 지위인가? 6개 쌍이 전부 1이므로 클리크는 맞다. 하지만 8번과 14번이 각각 추가 가능하므로 극대는 아니다. 그래서 max_cliques()의 36개 목록에 {1,2,3,4}는 나타나지 않는다.

Am <- as.matrix(as_adjacency_matrix(gk))
sum(Am[c(1,2,3,4), c(1,2,3,4)]) / 2            # 6  = C(4,2) → 클리크 맞음
which(Am[1,]==1 & Am[2,]==1 & Am[3,]==1 & Am[4,]==1)
# 8 14   ← 넷 모두와 친한 바깥 정점이 둘 → 극대 아님
Am[8, 14]                                       # 0

14. 클리크는 분할이 아니다 (Cliques Are Not a Partition)

"우리 반을 몇 개 무리로 나누라"는 요구에 클리크는 답하지 못한다. 극대 클리크는 서로 겹치기 때문이다. 각 정점이 몇 개의 극대 클리크에 속하는지 34명 전부 세어 보자.

반대쪽 끝도 보자. 극대 클리크에 딱 한 번만 등장하는 정점이 12명이다:

8 12 13 15 16 17 18 19 21 22 23 27

15. 클리크와 실제 분열 (Cliques vs the Real Split)

가라테 클럽은 실제로 두 진영으로 쪼개졌다. 기록된 소속은 다음과 같다.

이제 질문 — 클리크만 보고 이 분열을 맞힐 수 있었을까? 극대 클리크 36개 중 두 진영에 걸친 것이 몇 개인지 세어 보자.

간선 수준에서도 같은 그림이다. 78개 간선 중 진영을 가로지르는 것은 10개뿐이다.

1–9 1–32 2–31 3–9 3–10 3–28 3–29 3–33 14–34 20–34

$$\frac{10}{78} = 0.1282 \quad \Rightarrow \quad \text{간선의 } 87.2\%\text{가 같은 진영 안에 있었다}$$

10개 중 5개(3–9, 3–10, 3–28, 3–29, 3–33)가 3번 한 사람에게서 나온다. 3번은 사범 진영이면서 관장 진영에 다리를 다섯 개나 걸치고 있었던 인물이다.

두 지도자는 서로 아는 사이였을까 (Were the Two Leaders Connected?)

any(sapply(mck, function(k) all(c(1, 34) %in% as.integer(k))))
# FALSE   ← 1번과 34번이 함께 든 극대 클리크가 하나도 없다
are_adjacent(gk, 1, 34)
# FALSE   ← 애초에 서로 간선조차 없다

16. 연결정도가 크다고 뭉친 것은 아니다 (Degree Is Not Cohesion)

34번은 차수 17로 1위, 1번은 16으로 2위다. 그런데 이웃들끼리는 얼마나 친할까? "정점 $v$의 이웃 집합이 클리크에 얼마나 가까운가"를 재면 된다.

$$C(v) = \frac{(\text{이웃들 사이의 실제 간선 수})}{\binom{\deg(v)}{2}}$$

분모는 이웃들이 완전그래프였다면 있었을 간선 수다. $C(v) = 1$이면 $v$와 그 이웃 전체가 하나의 클리크를 이룬다.

$$C(1) = \frac{18}{120} = 0.15, \qquad C(34) = \frac{15}{136} = 0.110294\ldots$$

17. 클리크의 한계 (Limitations)

오늘 배운 도구는 정의가 아름답지만 실제로 쓰기엔 세 가지 문제가 있다.

18. 교실 적용 (Classroom Application)

교우관계 설문(“같이 모둠 하고 싶은 친구를 적어 주세요”)을 무방향으로 정리했다고 하자. 클리크 분석에서 실제로 건질 수 있는 것은 다음 네 가지다.

19. 연습문제 (Exercises)

20. 연습문제 해설과 답 (Solutions)

20-1. 연습문제 1 해설 — S2–S4를 추가하면 (Solution 1)

① 무엇이 바뀌는가 — 인접행렬

바꾸는 칸은 딱 두 개다: $A[2,4]$와 $A[4,2]$를 0에서 1로.

간선 수는 8 → 9가 된다.

② 합이 2였던 다섯 삼중항의 재계산 — 전부 전개

합이 3이던 두 개는 그대로 삼각형이고, 합이 0·1이던 것들은 한 칸 늘어도 3이 될 수 없다. 따라서 합이 2였던 다섯 개만 다시 계산하면 된다.

③ $\{S3,S4\}$의 극대성 재검사 — 바깥 5명 전부

④ 극대 클리크 목록 재작성

⑤ 값의 의미

20-2. 연습문제 2 해설 — 간선 하나로 4-클리크를 만들 수 있는가 (Solution 2)

① 무엇을 세는가

4-클리크는 4명 안의 모든 쌍이 연결돼야 하므로 필요한 간선 수는

$$\binom{4}{2} = \frac{4 \cdot 3}{2} = 6$$

간선을 하나만 더해서 6이 되려면 지금 5개가 있어야 한다.

② §5의 분포표를 다시 읽는다 — 0인 칸도 전부 표기

③ 가장 좋은 두 후보의 6개 쌍 전개

④ 값의 의미 — 왜 하필 두 후보 다 S4가 문제인가

20-3. 연습문제 3 해설 — 3번은 왜 특별한가 (Solution 3)

① 3번이 속한 극대 클리크를 전부 나열

② 교차 간선 10개를 3번 기준으로 분해

$$0+0+0+1+1+1+1+1+0+0 = 5, \qquad \frac{5}{10} = 0.5$$

③ 3번의 이중 지위 정리