구조적 등위성과 블록모델링

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

단원 3-4에서 아령 그래프 $H$(삼각형 A와 삼각형 B를 다리 A1–B1로 이은 6명 7간선)에 Girvan–Newman과 fast greedy를 각각 돌려 보라고 했다. 답을 짚고 넘어간다.

문제 1 — Girvan–Newman (Solution 1 — Girvan–Newman)

검산: $\sum_e C_B(e)=\sum_{s<t} d(s,t)$. 15쌍의 거리는 1이 7쌍, 2가 4쌍, 3이 4쌍이므로 $7\cdot1+4\cdot2+4\cdot3=7+8+12=27$. 맞다.

GN이 첫 번째로 제거하는 간선은 A1–B1(9로 최대)이고, 그 순간 $Q=5/14\approx 0.3571$. 두 번째부터는 남은 6개 간선이 전부 매개 1로 동점이라 아무거나 잘리고, $Q$는 내려간다.

문제 2 — fast greedy (Solution 2 — Fast Greedy)

$\Delta Q=\dfrac{28\,m_{AB}-2D_AD_B}{196}$에 전원 단독 상태의 값을 넣으면:

다리 A1–B1이 꼴찌인 이유는 공식이 그대로 말해 준다. 분자의 벌점 $2D_AD_B$는 두 끝점의 차수를 곱한 값인데, 다리의 양 끝은 이 그래프에서 가장 차수가 큰 두 명(3, 3)이다. 잇는 간선 수는 똑같이 1개인데 벌점만 18로 가장 크다. 최종 $Q=5/14$로 GN과 같은 답에 도달한다.

2. 오늘의 질문: 간선이 없는데 거리가 0이라니 (A Distance of Zero Without a Tie)

단원 3-4의 walktrap 절에서 이런 값을 봤다. 우리 학급 네트워크 $W$에서

walktrap의 무작위 걷기 거리가 정확히 0이었다. 그런데 $W$를 다시 보면 $A[1,2]=0$ — S1과 S2는 서로 친구가 아니다. 한 번도 이어져 있지 않은 두 사람의 거리가 왜 0인가?

S1의 행과 S2의 행이 여덟 칸 모두 글자 하나 다르지 않다. 두 사람은 서로를 모르지만 아는 사람의 명단이 완전히 같다.

3. 구조적 등위성의 정의 (Defining Structural Equivalence)

정점 $i$와 $j$가 구조적으로 등위라는 것은, 두 사람이 나머지 모든 사람에 대해 똑같은 관계를 갖는다는 뜻이다. 무방향 네트워크에서는:

방향 네트워크라면 보내는 쪽과 받는 쪽을 둘 다 봐야 한다:

행렬로 말하면 $i$행과 $j$행이 같고, $i$열과 $j$열이 같다는 것이다. $i$행은 $i$가 누구에게 보내는지, $i$열은 $i$가 누구에게 받는지를 담고 있으니, 등위란 보내는 명단도 같고 받는 명단도 같다는 말이다.

4. W에서 손으로 찾기 — 28쌍 전부 (Finding It by Hand in W: All 28 Pairs)

8명이니 쌍은 $\binom{8}{2}=28$개. 이웃 목록만 놓고 전부 대조한다.

이웃 목록이 글자 그대로 같은 쌍을 찾으면 두 쌍이 바로 보인다.

나머지 쌍은 왜 아닌지 한 번씩 짚어 둔다. 차수부터 다르면 볼 것도 없다:

(S7, S8)이 걸린다. 두 사람의 이웃 목록은 정확히 한 글자만 다르고, 그 다른 글자가 하필 서로의 이름이다. 이건 별도로 다룬다.

5. 두 가지 관례 — 서로 아는 쌍둥이 문제 (Two Conventions: The True-Twin Problem)

S7과 S8을 나란히 놓아 보자.

