배열 모형 — 차수를 고정하고 남는 것

1. 오늘의 질문: 차수를 빼고 나면 무엇이 남는가 (What Remains After Degree?)

가라테의 군집계수는 0.2557이다. $G(n,m)$으로 무작위화하면 0.1348이 나온다(4-7 §12). "실제가 두 배 가까이 높으니 뭉쳐 있다"고 말하고 싶다. 그런데 반론이 하나 있다.

이 반론은 정당하다. $G(n,m)$의 차수 분산은 3.9인데 가라테는 15.0이다(4-7 §11). 차수 분포부터가 다르다. 두 망은 애초에 비교 대상이 아니다.

해결책은 하나다. 차수를 실제와 똑같이 맞춘 무작위 망을 만들면 된다. 1번은 여전히 16명과, 34번은 여전히 17명과, 12번은 여전히 1명과 친구인 채로 누구와만 다시 뽑는 것이다. 그렇게 만든 망의 군집계수가 여전히 0.2557보다 낮다면, 그때는 "차수 때문이 아니다"라고 말할 수 있다.

2. 정의 — 반쪽 간선을 짝짓는다 (Pairing Half-Edges)

차수를 정확히 보존하면서 무작위로 잇는 방법은 놀랄 만큼 단순하다.

3번 단계가 핵심이다. 반쪽 간선에는 이름표가 없다 — 1번의 첫째 실인지 셋째 실인지 구별하지 않는다. 그저 $2m$개를 무작위로 짝짓는다.

이 규칙에서 차수는 자동으로 보존된다. 1번에 실이 16개 붙어 있으면 어떻게 짝지어도 1번의 차수는 16이다. 간선 수도 자동으로 $2m/2=m$이다. 4-7 §11에서 WS·BA가 못 했던 것이 정의만으로 해결된다.

3. 손 계산 ① 짝짓는 방법의 수 (Counting the Pairings)

작은 예로 끝까지 손으로 계산한다. 정점 4개, 차수 $(d_1,d_2,d_3,d_4)=(3,2,2,1)$.

반쪽 간선 8개에 번호를 붙여 두자. 1번의 것을 $a_1,a_2,a_3$, 2번의 것을 $b_1,b_2$, 3번의 것을 $c_1,c_2$, 4번의 것을 $e_1$이라 하자.

3-1. 8개를 둘씩 묶는 방법은 몇 가지인가 (How Many Ways to Pair Up Eight Stubs)

순서대로 세어 나간다.

• 아직 안 묶인 것 중 가장 앞의 것을 잡는다. 그 짝이 될 수 있는 것은 나머지 7개.
• 그 둘을 빼면 6개 남는다. 다시 가장 앞의 것의 짝은 5가지.
• 4개 남으면 3가지, 2개 남으면 1가지.

이것을 이중 계승(double factorial)이라 하고 $(2m-1)!!$로 쓴다.

3-2. 특정한 두 반쪽 간선이 서로 묶일 확률 (The Chance Two Given Stubs Pair Up)

$a_1$의 짝을 뽑는다고 생각하자. 후보는 $a_1$을 뺀 7개이고 전부 동등하다. 따라서 $a_1$이 하필 $b_1$과 묶일 확률은

4. 손 계산 ② 두 사람이 이어질 기대 횟수 (Expected Edges Between Two Nodes)

이제 진짜 궁금한 것을 계산한다. 1번과 2번 사이에 간선이 몇 개나 생기는가?

4-1. 지시함수로 분해한다 (Decomposing with Indicators)

1번의 실은 $a_1,a_2,a_3$, 2번의 실은 $b_1,b_2$다. 1–2 간선이 생기는 사건은 "$a$ 중 하나와 $b$ 중 하나가 묶이는 것"이고, 그런 짝의 조합은 $3\times2=6$가지다. 하나하나 지시함수로 쓰면

기대값의 선형성으로 여섯 항을 전부 전개한다.

일반화하면 항이 $d_i d_j$개이고 각각 $1/(2m-1)$이므로

4-2. 여섯 쌍 전부 (All Six Pairs)

합이 맞는지 확인하는 항등식이 있다.

5. 손 계산 ③ 자기고리와 검산 (Self-Loops and the Checksum)

서로 다른 쌍의 기대 간선을 다 더했더니 3.2857인데, 간선은 $m=4$개여야 한다. 0.7143개가 어디로 갔는가? 자기고리다.

5-1. 자기고리 기대 수 (Expected Number of Self-Loops)

정점 $i$ 안에서 실 두 개가 서로 묶이는 경우다. 고를 수 있는 쌍의 수는

각 쌍이 실제로 묶일 확률은 역시 $1/(2m-1)$이므로

5-2. 검산 — 전부 더하면 정확히 $m$ (Check: Everything Sums to Exactly m)

6. 3-3의 $d_id_j/2m$은 어디서 왔는가 (Where the Expected-Edge Term Comes From)

3-3에서 모듈러리티를 배울 때 이런 식을 썼다.

