7편Subgroups

하위집단 — 클리크·k-코어·커뮤니티

R 실습 — 손으로 돌려 보기STAGED+ 스터디

여기부터는 방향을 버리고 시작한다. "무리"는 대개 방향 없는 개념이기 때문이다.

gu <- igraph::as_undirected(g, mode = "collapse")
igraph::ecount(gu)
[1] 66

왜 88이 66이 되는가 — 상호 지명 22쌍은 화살표 두 개가 간선 하나로 합쳐진다.

88 - 22 = 66

. 4.2절의 dyad census 숫자와 정확히 맞아떨어진다.

mode="collapse"는 한쪽만 지명해도 간선을 남긴다(약한 규칙). mode="mutual"로 하면 상호 지명 22개만 남는다. 어느 쪽을 쓸지는 연구 질문이 정한다 — "누가 서로 친한가"라면 mutual, "누가 누구를 아는가"라면 collapse다. sna에서는 symmetrize(rule="weak")와 rule="strong"이 각각 대응한다.

6.1 클리크 (Cliques)

클리크는 서로가 서로를 다 아는 집단이다. 가장 엄격한 하위집단 정의다. 극대(maximal) 클리크는 여기에 아무도 더 넣을 수 없는 클리크를 말한다.

cl <- igraph::max_cliques(gu, min = 3)
length(cl)
[1] 19
max(sapply(cl, length))
[1] 5

# 크기 5짜리 네 개
for (b in cl[sapply(cl, length) == 5])
  cat(paste(sort(igraph::V(gu)$name[b]), collapse = ", "), "\n")
1006, 1009, 1021, 1057, 1078
1006, 1009, 1027, 1057, 1078
1009, 1027, 1057, 1075, 1078
1018, 1042, 1045, 1048, 1051

# sna 쪽은 크기별 개수를 표로 준다
sna::clique.census(sna::symmetrize(adj, rule = "weak"),
                   mode = "graph", tabulate.by.vertex = FALSE)$clique.count
 1  2  3  4  5
 1  4 10  5  4              # 3+ 짜리 = 10+5+4 = 19, igraph와 일치

교실 해석 — 5명짜리 클리크가 넷인데, 앞의 세 개가 서로 겹친다(1009·1057·1078이 셋 다에 들어 있다). 이건 별개의 세 무리가 아니라 여학생 쪽의 촘촘한 핵심 하나가 여러 방식으로 잘려 나온 것이다. 네 번째 {1018, 1042, 1045, 1048, 1051}만 완전히 별개 — 남학생 핵심이다. 클리크는 이렇게 겹쳐서 나오기 때문에 "무리 나누기"에는 부적합하다. 그래서 6.3절의 커뮤니티 탐지가 필요하다.

6.2 k-코어 (k-Cores)

클리크가 너무 엄격하다면 k-코어가 실용적인 대안이다. "이 안에 있는 모두가 이 안에서 최소 $k$ 명과 연결된" 최대 집단이다.

kc <- igraph::coreness(gu)
table(kc)
kc
 0  2  3  4
 1  3  6 16

igraph::V(gu)$name[kc == 4]
 [1] "1003" "1006" "1009" "1018" "1021" "1027" "1042" "1045"
 [9] "1048" "1051" "1054" "1057" "1060" "1072" "1075" "1078"

교실 해석 — 학급이 세 겹으로 되어 있다.

4-코어 16명 — 서로 안에서 최소 4명씩 연결된 두꺼운 핵심. 학급의 61%다.
3-코어에만 있는 6명 — 핵심에 붙어 있지만 한 겹 바깥.
2-코어 3명 + 0-코어 1명 — 주변부. 1024, 1030, 1033, 1036이 이 언저리다.

k-코어는 클리크와 달리 겹치지 않고 층을 이룬다(4-코어 ⊂ 3-코어 ⊂ 2-코어). "누가 주변부인가"를 볼 때는 클리크보다 이쪽이 훨씬 읽기 쉽다.
※ 이건 igraph에만 있다. sna에는 coreness()에 해당하는 함수가 없다.

클리크는 겹치고 k-코어는 층을 이룬다 — 그림 6 — 왼쪽 5명짜리 클리크 네 개. 분홍 셋은 **1009 · 1057 · 1078을 공유하며 겹쳐** 있고(진한 색), 파랑 하나만 따로 선다. **오른쪽** 같은 학급의 k-코어. 겹치지 않고 **안쪽으로 갈수록 두꺼워지는 층**이다.

6.3 커뮤니티 탐지 (Community Detection)

모듈러리티 $Q$ 는 "이 분할이 얼마나 좋은가"를 재는 점수다. 집단 내부 간선이 우연히 기대되는 것보다 얼마나 많은지를 본다. 0.3을 넘으면 뚜렷한 구조가 있다고 본다.

wt <- igraph::cluster_walktrap(gu)
length(wt)
[1] 5
round(igraph::modularity(wt), 6)
[1] 0.438705
igraph::sizes(wt)
 1  2  3  4  5
10 10  3  2  1

Louvain은 실행할 때마다 답이 달라진다.

qs <- replicate(200, igraph::modularity(igraph::cluster_louvain(gu)))
table(round(qs, 4))
0.4324 0.4351 0.4387
     2     23    175

200번 돌려 세 가지 다른 $Q$ 가 나왔다. 최적값 0.4387이 나올 확률은 88%다. 보고서나 발표 자료에 쓸 값은 결정적 알고리즘으로 뽑는다.

cluster_walktrap(gu)          # 결정적. Q = 0.438705
cluster_edge_betweenness(gu)  # 결정적. Q = 0.438705

이 자료에서는 둘이 완전히 같은 분할을 준다(집단 번호만 다르게 매겨진다). 서로 다른 원리의 두 알고리즘이 같은 답을 냈다는 건 구조가 그만큼 뚜렷하다는 뜻이다.

커뮤니티와 성별의 일치 — 그림 5 — 왼쪽 walktrap이 찾은 5개 집단, **오른쪽** 실제 성별. **경계가 완전히 겹친다.**

table(집단 = igraph::membership(wt),
      성별 = ifelse(igraph::V(gu)$female, "여", "남"))
    성별
집단 남 여
   1  0 10
   2 10  0
   3  0  3
   4  2  0
   5  1  0

교실 해석 — 이 안내서에서 가장 강한 결과다.

다섯 집단이 전부 성별이 한쪽으로만 되어 있다. 0이 아닌 칸이 각 행에 정확히 하나씩이다.

중요한 건 알고리즘이 성별을 전혀 보지 않았다는 점이다. walktrap에 들어간 것은 누가 누구를 지명했는지, 그 연결 구조뿐이다. 그런데 연결만 보고 나눴더니 남녀가 갈렸다.

9세 학급에서 이건 이상한 일이 아니라 발달상 전형적이다. 다만 담임 입장에서는 확인할 값어치가 있다 — "성별을 섞은 모둠"을 짜면 학생들의 자연스러운 관계망을 정면으로 거스르게 된다. 그게 나쁘다는 뜻이 아니라, 그 모둠이 왜 겉도는지를 설명해 준다는 뜻이다.

하위집단 — 클리크·k-코어·커뮤니티

6.1 클리크 (Cliques)

6.2 k-코어 (k-Cores)

6.3 커뮤니티 탐지 (Community Detection)

이어서 읽기