여섯 칸은 같고 딱 두 칸이 다르다. 그런데 그 두 칸은 7열과 8열, 즉 두 사람 자신의 자리다. S7이 S8과 친구이고 S8이 S7과 친구인 것 — 사실 이건 "이웃이 다르다"기보다 "서로 친구다"라는 말에 가깝다.

그래서 두 가지 관례가 있다.

차이가 나는 자리는 오직 $A[i,j]$와 $A[i,i]$ 두 종류뿐이다. 자기 고리가 없는 네트워크에서 $A[i,i]=A[j,j]=0$이므로, 두 관례가 갈리는 것은 $A[i,j]=1$일 때, 즉 두 사람이 서로 친구일 때뿐이다.

6. 거리로 재기 — 해밍 거리 (Measuring by Hamming Distance)

실제 데이터에서 완전히 등위인 쌍은 거의 없다. 그래서 "얼마나 등위에 가까운가"를 재는 자가 필요하다. 가장 단순한 자가 해밍 거리다.

말로 하면 "두 사람의 이웃 명단에서 서로 어긋나는 이름이 몇 개인가"이다. 0이면 완전 등위, 클수록 다른 자리에 있다.

손 계산 — (S1, S3) (Hand Calculation: S1 and S3)

1열과 3열을 빼고 나머지 여섯 열을 하나씩 대조한다. 같은 칸도 빠짐없이 적는다.

손 계산 — (S5, S6) (Hand Calculation: S5 and S6)

이 쌍이 $W$에서 가장 먼 쌍 중 하나다. 5열과 6열을 빼고 여섯 열을 본다.

$D(S_5,S_6)=6$ — 여섯 칸 중 여섯 칸이 다르다. 남은 모든 사람에 대해 두 사람의 태도가 정반대다. 그런데 이 두 사람은 서로 친구다($A[5,6]=1$). 친하지만 자리가 정반대인 사이 — 다리를 놓는 두 사람의 전형적인 모습이다.

28쌍 전부 (All 28 Pairs)

거리 행렬로 정리하면:

     S1 S2 S3 S4 S5 S6 S7 S8
S1    0  0  2  2  2  4  5  5
S2    0  0  2  2  2  4  5  5
S3    2  2  0  0  2  4  5  5
S4    2  2  0  0  2  4  5  5
S5    2  2  2  2  0  6  5  5
S6    4  4  4  4  6  0  1  1
S7    5  5  5  5  5  1  0  0
S8    5  5  5  5  5  1  0  0

유클리드 거리 (Euclidean Distance)

교재는 유클리드 거리도 쓴다. 0과 1로만 된 데이터에서는 둘의 관계가 아주 단순하다.

$A[i,k]-A[j,k]$는 −1, 0, 1 셋 중 하나뿐이고 제곱하면 1, 0, 1이 된다. 즉 제곱합이 곧 어긋난 칸의 개수다. 따라서 이진 데이터에서는

예: $D(S_1,S_3)=2$일 때 $d_E=\sqrt{2}\approx 1.4142$. 순서(누가 더 가까운가)는 어차피 같으므로, 손으로 볼 때는 해밍 쪽이 훨씬 읽기 좋다.

7. R의 sedist는 왜 값이 두 배인가 (Why sedist Doubles Everything)

교재 코드대로 sedist(W, method="hamming")를 돌리면 우리가 손으로 구한 값의 정확히 두 배가 나온다. $D(S_1,S_3)=2$인데 R은 4를 찍는다. 왜 그럴까?

sedist는 방향 네트워크를 기본으로 만들어졌다. §3에서 봤듯 방향 네트워크의 등위는 행(보내기)과 열(받기)을 둘 다 봐야 한다. 그래서 sedist는 각 정점의 프로필을 이렇게 이어 붙인다:

그런데 무방향 네트워크에서는 $A$가 대칭이라 $A[i,k]=A[k,i]$다. 보내기 프로필과 받기 프로필이 똑같은 벡터다. 같은 벡터를 두 번 이어 붙였으니 어긋나는 칸도 정확히 두 번 세어진다.

