좋은 나눔의 점수
그래프를 무리로 나누는 방법은 아주 많습니다. 어떤 나눔이 더 좋은지를 하나의 숫자로 비교해 봅니다.
이번 회차, 내 속도로.
기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 22로 돌아옵니다.
난이도·관심 주제 고르기
1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.
이렇게 다녀와요 1단계 · 약 12분
- 출발 · DAY 22모듈러리티 Q
- 1. 관심 주제연결 요소·커뮤니티 구분추가 09 · 새 추가 수업
- 복귀 · DAY 22원래 회차 이어가기
- 연결 요소·커뮤니티 구분 · 9회차의 연결 요소와 22회차의 커뮤니티가 헷갈린다면, 두 개념이 언제 같고 언제 다른지 확인하고 돌아갑니다.
선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.
핵심 개념
커뮤니티(community)는 안쪽 연결은 촘촘하고 바깥과의 연결은 성긴 노드 무리입니다. 그런데 ‘촘촘하다’에는 기준이 필요합니다. 엣지가 많은 노드끼리는 우연으로도 많이 이어지기 때문입니다. 모듈러리티(modularity) Q는 실제 커뮤니티 내부 엣지의 비율에서, 각 노드의 차수는 그대로 두고 엣지를 무작위로 다시 이었을 때 기대되는 내부 비율을 뺀 값입니다. 뉴먼과 거반(Newman & Girvan, 2004)이 제안했고, 뉴먼(Newman, 2006)은 이를 행렬 계산으로 최적화하는 방법을 보였습니다.
커뮤니티 c마다 내부 엣지 수 L_c와 구성원 차수 합 d_c를 구하면 Q = Σ_c [L_c/m − (d_c/2m)²]입니다. m은 전체 엣지 수입니다. 앞 항은 실제로 c 안에 있는 엣지의 비율이고, 뒤 항은 무작위로 이었을 때 엣지의 양 끝이 모두 c에 떨어질 것으로 기대되는 비율입니다. 모든 노드를 한 그룹에 넣으면 두 항이 모두 1이라 Q=0이고, 기대보다 내부 연결이 많을수록 Q가 커지며, 엇갈리게 나누면 음수가 될 수도 있습니다.
뉴먼과 거반은 뚜렷한 커뮤니티 구조가 있는 네트워크의 Q가 실제로는 대략 0.3~0.7 범위에 있고 그보다 높은 값은 드물다고 적었습니다. Q는 서로 다른 나눔을 비교하는 점수이지 정답을 알려 주는 값은 아닙니다. 또 Q가 가장 큰 나눔을 찾으려면 따져 볼 경우의 수가 너무 많아, 다음 회차의 Louvain 같은 근사 방법을 씁니다.
작은 예제로 따라가기
동아리 네트워크(m=11)를 {민수, 지아, 서준, 하린}과 {도윤, 유나, 태오, 보라}로 나눕니다. 각 무리의 내부 엣지는 L=5, 차수 합은 d=2+3+3+3=11입니다.
무리 하나의 기여는 5/11 − (11/22)² ≈ 0.455 − 0.25 = 0.205이고, 두 무리를 더하면 Q = 10/11 − 0.5 ≈ 0.41입니다.
{민수, 서준, 도윤, 태오}와 {지아, 하린, 유나, 보라}로 엇갈리게 나누면 각 무리의 내부 엣지는 2개, 차수 합은 11이라 Q = 2×(2/11 − 0.25) ≈ −0.14입니다.
직접 실험해 보기
‘두 무리’, ‘모두 한 그룹(Q=0)’, ‘엇갈린 나눔’ 프리셋을 차례로 눌러 Q와 표의 L_c·d_c를 비교한 뒤, 노드 하나를 눌러 다른 그룹으로 옮겼을 때 Q가 줄어드는지 확인하세요.
그룹을 나누고 모듈러리티 Q 계산하기
- A 민수, 지아, 서준, 하린, 도윤, 유나, 태오, 보라 (8명)
| 그룹 | L_c | d_c | L_c/m | (d_c/2m)² | 기여 |
|---|---|---|---|---|---|
| A | 11 | 22 | 1.000 | 1.000 | 0.000 |
L_c = 그룹 안 엣지 수, d_c = 그룹 구성원 차수 합, m = 전체 엣지 수. 기여 = L_c/m − (d_c/2m)².
이번에는 직접 풀어 보세요
정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.
힌트 보기
m=11, 2m=22입니다. 하린이 옮겨 가면 지아–하린과 서준–하린이 무리 사이 엣지가 됩니다.
풀이와 비교하기
첫 무리는 L=3, d=8, 둘째 무리는 L=6, d=14입니다. Q = 3/11−(8/22)² + 6/11−(14/22)² ≈ 0.140+0.140 ≈ 0.28로, 두 무리 나눔의 0.41보다 낮습니다. 하린의 엣지 3개 중 2개가 원래 무리 쪽에 있기 때문입니다.
풀이와 확인 표시는 이 브라우저에 저장됩니다.
오늘 이해한 것과 다시 볼 것
계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.
메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.오늘의 이해 확인
모듈러리티 식 Q = Σ_c [L_c/m − (d_c/2m)²]에서 뒤 항 (d_c/2m)²이 뜻하는 것은?
완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1
더 깊이 읽기
예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.
Finding and evaluating community structure in networksNewman & Girvan (2004)Modularity and community structure in networksNewman (2006)이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.