그때는 "$d_id_j/2m$이 무작위였을 때 기대되는 간선 수"라고만 하고 넘어갔다. 오늘 그 출처가 배열 모형이라는 것이 밝혀진다. 다만 분모가 다르다.

6-1. 근사의 오차는 정확히 얼마인가 (Exactly How Large Is the Approximation Error)

비율을 보면 오차가 $m$에만 의존한다는 것이 바로 나온다.

즉 모든 쌍에서 오차 비율이 똑같다. 가라테는 $2m=156$이므로

더 깔끔한 사실도 있다. §5-2의 합이 $2m-1$에서는 정확히 $m$이었는데, $2m$으로 바꾸면

어떤 망에서든 정확히 0.5개만큼 모자란다. 가라테로 확인하면 $2m-1$일 때 $74.593548+3.406452=78.000000=m$, $2m$일 때 $77.5=78-0.5$다.

7. R 검증 ① 몬테카를로 (Monte Carlo Check)

손으로 구한 $6/7$, $3/7$, $5/7$이 정말 맞는지 2만 번 돌려 확인한다.

ds <- c(3,2,2,1)
g  <- sample_degseq(ds, method="configuration")   # 자기고리·다중간선 허용
# 20000회 반복하며 쌍별 간선 수와 자기고리 수를 누적

모든 칸이 소수 둘째 자리까지 맞는다. 특히 4번의 자기고리가 정확히 0인 것이 좋은 확인이다 — 차수 1이면 짝지을 실이 없다는 손 계산이 그대로 나타났다.

8. R 검증 ② 가라테의 기대 간선 (Expected Edges in Karate)

같은 식을 가라테($n=34$, $m=78$, $2m=156$)에 적용한다.

1번 한 사람 안에서도 편차가 크다.

17배 차이다. 배열 모형이 $G(n,m)$과 근본적으로 다른 점이 여기 있다. $G(n,m)$에서는 모든 쌍의 기대값이 $78/\binom{34}{2}=0.139$로 똑같았다. 배열 모형은 상대의 인기까지 반영한다.

9. 함정 — simplify는 표본을 망친다 (simplify vs the vl Method)

§2에서 배열 모형이 다중 간선과 자기고리를 만든다고 했다. 실무에서 흔히 하는 처리는 simplify()로 지우는 것이다. 이것이 표본을 심하게 왜곡한다.

g1 <- simplify(sample_degseq(dk, method="configuration"))  # 지우기
g2 <- sample_degseq(dk, method="vl")                       # 단순그래프만 뽑기

simplify는 평균 11.9개(78개 중 15%)의 간선을 버린다. 그리고 버려지는 간선은 무작위가 아니다. 다중 간선은 $d_id_j$가 큰 쌍, 즉 허브끼리에서 주로 생긴다. 자기고리도 $\binom{d_i}{2}$에 비례하니 허브에서 생긴다. 결국 허브의 차수만 골라서 깎는다.

결과가 두 방향으로 나타난다.

• 차수동류성이 −0.1614로 올라간다(vl은 −0.3011). 허브의 차수가 깎이면 차수 격차가 줄어 이질성이 약해 보인다.
• 군집계수가 0.1650으로 떨어진다(vl은 0.2238). 간선이 15% 없어졌으니 삼각형도 줄어든다.

9-1. vl은 정말 차수를 보존하는가 (Does vl Really Preserve Degrees)

500개 표본 전부 검사했다.

10. R 검증 ③ 차수를 고정해도 남는 것 (What Survives: Karate)

이제 §1의 질문에 답한다. vl로 500번 무작위화하고 채점한다.

10-1. 군집계수 — §1의 반론이 맞았다 (Clustering: The Objection in §1 Was Right)

10-2. 모듈러리티 — 이것은 남는다 (Modularity: This One Survives)

반대로 파벌 분할의 $Q$는 압도적이다. 무작위 평균이 −0.0205로 0 근처인데 실제는 0.3715, $z=+8.38$이다. 500개 표본 중 0.115를 넘은 것이 하나도 없다.

§8에서 본 $A[1,34]=0$이 여기서 값을 만든다. 차수만 보면 1번과 34번은 1.75개로 이어져 있어야 하는데 0이다. 두 허브가 서로를 피하고 각자 자기편을 데려간 구조 — 이건 차수 수열 어디에도 안 적힌 정보다.

10-3. 차수동류성 — 무작위도 음수지만 실제는 더 음수다 (Assortativity: Random Is Negative, Observed Is More So)

실제 $r=-0.4756$, 무작위 평균 $-0.3011$, $z=-3.55$. 읽을 점은 무작위조차 −0.30으로 꽤 음수라는 것이다.

이유는 §8에서 이미 나왔다. 차수 17짜리 34번이 이을 상대는 33명뿐인데 그중 차수가 큰 사람은 몇 없다. 허브가 많은 이웃을 가지려면 필연적으로 차수 낮은 사람들과 이어질 수밖에 없다. 이것은 구조적 제약이지 "인기 있는 애가 인기 없는 애와 친하다"는 사회적 사실이 아니다.

11. R 검증 ④ FMH — 차수로 전혀 설명 안 되는 망 (FMH)