> all(D == sedist(W, method='hamming') / 2)
[1] TRUE

8. 상관으로 재기 (Measuring by Correlation)

해밍은 "몇 칸 다른가"만 센다. 그런데 차수가 크게 다른 두 사람은 겹치는 이웃이 많아도 해밍이 커진다. 이걸 보정하려고 피어슨 상관을 쓰기도 한다.

해밍과 달리 클수록 비슷하다(거리가 아니라 유사도다). 1이면 완전 등위, −1이면 정반대.

손 계산 — $r(S_1,S_3)$ (Hand Calculation)

1열·3열을 빼면 남는 열은 (S2, S4, S5, S6, S7, S8) 여섯 개.

평균은 둘 다 $\bar x = \bar y = 2/6 = 1/3$. 편차를 전부 적는다.

재미있는 점: S6, S7, S8 세 칸은 둘 다 0인데도 곱이 $+1/9$로 양수 기여를 한다. "둘 다 저 사람들과는 안 논다"는 공통의 부재도 유사성으로 세는 것이다. 해밍이라면 이 세 칸은 그냥 "안 다름"으로 0점 처리된다. 이게 두 자의 성격 차이다.

손 계산 — $r(S_5,S_6) = -1$ (A Perfect Anticorrelation)

5열·6열을 빼면:

여기서 $y = 1 - x$다. 즉 $y$는 $x$의 완벽한 뒤집기다. 어떤 변수와 그것을 뒤집은 변수의 상관은 항상 정확히 −1이므로

§6에서 해밍 6(최댓값)이었던 그 쌍이 상관에서도 −1(최솟값)이다. 두 자가 같은 답을 준 셈.

주요 쌍 비교 (Side-by-Side Comparison)

(S1,S3)과 (S1,S5)를 보라. 해밍은 둘 다 2로 똑같은데 상관은 0.25 대 0.5로 갈린다. S5는 차수 5로 S1의 이웃을 전부 품고 있어서, "겹치는 정도"로 보면 S1과 더 닮았다. 해밍은 이 차이를 못 잡고 상관은 잡는다.

9. 위계적 군집화 — 덴드로그램 손 추적 (Hierarchical Clustering by Hand)

이제 거리 행렬 $D$가 있으니 가까운 것끼리 묶어 올라간다. 단원 3-4의 fast greedy와 겉모습은 같은 병합형이지만, 기준이 $Q$가 아니라 등위 거리라는 점이 다르다.

묶인 덩어리 사이의 거리는 완전 연결법(complete linkage)으로 잰다:

"가장 안 닮은 두 사람의 거리"를 덩어리의 거리로 삼는 것이다. 보수적인 기준이라 덩어리 안의 모든 사람이 서로 그 높이 이내로 닮았음이 보장된다. 등위 분석에는 이 성질이 중요해서 equiv.clust의 기본값도 complete다.

1단계 — 거리 0인 쌍부터 (Step 1: Distance Zero)

$D$의 최솟값은 0이고, 그런 쌍이 세 개다. 순서대로 묶는다.

지금 덩어리는 다섯 개: {S1,S2}, {S3,S4}, {S5}, {S6}, {S7,S8}

2단계 — 다섯 덩어리의 거리 10쌍 전부 (Step 2: All Ten Cluster Pairs)

가장 가까운 쌍은 {S6}과 {S7,S8}. 높이 1에서 병합한다. 덩어리는 넷: {S1,S2}, {S3,S4}, {S5}, {S6,S7,S8}

3단계 — 세 곳이 동점 2 (Step 3: A Three-Way Tie)

2가 셋이나 동점이다. R은 번호 순서로 {S1,S2}+{S3,S4}를 먼저 묶는다(높이 2). 그다음 {S1,S2,S3,S4}와 {S5}의 거리는 $\max(2,2,2,2)=2$로 여전히 2 — 그래서 같은 높이 2에서 S5도 흡수된다.

