완화된 클리크 — n-클리크, k-플렉스, k-코어

1. 오늘의 질문 — 클리크는 왜 너무 엄격한가 (Today's Question: Why Cliques Are Too Strict)

지난 단원(3-1)에서 7명 네트워크 $U$의 극대 클리크를 전부 찾았다. 네 개가 나왔는데, 그중 두 개가 크기 2였다 — {S3,S4}와 {S4,S5}. "세 명이 서로 다 친한 모둠"은 딱 두 개뿐이었다.

가라테 클럽에서는 더 답답했다. 극대 클리크가 36개나 나왔고 최대 크기는 5였는데, 그 크기 5짜리 두 개가 이랬다:

$$\{1,2,3,4,\mathbf{8}\} \qquad\text{그리고}\qquad \{1,2,3,4,\mathbf{14}\}$$

네 명(1,2,3,4)이 똑같고 마지막 한 명만 다르다. 누가 봐도 {1,2,3,4,8,14} 여섯 명이 한 무리인데, 클리크는 이것을 두 개의 다른 집단으로 쪼개서 보고한다. 이유는 단 하나 — 8번과 14번 사이에 간선이 없기 때문이다.

완화의 세 방향 (Three Directions of Relaxation)

클리크의 조건 "집단 안 모든 쌍 $i,j$에 대해 $A[i,j]=1$"을 서로 다른 세 방식으로 늦출 수 있다.

②와 ③은 언뜻 같은 말처럼 들리지만 정반대 방향이다. ②는 "빠진 수"를 세고 ③은 "있는 수"를 센다. 집단이 커질수록 ②는 점점 엄격해지고(전체가 늘어도 허용 결석은 그대로), ③은 점점 느슨해진다(요구 친구 수는 그대로인데 후보가 늘어난다). 오늘 이 차이를 손으로 확인한다.

2. 오늘의 네트워크 $W$ (Today's Network)

지난 시간의 $U$는 너무 성글어서 세 완화가 서로 구별되지 않는다 ($U$에서는 2-플렉스의 최대 크기가 3으로 클리크와 똑같고, 2-코어는 7명 전원이다). 오늘은 8명짜리 $W$를 쓴다. 간선 12개, 무방향.

S1–S3, S1–S4, S1–S5, S2–S3, S2–S4, S2–S5, S3–S5, S4–S5,
S5–S6, S6–S7, S6–S8, S7–S8

인접행렬 $W$ (The Adjacency Matrix)

대각선은 전부 0(자기 자신은 세지 않는다), 행렬은 대칭이다(무방향). 차수의 합 24 = 간선 수 12의 두 배 — 단원 1-4의 악수 정리 검산이 맞는다. 밀도는

$$\Delta = \frac{2m}{n(n-1)} = \frac{2\times 12}{8\times 7} = \frac{24}{56} = 0.4286$$

3. 클리크로 먼저 보기 — 다섯 명이 네 조각으로 (Cliques First: Five People Shattered into Four)

지난 단원의 방법으로 $W$를 분석해 보자. 먼저 {S1,S2,S3,S4,S5}가 클리크인가? 10개 쌍을 전부 확인한다.

10쌍 중 8쌍이 있는데 클리크가 아니다. 빠진 두 쌍이 만드는 피해를 정확히 세어 보자. $\{S1,\dots,S5\}$에서 뽑을 수 있는 삼중항은 $\binom{5}{3}=10$개다.

여기에 오른쪽의 {S6,S7,S8}까지 더하면 $W$의 삼각형은 모두 5개다. 4명짜리 클리크는 하나도 없다. 이유는 두 가지로 나뉜다 — 왼쪽에서 4명을 고르면 $\binom{4}{2}=6$쌍 안에 S1–S2 아니면 S3–S4가 반드시 들어가고, 오른쪽 {S6,S7,S8}에 누구를 더하려 해도 S6과 이어진 사람은 S5뿐인데 S5–S7이 없다. 따라서 $\omega(W)=3$이고, $W$의 극대 클리크는 6개다:

4. 완화 ① 거리를 늦춘다 — n-클리크 (Relaxation ①: Loosen the Distance — n-clique)

정의 (Definition)

손 계산 ① — 측지거리를 $W^k$로 구한다 (Distances from Powers of W)

단원 1-6의 방법을 쓴다: $d(i,j)$는 $W^k[i,j] > 0$이 되는 가장 작은 $k$다. 두 개만 손으로 해 보자.

(가) $d(\text{S1},\text{S2})$ — 먼저 $k=1$: $W[1,2]=0$이므로 거리 1이 아니다. $k=2$로 간다.

$$(W^2)[1,2] = \sum_{k=1}^{8} W[1,k]\cdot W[k,2]$$

$(W^2)[1,2] = 0+0+1+1+1+0+0+0 = 3 > 0$이므로 $d(\text{S1},\text{S2})=2$다. 초록 세 칸이 각각 지름길 하나에 대응한다: S1→S3→S2 S1→S4→S2 S1→S5→S2. 서로 안 친한 S1과 S2 사이에 공통의 친구가 셋이나 있다.

(나) $d(\text{S1},\text{S7})$ — $W[1,7]=0$이니 1은 아니다. $k=2$를 보자.

여덟 항이 전부 0이다. S1의 친구(S3, S4, S5)와 S7의 친구(S6, S8)가 한 명도 겹치지 않는다. 그래서 $k=3$으로 간다. 이번에는 $W^2$의 1행을 먼저 구해 두자. $W$의 1행이 $(0,0,1,1,1,0,0,0)$이므로 $(W^2)[1,\cdot] = W[3,\cdot]+W[4,\cdot]+W[5,\cdot]$다:

이제 $(W^3)[1,7] = \sum_k (W^2)[1,k]\cdot W[k,7]$:

$(W^3)[1,7]=1 > 0$ → $d(\text{S1},\text{S7})=3$. 유일한 초록 칸 $k=6$이 그 경로를 알려 준다: $(W^2)[1,6]=1$은 S1→S5→S6 하나뿐이고, 거기에 S6→S7을 붙이면 S1→S5→S6→S7이다.

$W$의 측지거리 행렬 (The Distance Matrix)

같은 방법을 모든 쌍에 적용하면 (R 검증은 §12):

지름은 3(빨간 칸), 평균 거리는 1.8571이다.

계산 요령 — 거리 행렬을 이진화하면 클리크 문제로 바뀐다 (Binarize and Reuse the Clique Algorithm)

$n=2$로 이진화하면 (거리 1과 2를 1로, 3을 0으로):

$B$의 간선 수는 $40/2 = 20$개, 밀도 $20/28 = 0.7143$. 원래 0.4286에서 크게 올랐다. 이제 $B$에서 클리크를 찾는다.

왼쪽 위 6×6 블록(S1~S6)이 대각선만 빼고 전부 1이다(초록). 즉 {S1,S2,S3,S4,S5,S6}은 $B$의 클리크 = $W$의 2-클리크다. 15개 쌍을 원래 거리로 다시 확인해 보자.

15쌍 모두 2 이하 — 2-클리크가 맞다. 극대인가? S7을 넣으면 $d(\text{S1},\text{S7})=3 > 2$라서 실패, S8도 마찬가지다. 극대다.

$B$에서 오른쪽 아래를 보면 {S5,S6,S7,S8}도 서로 전부 1이다. $d(\text{S5},\text{S7}) = d(\text{S5},\text{S8}) = 2$, 나머지는 1. 여기에 S1을 넣으면 $d(\text{S1},\text{S7})=3$이라 실패. 이것도 극대 2-클리크다.

5. n-클리크의 함정 — 간선이 하나도 없는 2-클리크 (The n-clique Trap)

그런데 §4의 정의에 있던 아래첨자 $G$가 문제를 일으킨다. 가장 작고 기억하기 좋은 반례는 6-사이클 $C_6$다. 여섯 명이 손을 잡고 둥글게 원을 만든 모양 — 간선은 C1–C2, C2–C3, C3–C4, C4–C5, C5–C6, C6–C1 여섯 개뿐이다.

$C_6$의 거리 행렬:

{C1, C3, C5}의 세 쌍을 확인한다.

세 쌍 모두 거리 2 이하 → {C1,C3,C5}는 2-클리크다. 그런데 이 세 명만 남기고 나머지를 지운 유도 부분그래프를 보면:

같은 문제가 오늘의 $W$에서도 약하게 나타난다. 2-클리크 {S1,…,S6}에서 S6이 집단 안에서 아는 사람은 S5 하나뿐이다. S6은 S1·S2·S3·S4 누구와도 직접 관계가 없는데, S5를 경유해 거리 2가 되므로 통과했다. "S6도 이 모둠의 일원"이라고 말하기엔 근거가 얇다.

6. n-클랜과 n-클럽 (n-clan and n-club)

§5의 함정을 막으려고 Mokken(1979)이 두 가지 보완 개념을 제안했다. 둘 다 "거리를 집단 안에서 다시 재라"는 요구다.

정의가 헷갈리니 무엇을 어디서 재는지 표로 못박아 두자.

손 계산 — {S1,…,S6}은 2-클랜인가 (Is It a 2-clan?)

S7, S8을 지우고 여섯 명만 남긴 유도 부분그래프에서 거리를 다시 잰다. 간선은 9개가 남는다(S5–S6 포함, S6–S7과 S6–S8은 잘려 나감).

최댓값이 2이므로 $\operatorname{diam}(G[S])=2 \le 2$ → 2-클랜이다. §4의 전체 거리 행렬과 비교하면 여섯 명 사이의 값이 하나도 변하지 않았다. 지름길이 전부 이 여섯 명 안에 있었다는 뜻이다. 같은 계산을 {S5,S6,S7,S8}에 해도 유도 지름이 2 → 2-클랜. $W$의 두 극대 2-클리크는 둘 다 2-클랜이다(§5의 함정에 걸리지 않았다).

반대로 $C_6$에서는 여덟 개의 극대 2-클리크 중

여덟 개 중 여섯 개가 2-클랜이고, 문제의 두 개가 정확히 걸러진다. n-클랜은 n-클리크의 함정을 고치는 필터다.

7. 완화 ② 빠진 연결을 허용한다 — k-플렉스 (Relaxation ②: Allow Absences — k-plex)

n-클리크는 "거리"를 늦춰서 문제가 생겼다. 그러면 거리는 그대로 두고 빠진 간선 몇 개를 봐주는 쪽으로 가면 어떨까. Seidman & Foster(1978)의 k-플렉스다.

"$k-1$명까지 몰라도 된다"로 바꿔 읽기 (Reading It as "May Miss k−1")

$S$ 안에서 $i$가 만날 수 있는 상대는 자기 자신을 뺀 $s-1$명이다. 그중 모르는 사람 수는

$$(s-1) - \deg_S(i) \;\le\; (s-1) - (s-k) \;=\; k-1$$

즉 각자 최대 $k-1$명까지 몰라도 된다. 이 형태가 훨씬 외우기 쉽다.

손 계산 — {S1,S2,S3,S4,S5}는 2-플렉스인가 (Hand Calculation)

먼저 다섯 명만 남긴 유도 인접행렬을 쓴다(§2의 $W$에서 1~5행·1~5열을 잘라낸 것).

행합을 항 하나도 빼지 않고 전개하면:

S5가 0명을 놓친 것도 의미가 있다. S5는 이 집단의 완전 참여자다. 2-플렉스는 이런 사람과 "한 명 놓친 사람"을 같은 집단으로 묶어 준다.

대조 — S6을 넣으면 무너진다 (Contrast: Adding S6 Breaks It)

2-클리크는 S6까지 넣어 여섯 명을 만들었다. k-플렉스는 어떨까? $\{S1,\dots,S6\}$의 유도 차수를 다시 센다. $s=6$이 되었으니 2-플렉스 기준은 $\deg_S \ge 6-2 = 4$다.

최솟값이 1(S6)이다. $s-k = 1$에서 $k = 6-1 = 5$. $\{S1,\dots,S6\}$은 5-플렉스다 — 즉 "각자 4명까지 몰라도 됨"을 허용해야 겨우 성립한다. 6명 집단에서 4명을 몰라도 된다면 사실상 아무 조건도 아니다.

8. $k$는 어디까지 봐줘도 되는가 — $k < (s+2)/2$ (How Large Can k Be?)

$k$를 키우면 집단은 커지지만 언젠가 "집단"이라 부를 수 없게 된다. 경계선이 어디인지 Seidman & Foster가 정확히 밝혔다.

왜 그런가 — 비둘기집 원리로 손 증명 (Why: A Pigeonhole Argument)

$S$ 안에서 서로 안 친한 두 사람 $i, j$를 잡자(친하면 거리 1이니 볼 필요가 없다). 이 둘 사이에 $S$ 안의 공통 친구가 반드시 있음을 보이면 된다.

⑥의 부등식을 풀면:

$$2(s-k) > s-2 \;\Longleftrightarrow\; 2s-2k > s-2 \;\Longleftrightarrow\; s+2 > 2k \;\Longleftrightarrow\; k < \frac{s+2}{2}$$

겹치는 사람이 바로 $i$와 $j$의 공통 친구이고, 그 사람은 $S$ 안에 있다. 따라서 i→공통친구→j로 두 걸음 — 유도 지름 2가 보장된다. ∎

오늘의 집단들에 적용 (Applying the Test)

9. 완화 ③ 안쪽 친구 수만 요구한다 — k-코어 (Relaxation ③: Require Only Inside Friends — k-core)

k-플렉스와 무엇이 다른가 (How It Differs from k-plex)

부등식의 오른쪽만 다르다. 그런데 그 차이가 전부다.

"해가 유일하다"는 성질은 증명이 짧다. $S_1$과 $S_2$가 각각 조건을 만족하면 $S_1 \cup S_2$의 어떤 정점도 원래 있던 쪽의 친구를 그대로 갖고 있으므로 여전히 $\deg \ge k$다. 즉 합집합도 k-코어 조건을 만족한다 → 모든 것을 합친 것이 유일한 극대해다. k-플렉스에는 이 성질이 없다(합치면 $s$가 커져서 기준도 올라간다).

손 계산 — 벗겨내기로 3-코어 찾기 (Hand Calculation: Peeling)

$W$에서 $k=3$으로 실행한다.

단계 1 — 전체 8명. 차수는 §2의 표에서 그대로 가져온다.

S7, S8을 지운다. 남은 사람: {S1, S2, S3, S4, S5, S6}.

단계 2 — 여섯 명 안에서 차수를 다시 센다. S7·S8이 사라졌으니 그들과 이어져 있던 사람의 차수가 줄어든다.

S6을 지운다. 남은 사람: {S1, S2, S3, S4, S5}.

단계 3 — 다섯 명 안에서 다시 센다. 이 값은 §7의 표에서 이미 구했다.

나머지 $k$들 (The Other Values of k)

따라서 각자의 코어 번호는:

10. 코어 번호는 차수가 아니다 (Coreness Is Not Degree)

§9의 마지막 표에서 노란 두 칸이 오늘의 가장 중요한 교훈이다.

반전 ① — S6: 차수는 S1~S4와 같은데 코어는 낮다 (Same Degree, Lower Coreness)

차수만 보면 S1과 S6은 똑같이 3이다. 그런데 친구의 질이 다르다. S6의 친구 셋 중 둘(S7, S8)이 차수 2짜리 약한 사람이라, 그 둘이 무너지는 순간 S6은 친구 1명만 남는다. S1의 친구는 셋 다 3-코어 소속이라 아무도 무너지지 않는다.

반전 ② — S5: 차수가 제일 높은데 코어는 남들과 같다 (Highest Degree, Ordinary Coreness)

S5는 차수 5로 $W$에서 가장 인기가 많다. 그런데 코어 번호는 3 — S1~S4와 똑같다. S5의 친구 5명 중 S6이 3-코어에서 탈락했기 때문에, 3-코어 안에서 S5의 차수는 4로 줄어든다. 4-코어가 되려면 S5뿐 아니라 나머지 넷도 전부 내부 차수 4를 확보해야 하는데 S1~S4는 3이 한계다.

11. 세 가지 완화 비교 (Comparing the Three Relaxations)

같은 네트워크 $W$를 세 방법으로 분석한 결과를 한 표에 놓는다.

세 축이 서로 다른 것을 잡는다 (Three Different Axes)

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

## ── ① n-클리크: 거리 행렬을 n 이하에서 이진화한 뒤 클리크를 찾는다 (§4) ──
D <- distances(gW)
D[1, ]
S1 S2 S3 S4 S5 S6 S7 S8
 0  2  1  1  1  2  3  3          ← §4 손 계산과 일치

g2 <- graph_from_adjacency_matrix(((D <= 2) & (D > 0)) * 1, mode = "undirected")
lapply(max_cliques(g2), function(v) nm[sort(as.integer(v))])
[1] "S5" "S6" "S7" "S8"
[1] "S1" "S2" "S3" "S4" "S5" "S6"   ← 극대 2-클리크 2개

## ── n-클랜 판정: 유도 부분그래프의 지름 (§6) ──
diameter(induced_subgraph(gW, 1:6))     [1] 2   → 2-클랜
diameter(induced_subgraph(gW, 5:8))     [1] 2   → 2-클랜

## ── ② k-플렉스: 유도 부분행렬의 행합이 s-k 이상인가 (§7) ──
rowSums(W[1:5, 1:5])                    S1 S2 S3 S4 S5
                                         3  3  3  3  4   ← 전부 ≥ 5-2 = 3 → 2-플렉스
rowSums(W[1:6, 1:6])                    S1 S2 S3 S4 S5 S6
                                         3  3  3  3  5  1   ← S6이 1 → 5-플렉스에 불과

## ── ③ k-코어: 벗겨내기는 coreness() 한 줄 (§9) ──
degree(gW)                              S1 S2 S3 S4 S5 S6 S7 S8
                                         3  3  3  3  5  3  2  2
coreness(gW)                            S1 S2 S3 S4 S5 S6 S7 S8
                                         3  3  3  3  3  2  2  2   ← S6만 2 (§10 반전)

13. 실전 — 가라테 클럽의 코어 분해 (In Practice: Core Decomposition of the Karate Club)

단원 3-1에서 가라테 클럽의 극대 클리크가 36개나 나와 읽기 어려웠다. 같은 자료를 k-코어로 보면 34명이 딱 네 층으로 정리된다.

벗겨내기 3단계 (Three Peeling Rounds)

2단계와 3단계가 연쇄 붕괴다. 전체 차수만 봤다면 6, 7, 28, 30, 32, 24번은 모두 4 이상이라 살아남았어야 한다. 그러나 이웃이 먼저 무너지면 같이 무너진다.

32번이 가장 극적이다. 차수 6은 34명 중 5위권인데 코어 번호는 3이다. 이웃 여섯 중 25, 26, 29번이 주변부라 함께 떨어졌다. S6이 S7·S8과 함께 떨어진 것(§10)과 정확히 같은 구조다.

네 층의 명단 (The Four Layers)

4-코어 10명의 내부 밀도 0.5556은 전체 밀도 0.139의 네 배다. 같은 자료를 보고 "34명 중 이 10명이 조직의 뼈대"라고 한 줄로 말할 수 있게 된다.

단원 3-1의 클리크와 맞춰 보기 (Cross-check with Unit 3-1)

즉 4-코어 10명 = {1,2,3,4,8} ∪ {1,2,3,4,14} ∪ {9,31,33,34}이다. 클리크 36개가 뒤엉켜 있던 자리에서 k-코어는 핵심 세 덩어리를 자동으로 골라 합쳐 주었다.

약속했던 확인 — {1,2,3,4,8,14}는 2-플렉스인가 (The Promised Check)

§1에서 "8번과 14번 사이에 간선이 없어서 두 개로 쪼개졌다"고 했다. k-플렉스가 이 둘을 합쳐 주는지 손으로 확인하자. $s=6$, 2-플렉스 기준은 $\deg_S \ge 6-2 = 4$다.

반대 방향의 경고 — 가라테의 2-클리크 (A Warning: 2-cliques in Karate)

가라테 클럽에서 모든 쌍의 61.14%가 이미 거리 2 이내다(지름 5, 평균 거리 2.4082). 그래서 2-클리크의 최대 크기가 18명 — 학급의 절반이 넘는다. "이 18명이 한 집단"이라는 말은 아무것도 알려 주지 않는다.

14. 교실 적용 (Classroom Application)

15. 연습문제 (Exercises)

16. 해설과 답 (Solutions)

문제 1 해설 (Solution 1)

(1) 무엇을 잘라내는가. §2의 8×8 행렬 $W$에서 5, 6, 7, 8번 행과 5, 6, 7, 8번 열만 남긴다. S1~S4와의 연결은 전부 버린다 — 유도 부분그래프란 그런 뜻이다.

버려진 연결에 주의하라. S5는 원래 차수 5(S1, S2, S3, S4, S6)였지만 그중 네 명이 집단 밖이라 잘려 나갔다. 이것이 k-플렉스와 n-클리크의 결정적 차이다.

$s=4$이고 최솟값은 $\min \deg_S = 1$(S5)이다. $s-k \le 1$을 만족하는 가장 작은 $k$를 찾으면 $k \ge 4-1 = 3$.

값의 의미 — 4명 집단에서 각자 2명을 몰라도 된다면 나머지는 1명뿐이다. 사실상 "친구 한 명만 있으면 통과"라는 뜻이라, 집단이라 부르기 민망한 기준이다. 실제로 S5는 이 집단 안에서 S6 한 명만 알고 있다. §7의 왼쪽 집단이 2-플렉스로 통과했던 것과 대조된다.

(2) 정리 적용.

그래서 직접 잰다. 유도 부분그래프의 간선은 S5–S6, S6–S7, S6–S8, S7–S8 네 개다.

(3) 2-클리크 판정. 이번에는 전체 그래프 $W$에서 잰 거리를 쓴다(§4의 표).

(4) 2-클랜 판정. (2)에서 유도 지름이 2임을 이미 구했고, (3)에서 극대 2-클리크임을 확인했다.

문제 2 해설 (Solution 2)

(1) $W'$의 차수. S1–S6과 S2–S6을 추가하면 행렬에서 $[1,6],[6,1],[2,6],[6,2]$ 네 칸이 0에서 1로 바뀐다.

(2) 벗겨내기. $k=3$으로 실행한다.

2단계의 재계산을 항까지 펼쳐 보자. 남은 여섯 명은 {S1,…,S6}이다.

4-코어도 확인해 두자(코어 번호를 확정하려면 필요하다). 차수 4 미만인 S3, S4, S7, S8을 제거하면 {S1, S2, S5, S6}이 남는데, 그 안에서 S1의 친구는 S5, S6 둘뿐(S3, S4를 잃었다)이라 4에 미달이다. S2도 마찬가지, S5와 S6은 3. 결국 전원 제거되어 4-코어는 공집합이다.

(3) S6은 왜 올라갔나. 두 경우의 2단계를 나란히 놓으면 한눈에 보인다.

(4) 대신 S1–S2와 S3–S4를 추가했다면? 이때 왼쪽 다섯 명은 완전한 $K_5$가 되어 차수가 (4,4,4,4,5)로 오른다. 가장 큰 클리크가 5명이 되고 $\omega$가 3에서 5로 뛴다 — 대단한 개선처럼 보인다. 그런데 S6은? S6의 친구 명단은 조금도 바뀌지 않았다: 여전히 S5, S7, S8뿐이다.