이분 네트워크와 투영

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

단원 3-5에서 두 문제를 냈다. 답을 짚고 넘어간다.

문제 1 — 아령 그래프 $H$의 구조적 등위성 (Solution 1 — Structural Equivalence in the Barbell)

$H$는 삼각형 A(A1,A2,A3)와 삼각형 B(B1,B2,B3)를 다리 A1–B1로 이은 6명 7간선 그래프다. 완화 해밍 거리 $D(i,j)=\#\{k\notin\{i,j\}: A[i,k]\neq A[j,k]\}$를 15쌍 전부 구하면:

등위 쌍은 (A2,A3)와 (B2,B3) 둘뿐이다. 각각 이웃이 정확히 같고 ($N(A2)=N(A3)=\{A1,A3\}$ 또는 $\{A1,A2\}$ — 서로를 뺀 나머지가 같다), 게다가 서로 간선이 있으므로 엄격 관례에서는 등위가 아니고 완화 관례에서만 등위다. 3-5에서 배운 서로 아는 쌍둥이(true twins)다.

완전 연결(complete linkage) 병합 높이는 0, 0, 1, 1, 4. 즉 (A2,A3)@0 → (B2,B3)@0 → A1이 {A2,A3}에 @1 → B1이 {B2,B3}에 @1 → 두 덩어리가 @4에 합쳐진다. $h=0.5$로 자르면 위치 4개 {A1} {A2,A3} {B1} {B2,B3}가 나온다(소속 벡터 122344).

모든 칸이 0 아니면 1이므로 오차 0이다. 칸 수는 $0+2+1+2\;/\;2+2+2+4\;/\;1+2+0+2\;/\;2+4+2+2=30=6\cdot 5$로 딱 맞는다. 3-5의 $W$와 달리 여기서는 두 대각 칸이 1이다 — {A2,A3}와 {B2,B3}는 서로 아는 쌍둥이라 자기들끼리도 다 이어져 있다(완전 블록).

문제 2 — $W$에 S1–S2 간선을 더하면 (Solution 2 — Adding One Edge to W)

세 가지가 동시에 일어난다.

• 등위는 살아남지만 종류가 바뀐다. $A[1,2]=1$이 되었으므로 엄격 등위는 깨지고 (all(W2[1,]==W2[2,]) → FALSE) 완화 등위만 남는다. S1,S2는 서로 모르는 쌍둥이 → 서로 아는 쌍둥이로 바뀌었다.
• 정확히 12칸의 거리가 바뀐다. 그것도 양방향으로:

  바뀐 쌍	이전	이후	왜
  (S1,S3) (S1,S4) (S1,S5) (S2,S3) (S2,S4) (S2,S5)	2	1	S1이 S2와 이어지자 S3·S4·S5의 이웃 목록과 더 닮아졌다
  (S1,S6) (S2,S6)	4	5	S6는 S2와 안 이어져 있는데 S1은 이어짐 → 어긋난 칸 하나 추가
  (S1,S7) (S1,S8) (S2,S7) (S2,S8)	5	6	같은 이유. S7·S8과는 더 멀어졌다

  간선 하나가 어떤 쌍은 가깝게, 어떤 쌍은 멀게 만든다. 구조적 등위 거리는 "연결"이 아니라 "연결 패턴의 일치"를 재기 때문이다.
• 블록모델은 딱 한 칸만 바뀐다. 새 병합 높이는 0, 0, 0, 1, 1, 2, 6이고 $h=0.5$로 자르면 위치는 그대로 5개(11223455)다. 밀도 행렬에서 $P_1\!\to\! P_1$ 칸만 0에서 1로 — 영 블록(null block)이 완전 블록(complete block)으로 바뀐다. 오차는 여전히 0이다. ($h=1.5$로 자르면 11112333, 위치 3개가 된다.)