4단계 — 마지막 (Step 4: The Last Merge)

남은 두 덩어리 {S1,S2,S3,S4,S5}와 {S6,S7,S8}의 거리는 $\max(4,5,5,4,5,5,4,5,5,4,5,5,\mathbf{6},5,5)=\mathbf{6}$ — $D(S_5,S_6)=6$이 최대다. 높이 6에서 전체가 하나가 된다.

어디서 자를 것인가 (Where to Cut)

10. 블록모델 ① 밀도 행렬 25칸 (Blockmodel: The Density Matrix)

위치를 정했으면 이제 위치끼리의 관계를 요약한다. 8×8 행렬을 5×5로 줄이는 것이다. 이것이 블록모델링이다.

위치 $\mathcal{A}$에서 위치 $\mathcal{B}$로 가는 블록 밀도는:

$h=0.5$에서 자른 다섯 위치로 25칸을 전부 계산한다.

P1={S1,S2}, P2={S3,S4}, P3={S5}, P4={S6}, P5={S7,S8}

칸 수를 다 더하면 $14+14+7+7+14=56=8\times7$로, 대각선(자기 자신)을 뺀 인접행렬의 모든 칸을 정확히 한 번씩 덮었다. 검산 통과.

        P1 P2 P3 P4 P5
P1       0  1  1  0  0
P2       1  0  1  0  0
P3       1  1 NA  1  0
P4       0  0  1 NA  1
P5       0  0  0  1  1

11. 블록모델 ② 이미지 행렬과 오차 (The Image Matrix and Fit)

밀도 행렬을 한 번 더 줄여 0과 1만 남긴다. 기준은 보통 전체 밀도다.

그런데 $W$의 밀도 행렬은 이미 전부 0 아니면 1이다. 자를 것이 없다. 밀도 행렬 = 이미지 행렬이다.

블록모델의 오차 (Blockmodel Error)

오차는 "이상적인 블록이라면 이랬어야 하는데 실제로 어긋난 칸의 수"다. 1블록(완전 블록)에서는 0인 칸이, 0블록(영 블록)에서는 1인 칸이 오차다.

$W$의 5위치 블록모델에서는 오차 = 0이다. 모든 블록이 밀도 정확히 0 아니면 1이니, 어긋난 칸이 하나도 없다. 이를 완벽 적합(perfect fit) 또는 lean fit이라 부른다.

더 굵게 자르면 어떻게 되는가 (Cutting Coarser)

$h$를 높여 위치를 줄이면 오차가 생긴다. R 눈금 $h=3$(손 눈금 1.5)이면 위치 4개 — {S1,S2} {S3,S4} {S5} {S6,S7,S8} — 이고, 이때 P4→P4 밀도가 다음과 같다:

여기는 삼각형이라 아직 1이다. 문제는 다른 칸에서 생긴다. R로 확인하면 $h=3$에서 0.3333짜리 칸이 나타난다 — 0도 1도 아닌 어중간한 블록, 곧 오차가 있는 블록이다. $h=5$(손 눈금 2.5, 위치 2개)까지 굵게 자르면 0.8000, 0.0667, 1.0000 같은 값이 나온다.

12. 방향 네트워크 — 보내기와 받기 (Directed Networks: Send and Receive)

§3에서 방향 네트워크는 행과 열을 둘 다 봐야 한다고 했다. 왜 그런지 교재(block modeling.r)의 5명짜리 예제로 확인한다.

  A B C D E
A 0 1 1 0 0     A는 B, C에게 보낸다
B 0 0 0 1 1     B는 D, E에게 보낸다
C 0 0 0 1 1     C는 D, E에게 보낸다
D 0 0 0 1 1     D는 자기 자신과 E에게 보낸다  ← 자기 고리
E 0 0 0 1 0     E는 D에게 보낸다

완화 관례(자기들 행·열은 제외)로 10쌍을 판정하면 이렇게 갈린다.