가라테는 "군집계수가 설명됐다"는 온건한 결과였다. FMH 거대성분($n=439$, $m=573$)은 정반대다. 300표본.

여덟 지표 전부 $\lvert z\rvert\gt6$이다. 가라테에서 군집계수가 $z=1.23$으로 "설명됐다"던 것과 대조하면 FMH는 차수 수열이 거의 아무것도 설명하지 못한다.

11-1. E-I 지수의 부호가 뒤집히는 것 (The Sign Flip)

가장 극적인 칸이다. E-I 지수는 3단계에서 배운 대로

−1이면 완전 동종, +1이면 완전 이종이다.

부호만 뒤집힌 게 아니라 크기도 비슷하게 대칭이다. 왜 무작위가 +0.63인지는 간단하다. 학년이 4개면 무작위로 이었을 때 상대가 다른 학년일 확률이 약 3/4다. 이종이 기본값이고, 실제는 그 기본값에서 정반대로 가 있다.

11-2. 거리와 군집계수가 동시에 크다 (Both Long and Clustered)

FMH는 평균 거리 $z=+124$로 무작위보다 멀고, 군집계수 $z=+92$로 무작위보다 뭉쳐 있다. 이 조합이 4-4에서 배운 왓츠–스트로가츠의 격자 쪽 끝이다 — 그래서 4-7 §11에서 WS만이 FMH의 거리·지름을 자릿수라도 맞혔던 것이다.

동시에 4-7에서 WS가 군집계수를 0.0022로 완전히 실패했다는 것도 기억하자. 오늘의 결론은 그때보다 강하다. 4-7에서는 "여섯 모형 중 아무도 못 맞혔다"였는데, 오늘은 실제 차수 수열을 그대로 주었는데도 못 맞혔다. FMH의 구조는 차수에도, 지금까지 배운 어떤 생성 규칙에도 담기지 않는다.

12. 네 모형 최종 대조 (Final Comparison of Four Models)

4단계에서 배운 것을 한 표로 닫는다. 가라테, 각 300회.

배열 모형만이 간선 78개와 최대 차수 17을 정확히 재현한다. 그러면서 군집계수도 실제에 가장 가깝다(0.2251 대 0.2557).

13. 교실 적용 (Classroom Application)

13-1. 교우관계 조사에 그대로 쓰는 절차 (A Procedure You Can Run on Friendship Data)

5번이 실무적으로 가장 중요하다. 지표를 열 개 재서 열 개를 다 보고하면 어느 것이 진짜 발견인지 알 수 없다. 가라테에서 군집계수 0.2557은 숫자만 보면 인상적이지만 $z=1.23$이므로 보고할 것이 없다.

13-2. "인기 많은 애가 있어서 그런 것 아닌가?"에 답하는 법 (Answering "Isn't It Just the Popular Kids?")

교사·관리자와 이야기할 때 가장 자주 나오는 반론이 이것이다. 그리고 정당한 반론이다 — 가라테에서는 실제로 맞았다(§10-1).

13-3. 차수를 고정한다는 것의 교실적 의미 (What Fixing Degrees Means in a Classroom)

배열 모형이 하는 일을 교실 언어로 옮기면 이렇다.

이 관점에서 §10~§11의 결과를 다시 읽으면 문장이 아주 단순해진다.

• 가라테의 삼각형은 선택이 아니다. 친구 수만 그대로 두고 제비뽑기해도 39개가 나온다(실제 45개).
• 가라테의 파벌 분열은 선택이다. 제비뽑기 500번 중 한 번도 이 정도로 갈리지 않았다.
• FMH의 학년 벽은 선택이다. 제비뽑기하면 오히려 학년을 넘나드는 쪽이 기본값이다(+0.63).

13-4. 한계 — 배열 모형이 답하지 못하는 것 (Limits: What the Configuration Model Cannot Answer)

14. 연습문제 (Exercises)

15. 해설과 답 (Solutions)

15-1. 연습문제 1 해설 (Solution to Exercise 1)

(가) 짝짓는 방법의 수.

반쪽 간선 12개를 둘씩 묶는다. 남은 것 중 가장 앞의 것을 잡아 짝을 정해 나가면 후보 수가 11, 9, 7, 5, 3, 1로 줄어든다.

차례대로 곱하면

특정 두 반쪽 간선이 묶일 확률은 후보가 $2m-1=11$개이므로

(나) 열 쌍 전부. $E[X_{ij}]=d_id_j/11$.

검산:

(다) 자기고리. $E[\text{자기고리}_i]=\binom{d_i}{2}/11$.

(라) 근사와의 비교.

§6에서 유도한 대로 오차 비율은 $\frac{2m}{2m-1}-1=\frac1{2m-1}=\frac1{11}=9.09\%$로 쌍과 무관하게 일정하다.

15-2. 연습문제 2 해설 (Solution to Exercise 2)

(가) $z$ 계산. $z=(X_{\text{실제}}-\bar X)/s$를 네 번 적용한다.

(나) 보고할 것과 안 할 것.

(다) 담임에게 할 답.