2. 오늘의 질문: 명단밖에 없을 때 (Today's Question: When All You Have Is a Roster)

단원 1-1부터 3-5까지, 우리가 다룬 행렬 $A$는 예외 없이 학생 × 학생이었다. $A[i,j]=1$은 "$i$와 $j$가 친구다"라는 뜻이었고, 그 자료를 얻으려면 누군가에게 "너는 누구와 친하니?"라고 직접 물어야 했다.

그런데 실제 교실에서 교사가 손에 쥐고 있는 자료는 대개 그런 모양이 아니다. 동아리 신청서, 모둠 배정표, 방과후 수업 명단, 도서 대출 기록, 체험학습 조 편성표 — 전부 학생 × 무엇이다. 아무도 교우관계를 조사하지 않았지만, "누가 어디에 속해 있는가"는 이미 다 적혀 있다.

이 단원의 절반은 만드는 법(§3–§8), 나머지 절반은 잃는 것(§9–§15)에 관한 이야기다. 그리고 잃는 쪽이 훨씬 중요하다.

3. 이분 네트워크와 소속행렬 (Two-mode Networks and the Incidence Matrix)

이분(bipartite) 네트워크 또는 2-모드(two-mode) 네트워크는 정점이 두 종류로 나뉘고, 간선이 서로 다른 종류 사이에만 놓이는 네트워크다. 학생끼리는 이어지지 않고, 활동끼리도 이어지지 않는다. 오직 "학생 — 활동"만 이어진다.

이 단원 내내 쓸 예제를 정한다. 학생 6명(S1–S6), 활동 4개(E1=축구부, E2=독서부, E3=밴드부, E4=봉사부).

행합과 열합은 서로 다른 것을 센다.

• 행합 $r_i=\sum_k A[i,k]$ = 학생 $i$가 참여한 활동 수. S1은 2개, S4는 1개.
• 열합 $c_k=\sum_i A[i,k]$ = 활동 $k$의 인원 수. E1은 3명, E2는 2명.

둘의 총합은 반드시 같다. 둘 다 행렬 안의 1을 전부 센 값이기 때문이다.

4. 하나의 인접행렬로 합치기 (Folding It into One Adjacency Matrix)

$A$는 정사각행렬이 아니라서 지금까지 배운 도구(거듭제곱, 중심성, 컴포넌트)를 바로 쓸 수 없다. 그래서 학생과 활동을 전부 정점으로 취급해 $(n+m)\times(n+m)$ 정사각 인접행렬로 다시 쓴다.

$B$는 대칭이고 간선 수는 $\sum A = 10$개다. 소속행렬의 1 하나가 간선 하나가 된다. 그림 21의 오른쪽 패널이 바로 이 $B$를 그린 것이다. 빨간 선으로 나눈 네 블록 중 대각 두 블록이 완전히 비어 있고, 비대각 두 블록이 서로 전치 관계다.

5. 이분 네트워크에는 삼각형이 없다 (No Triangles: Odd Cycles Are Impossible)

$B$ 위를 걷는다고 생각해 보자. 학생에서 출발하면 반드시 활동으로 가고, 활동에서는 반드시 학생으로 온다. 한 걸음마다 모드가 바뀐다. 따라서 출발점으로 돌아오려면 짝수 걸음이 필요하다.

단원 1-3에서 배운 도구로 ①을 바로 확인할 수 있다. 삼각형 개수는 $\operatorname{tr}(A^3)/6$이었다.

10개 대각 원소가 전부 0이다. 우연이 아니라 구조적으로 그럴 수밖에 없다. $B^2$의 비대각 블록이 0이고(§8) $B^3$의 대각 블록이 0이기 때문이다.

②·③은 실제 거리 행렬로 확인한다. $B$의 측지거리 10×10 중 학생–학생 부분:

초록 칸(학생–학생)은 전부 짝수, 노란 칸(학생–활동)은 전부 홀수다. 지름은 7 — S6에서 E2까지다. 경로를 따라가 보면 S6 → E4 → S5 → E3 → S3 → E1 → S1 → E2 로 정확히 7걸음이다.

6. 학생 투영 — 15쌍 전부 (The Actor Projection: All 15 Pairs)

이제 본론이다. "학생 × 활동" 자료에서 "학생 × 학생" 네트워크를 뽑아내는 것을 투영(projection)이라 한다.

$R[1,2]$ — S1과 S2 (Expanding R[1,2] Term by Term)

0이 되는 항도 생략하지 않고 네 항을 전부 쓴다.

$R[1,3]$ — S1과 S3 (Expanding R[1,3])

$R[1,4]$ — S1과 S4 (Expanding R[1,4])

15쌍 전부 (All 15 Pairs at Once)

나머지도 같은 방식이다. 어느 활동에서 곱이 1이 되는지만 적으면 충분하다.

모아 쓰면 다음 6×6 대칭행렬이다.

7. 활동 투영 — 6쌍 전부 (The Event Projection: All 6 Pairs)

곱하는 순서를 뒤집으면 반대쪽 모드의 네트워크가 나온다.

$C[1,2]$ — 축구부와 독서부 (Expanding C[1,2])

이번에는 학생 6명 전부에 대해 더한다. 여섯 항을 모두 쓴다.

$C[2,4]$ — 독서부와 봉사부 (Expanding C[2,4])

6쌍 전부와 결과 행렬 (All 6 Pairs)

여기서도 대각선은 지우기 전에 $(A^{\mathsf T}A)[k,k]=\sum_i A[i,k]^2 = c_k$, 즉 활동의 인원 수였다. E1–E4는 3, 2, 3, 2로 §3의 열합과 같다.

8. 두 투영은 $B^2$ 안에 이미 들어 있다 (Both Projections Live Inside B²)

여기서 단원 1-2가 되돌아온다. 그때 배운 것은 $(A^2)[i,j]$가 $i$에서 $j$로 가는 2단계 경로의 수라는 사실이었다. $B$를 제곱하면 무슨 일이 벌어지는지 블록으로 계산해 보자.

실제 $B^2$를 보면 정확히 그 모양이다.

파란 블록이 $AA^{\mathsf T}$(대각선은 학생 차수 2,2,2,1,2,1), 노란 블록이 $A^{\mathsf T}A$(대각선은 활동 크기 3,2,3,2), 비대각 블록은 전부 0이다. "짝수 걸음으로는 모드를 바꿀 수 없다"(§5)가 행렬로 나타난 모습이다.

같은 논리로 $B^3 = \begin{pmatrix}\mathbf 0 & AA^{\mathsf T}A \\ A^{\mathsf T}AA^{\mathsf T} & \mathbf 0\end{pmatrix}$이므로 대각 블록이 0, 곧 $\operatorname{tr}(B^3)=0$이고 삼각형이 없다(§5). 두 사실은 같은 사실이다.

9. 투영의 대가 ① 정보 손실 (The Price of Projection: Information Loss)

투영은 편리하지만 되돌릴 수 없다. 결정적인 이유를 가장 작은 예로 보인다.

학생 X, Y, Z 셋이 있다. 두 가지 전혀 다른 상황을 생각해 보자.

두 상황은 완전히 다르다. (가)에서는 셋이 한 자리에 같이 있었고, (나)에서는 한 번도 셋이 모인 적이 없다. 그런데 투영을 계산하면:

투영을 하는 순간 우리는 "몇 명이 모인 자리였는가"를 버린다. 그리고 다음 절에서 보듯, 바로 그 버려진 정보가 결과를 가장 크게 왜곡한다.

10. 투영의 대가 ② 공짜로 생기는 클리크 (Cliques You Never Observed)

$c_k$명이 참여한 활동 하나는 투영에서 그 $c_k$명 전원을 서로 잇는다. 즉 활동 하나가 크기 $c_k$의 클리크 하나를 만든다. 만들어지는 간선 수는

이 값은 $c_k$에 대해 제곱으로 늘어난다. 2인 활동은 간선 1개, 5인 활동은 10개, 14인 활동은 91개다.

우리 예제에서 확인해 보자. 이진화한 투영 $R$의 삼각형을 세면 2개다: {S1,S2,S3}(전부 E1 축구부)와 {S3,S4,S5}(전부 E3 밴드부). 전역 군집계수는

더 나쁜 것은 이 인위적 클리크들이 서로 겹친다는 점이다. 활동별로 만든 간선을 다 더하면 $\sum_k \binom{c_k}{2}$인데, 실제 투영 간선 수는 그보다 적다. 같은 쌍이 여러 활동에서 반복해 이어지기 때문이다. 우리 예제에서는

인데 실제 간선은 7개다. 차이 1은 (S1,S2)가 E1과 E2 양쪽에서 이어지기 때문이다. 바로 그 쌍이 가중치 2를 갖는다. §14에서 이 겹침이 훨씬 심해지는 실제 자료를 본다.

11. 이분 네트워크의 밀도와 차수 (Density and Degree in Two-mode)

이분 자료에서는 분모가 달라진다. 단원 1-5에서 무방향 밀도는 $\dfrac{2L}{n(n-1)}$이었지만, 여기서는 학생끼리 이어질 가능성 자체가 없으므로 $n(n-1)/2$를 분모로 쓰면 안 된다.

"학생 한 명이 참여할 수 있는 활동 4개 중 평균 1.67개에 참여했다"는 뜻이다.

차수 정규화도 마찬가지로 갈라진다. 두 모드는 서로 다른 최댓값을 갖는다.

12. 가중치를 거리로 되돌리기 (Turning Weight Back into Distance)

투영 $R$의 값은 강도다. $R[i,j]$가 클수록 두 학생은 가깝다. 그런데 근접 중심성이나 매개 중심성은 거리를 더해 나가는 지표다. 강도를 그대로 거리로 쓰면 부호가 뒤집힌다 — 단원 2-5에서 다룬 그 문제가 그대로 재현된다.

교재 bipartite_1.R이 closeness(1/R)라고 쓴 것이 이 때문이다. 가중치의 역수를 거리로 삼는다.

S1에서 출발해 보자. 두 방식의 결과가 어떻게 갈리는지 항을 전부 쓴다.

S1과 S2가 활동 두 개를 함께한 덕분에 S1의 근접 중심성이 올라갔다. S3는 두 방식 모두 $5/6 = 0.8333$으로 같다 — S3에 붙은 간선은 전부 가중치 1이라 바뀔 것이 없다.

13. 뉴먼 가중 투영 (Newman's Weighted Projection)

§10에서 본 문제 — 큰 활동일수록 간선을 제곱으로 쏟아낸다 — 를 정면으로 다루는 방법이 있다. 큰 활동에서 만난 것은 덜 쳐 주자는 발상이다.

우리 예제의 활동 크기는 $c = (3,2,3,2)$이므로 쌍당 기여는 $\bigl(\tfrac12,\,1,\,\tfrac12,\,1\bigr)$이다.

순위가 어떻게 달라졌는지 보자. 원 가중치로는 (S1,S2)=2가 (S5,S6)=1의 두 배였다. 뉴먼으로는 1.5 대 1.0으로 1.5배로 줄었다. 이유는 명확하다 — S1,S2가 함께한 E1은 3인 활동이라 "둘만의 관계"라는 증거가 약하고, S5,S6이 함께한 E4는 둘뿐인 활동이라 훨씬 강한 증거다.

그리고 (S1,S3)=0.5와 (S5,S6)=1.0을 비교하면 순위가 뒤집혔다. 원 가중치로는 둘 다 1로 동점이었지만, 뉴먼은 "3명 중에서 만난 것"보다 "둘만 있는 자리에서 만난 것"을 두 배로 쳐 준다.

14. 실전: Davis 남부 여성 18명 (Davis's Southern Women)

2-모드 분석의 표준 자료를 쓴다. Davis, Gardner & Gardner가 1930년대 미국 남부의 한 도시에서 여성 18명이 사교 행사 14개에 참석한 기록을 신문 사교란과 관찰로 모은 것이다(1941). 누구도 "누가 누구와 친하냐"고 묻지 않았다. 오직 참석 명단뿐이다. tnet 패키지에 들어 있다.

원자료 (The Raw Two-mode Data)

그림 24 왼쪽에서 이미 구조가 보인다. 빨간 선 위쪽(W1–W9)은 왼쪽 행사들(E1–E9)에, 아래쪽(W10–W18)은 오른쪽 행사들(E7–E14)에 몰려 있다. 원저가 두 집단으로 나눈 것이 이 패턴이다. 원자료에는 구조가 뚜렷이 남아 있다.

투영하면 무슨 일이 벌어지는가 (What Projection Does to It)

왜 이렇게 됐는가? $\binom{c_k}{2}$를 활동별로 더해 보면 답이 나온다.

그런데 실제 간선은 139개다. 같은 쌍이 평균 $322/139 = 2.32$번 중복해서 이어진 셈이다. 특히 E8 한 행사에 14명이 참석했으므로 그것만으로 $\binom{14}{2}=91$개 — 전체 139개 간선의 65.5%를 혼자 만들어 낸다. 실제로 E8을 빼고 투영하면 간선이 139에서 121개로, 밀도가 0.7908로 떨어진다.

가중치를 살리면 (Keeping the Weights)

같은 투영에 가중치를 그대로 두고 단원 3-4의 알고리즘을 돌린다.

ARI 0.7772면 원저의 분할을 상당히 잘 복원한 것이다. 갈리는 지점은 W8과 W9 — 원저에서는 둘 다 1집단인데 Louvain은 W8을 2집단으로 보낸다. 실제로 W8은 행사 3개(E6, E8, E9)에만 참석했고 그중 E8, E9는 양쪽 집단이 다 오는 큰 행사다. 소속이 애매한 것은 알고리즘 탓이 아니라 자료가 실제로 애매하기 때문이다. Davis 자료를 다룬 20여 편의 논문이 대부분 W8, W9, W16을 경계 사례로 꼽는다.

뉴먼 가중을 적용하면 (Applying Newman Weighting)

§13의 공식을 이 자료에 적용하면 가장 가까운 쌍이 바뀐다.

W1과 W3은 7번이나 같이 있었는데도 1위를 내준다. 함께한 행사가 E8(14명), E9(12명), E5·E6(8명)처럼 크기 때문이다. 반면 W13과 W14는 6번뿐이지만 그중 E13, E14는 3명짜리 작은 모임이라 $1/2$씩 온전히 받는다. "몇 번 마주쳤나"와 "얼마나 사적인 자리에서 마주쳤나"는 다른 질문이다.

두 가중치의 스피어만 순위상관은 0.9422로 전반적으로는 비슷하지만, 바로 그 상위권에서 순서가 갈린다. 그리고 상위권이 곧 분석 결과를 좌우한다.

15. 투영하지 말고 이분 그래프에서 바로 (Skip the Projection Entirely)

§9–§14를 요약하면 "투영은 정보를 잃고 인위적 구조를 더한다"는 것이다. 그렇다면 가장 자연스러운 해법은 투영하지 않는 것이다. $B$는 어차피 정사각 인접행렬이므로, 커뮤니티 탐지 알고리즘을 거기에 바로 돌릴 수 있다.

결과가 질적으로 다르다.

• $Q = 0.3225$ — 투영 후의 0.1519보다 두 배 이상 높다. 인위적 밀도가 없으니 분모가 부풀지 않았다.
• 각 집단이 여성과 행사를 함께 담고 있다. "이 사람들이 한 집단"이 아니라 "이 사람들이 이 행사들에 모인다"까지 한 번에 말해 준다. 투영으로는 얻을 수 없는 정보다.
• 여성 부분만 떼어 원저와 비교하면 ARI 0.4473으로 Louvain-on-투영(0.7772)보다 낮다. 집단을 2개가 아니라 4개로 쪼갰기 때문이다. 이것을 "더 나쁘다"고 읽을 필요는 없다 — 더 잘게 본 것이고, P1과 P2가 원저의 1집단, P3와 P4가 대체로 2집단에 해당한다.

16. R로 검증 (Verification in R)

먼저 소속행렬을 만들고 두 가지 방법으로 투영한다.

library(igraph)
A <- matrix(c(1,1,0,0,  1,1,0,0,  1,0,1,0,
              0,0,1,0,  0,0,1,1,  0,0,0,1),
            nrow = 6, byrow = TRUE,
            dimnames = list(paste0("S",1:6), paste0("E",1:4)))

## 방법 1 — 행렬 곱으로 직접
R <- A %*% t(A); diag(R) <- 0     # 학생 투영
C <- t(A) %*% A; diag(C) <- 0     # 활동 투영

## 방법 2 — igraph (현대 함수명)
gB <- graph_from_biadjacency_matrix(A)   # 옛 이름: graph.incidence()
is_bipartite(gB)                          # TRUE
V(gB)$type                                # FALSE=학생, TRUE=활동
pr <- bipartite_projection(gB, multiplicity = TRUE)
as_adjacency_matrix(pr[[1]], attr = "weight")   # R 과 일치
as_adjacency_matrix(pr[[2]], attr = "weight")   # C 와 일치

두 방법이 같은지 확인했다 — TRUE. 교재가 쓰는 sna 경로도 같은 결과다.

## 교재 방식 — B를 손으로 조립
n <- nrow(A); m <- ncol(A)
B <- rbind(cbind(matrix(0,n,n), A),
           cbind(t(A), matrix(0,m,m)))
sum(B)/2                       # [1] 10   간선 수 = sum(A)
sum(diag(B %*% B %*% B))       # [1] 0    삼각형 없음 (§5)
all(distances(graph_from_adjacency_matrix(B, mode="undirected"))[1:6,1:6] %% 2 == 0)
                               # [1] TRUE 학생끼리 거리는 모두 짝수

§13의 뉴먼 가중은 tnet에 구현되어 있다. 손 계산과 일치하는지 확인했다.

library(tnet)
New <- matrix(0, 6, 6)
cs  <- colSums(A)
for (i in 1:6) for (j in 1:6) if (i != j) for (k in 1:4)
  if (A[i,k] == 1 && A[j,k] == 1) New[i,j] <- New[i,j] + 1/(cs[k] - 1)
New[1,2]                       # [1] 1.5    = 1/2 + 1  (§13과 일치)

## Davis 자료로 tnet 내장 함수와 대조
data(Davis.Southern.women.2mode)
tn <- projecting_tm(as.tnet(Davis.Southern.women.2mode,
                            type = "binary two-mode tnet"), method = "Newman")
                               # 손 계산과 전부 일치 (TRUE)

17. 교실 적용 (Classroom Application)

18. 연습문제 (Exercises)

19. 해설과 답 (Solutions)

문제 1 (a) — 이분 밀도 (Solution 1a — Two-mode Density)

행합은 2, 2, 2, 2, 1이고 열합은 5, 2, 2다. 검산: $2+2+2+2+1 = 9 = 5+2+2$ ✓

문제 1 (b) — 학생 투영 10쌍 (Solution 1b — All 10 Pairs)

세 항을 전부 쓴다. 곱하는 것은 $T$의 $i$행과 $j$행이다.

문제 1 (c) — 밀도 1.0을 어떻게 읽을 것인가 (Solution 1c — Reading a Density of 1.0)

10쌍 모두 $R[i,j]\ge 1$이므로 이진화하면 간선 10개, 즉 $K_5$ 완전그래프다.

문제 1 (d) — 활동 투영 (Solution 1d — The Event Projection)

문제 1 (e) — 뉴먼 가중 (Solution 1e — Newman Weighting)

활동 크기는 $c = (5, 2, 2)$이므로 쌍당 기여는

문제 2 (a)(b) — 두 개의 서로 다른 소속행렬 (Solution 2ab — Two Different Incidence Matrices)

가장 단순한 두 가지는 §9의 3인 예제를 4인으로 늘린 것이다.

(나)의 여섯 활동은 $\binom{4}{2}=6$개 쌍 각각에 하나씩 대응한다: G1={U1,U2}, G2={U1,U3}, G3={U1,U4}, G4={U2,U3}, G5={U2,U4}, G6={U3,U4}.

확인해 보자. (가)에서 $R[1,2]$는 항이 하나뿐이라 $1\cdot 1 = 1$. (나)에서 $R[1,2]$는 여섯 항을 전부 쓰면

나머지 5쌍도 같은 방식으로 정확히 1이 된다. 각 쌍마다 딱 하나의 활동에서만 곱이 1이기 때문이다.

문제 2 (c) — 최소 활동 수 (Solution 2c — The Minimum Number of Events)

문제 2 (d) — 뉴먼 가중은 둘을 구별하는가 (Solution 2d — Can Newman Weighting Tell Them Apart?)

(가)는 활동 크기 $c=4$이므로 쌍당 기여가 $\dfrac{1}{4-1}=\dfrac13$. (나)는 모든 활동이 $c=2$이므로 $\dfrac{1}{2-1}=1$.

다음 단원 — 3-7 동질성(homophily)과 E-I 지수. 지금까지는 "누가 누구와 이어져 있는가"라는 구조만 봤다. 이제 정점에 속성(성별, 성적 수준, 출신 학교, 관심사)을 붙이고 묻는다: 비슷한 사람끼리 뭉치는가? E-I 지수 한 줄로 "우리 반은 남녀가 갈라져 있는가"에 수치로 답하는 법을 손 계산으로 배운다.