(A, B)를 손으로 (Hand Calculation: A and B)

행 비교 — A행과 B행에서 A열·B열을 뺀 (C, D, E) 세 칸:

열 비교 — A열과 B열에서 A행·B행을 뺀 (C, D, E) 세 칸:

13. R로 검증 (Verification in R)

library(sna); 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 }

## 완화 해밍 거리 D — i, j 열을 빼고 비교 (손 계산과 같은 눈금)
D <- matrix(0, 8, 8, dimnames = list(nm, nm))
for (i in 1:8) for (j in 1:8) {
  kk <- setdiff(1:8, c(i, j))
  D[i, j] <- sum(W[i, kk] != W[j, kk])
}
D
   S1 S2 S3 S4 S5 S6 S7 S8
S1  0  0  2  2  2  4  5  5
S2  0  0  2  2  2  4  5  5
S3  2  2  0  0  2  4  5  5
S4  2  2  0  0  2  4  5  5
S5  2  2  2  2  0  6  5  5
S6  4  4  4  4  6  0  1  1
S7  5  5  5  5  5  1  0  0
S8  5  5  5  5  5  1  0  0

## sedist는 보내기+받기를 이어 붙이므로 무방향에서는 정확히 두 배 (§7)
all(D == sedist(W, method = "hamming") / 2)
[1] TRUE

## 상관은 두 배로 붙여도 값이 안 변한다 (§8)
sedist(W, method = "correlation")[5, 6]
[1] -1

## 위계적 군집화 — 손으로 추적한 병합 순서(§9)와 대조
hc <- hclust(as.dist(D), method = "complete")
cbind(hc$merge, height = hc$height)
              height
[1,] -1 -2        0     {S1,S2}
[2,] -3 -4        0     {S3,S4}
[3,] -7 -8        0     {S7,S8}
[4,] -6  3        1     S6 + {S7,S8}
[5,]  1  2        2     {S1,S2} + {S3,S4}
[6,] -5  5        2     S5 흡수
[7,]  4  6        6     전체 통합

paste(cutree(hc, h = 0.5), collapse = "")
[1] "11223455"

## 블록모델 — h는 sedist 눈금이라 손 눈금의 두 배로 넣는다
ec <- equiv.clust(W, method = "hamming", cluster.method = "complete")
ec$cluster$height
[1] 0 0 0 2 4 4 12   ← 손 계산 0,0,0,1,2,2,6 의 두 배

bm <- blockmodel(W, ec, h = 1)      # 손 눈금 0.5
bm$block.membership[order(bm$order.vector)]
[1] 1 1 2 2 3 4 5 5
round(bm$block.model, 4)
        Block 1 Block 2 Block 3 Block 4 Block 5
Block 1       0       1       1       0       0
Block 2       1       0       1       0       0
Block 3       1       1     NaN       1       0
Block 4       0       0       1     NaN       1
Block 5       0       0       0       1       1

## 전체 밀도 — 이미지 행렬의 문턱값
sum(W) / (8 * 7)
[1] 0.4285714

14. 가라테에 적용 (Applying It to Karate)

인공 예제 $W$는 너무 깨끗했다. 실제 데이터에서는 어떨까? 34명 78간선의 가라테 클럽에 같은 절차를 돌린다.

완전히 등위인 쌍 (Perfectly Equivalent Pairs)

$\binom{34}{2}=561$쌍 중 거리가 정확히 0인 쌍은 11개다. 그런데 이 11쌍은 흩어져 있지 않고 딱 두 무리를 이룬다.

거의 등위인 쌍과 가장 먼 쌍 (Near-Equivalent and Farthest Pairs)

거리 1(딱 한 칸 어긋남)인 쌍도 9개 있다: (5,6), (7,11), (8,14), (10,29), (12,13), (12,18), (12,22), (18,20), (20,22).

반대쪽 끝은 (1, 34), 거리 25다. 차수 16과 17로 이 클럽에서 가장 큰 두 사람, 사범과 회장이다. 561쌍 중 가장 등위가 아닌 쌍이 두 지도자라는 것 — 둘 다 "지도자"이지만 거느린 사람이 겹치지 않는다는 뜻이다.

덴드로그램을 잘라 보면 (Cutting the Dendrogram)

이건 등위 분석이 틀린 게 아니라 다른 걸 물었기 때문이다. 등위 분석이 가장 먼저 갈라낸 것은 파벌이 아니라 "많이 거느린 사람 vs 그렇지 않은 사람", 즉 계층이다. $k=4$로 더 쪼개서야 1번과 33·34번이 각각 떨어져 나오고 ARI가 0.3675까지 올라간다.

15. 커뮤니티와 위치는 다른 질문이다 (Community vs Position)

16. 정규 등위성 맛보기 (A Taste of Regular Equivalence)

구조적 등위성에는 한계가 하나 있다. 지난 시간의 아령 그래프 $H$를 보자.

   A2 ---- A3        B2 ---- B3
    \      /          \      /
     \    /            \    /
      A1 ------------- B1

A1과 B1의 등위 거리는 4다 — 여섯 칸 중 네 칸이 어긋난다. 구조적 등위성의 기준으로는 전혀 닮지 않은 두 사람이다.

그런데 그림을 보면 두 사람은 명백히 똑같은 처지다. 각자 삼각형 하나를 거느리고, 다리 하나를 붙들고 있다. 왼쪽 그림을 좌우로 뒤집으면 A1은 정확히 B1이 된다.

이 직관을 정의로 옮긴 것이 정규 등위성(regular equivalence)이다. 대략 이런 뜻이다:

정의에 "등위"가 다시 들어가는 재귀적 정의라, 구조적 등위성처럼 한 번 훑어서 계산할 수 없다. 반복해서 수렴시키는 알고리즘(REGE, CATREGE 등)이 따로 있다.

17. 교실 적용 (Classroom Application)

18. 연습문제 (Exercises)

19. 해설과 답 (Solutions)

문제 1 해설 — 아령 그래프의 구조적 등위성 (Solution 1)

(1) 이웃 목록과 15쌍의 거리. 먼저 인접행렬을 놓는다.

(A2, A3)를 예로 전개해 본다. 2열·3열을 빼고 나머지 (A1, B1, B2, B3) 네 칸:

(A1, B1)도 전개한다. A1열·B1열을 빼고 (A2, A3, B2, B3) 네 칸:

15쌍 전부:

(3) 병합 5단계. complete linkage로 추적한다.

(4) 밀도 행렬 16칸. a={A1}, b={A2,A3}, c={B1}, d={B2,B3}로 놓는다.

칸 수 검산: $(0+2+1+2)+(2+2+2+4)+(1+2+0+2)+(2+4+2+2)=5+10+5+10=30=6\times5$. 통과.

    a  b  c  d
a  NA  1  1  0
b   1  1  0  0
c   1  0 NA  1
d   0  0  1  1

문제 2 해설 — W에 간선 하나를 더하면 (Solution 2)

(1) 여전히 등위인가. 새 행렬 $W'$에서 S1행과 S2행을 나란히 놓는다.

(2)(3)(4) 바뀌는 칸. 바뀌는 이유는 하나다 — 1열과 2열의 값이 달라졌기 때문. 따라서 어떤 쌍의 거리는 그 쌍이 1열·2열을 비교 대상에 포함하는지에만 달려 있다.

(5) 새 덴드로그램. 새 거리 행렬:

     S1 S2 S3 S4 S5 S6 S7 S8
S1    0  0  1  1  1  5  6  6
S2    0  0  1  1  1  5  6  6
S3    1  1  0  0  2  4  5  5
S4    1  1  0  0  2  4  5  5
S5    1  1  2  2  0  6  5  5
S6    5  5  4  4  6  0  1  1
S7    6  6  5  5  5  1  0  0
S8    6  6  5  5  5  1  0  0