Day 23 · 옮기고 합치기, Louvain

A SMALL DETOUR

이번 회차, 내 속도로.

기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 23로 돌아옵니다.

난이도·관심 주제 고르기

이번 회차는 어느 속도로 볼까요?기초부터새 보충 수업부터 짚어요현재 수준으로관심 주제부터 살펴봐요한 걸음 더새 심화 수업까지 넓혀요

더 살펴볼 주제 1~2개 선택연결 요소·커뮤니티 구분추가 09 · 새 수업 · 9회차의 연결 요소와 22회차의 커뮤니티가 헷갈린다면, 두 개념이 언제 같고 언제 다른지 확인하고 돌아갑니다.해상도 한계·삼각형 고리추가 10 · 새 수업 · 22~24회차에서 Q를 키워 커뮤니티를 찾았다면, 그 기준이 작은 무리를 보지 못하는 한계를 확인하고 돌아갑니다.군집 계수·삼각형DAY 21 · 이웃 쌍과 삼각형으로 군집 계수를 세면 무리 안쪽과 길목 노드를 구분할 수 있습니다.모듈러리티 QDAY 22 · 모듈러리티 Q를 손으로 계산해 두 나눔 중 어느 쪽이 나은지 근거를 댈 수 있습니다.Leiden·계층DAY 24 · Leiden의 정제 단계와 해상도를 알면 계층 커뮤니티가 어떻게 만들어지는지 설명할 수 있습니다.계층 커뮤니티·보고서DAY 88 · GraphRAG가 계층 Leiden으로 나눈 커뮤니티마다 보고서를 만드는 과정에서 커뮤니티 레벨의 의미를 확인합니다.

1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.

이렇게 다녀와요 1단계 · 약 12분

출발 · DAY 23Louvain 두 단계
1. 관심 주제연결 요소·커뮤니티 구분추가 09 · 새 추가 수업
복귀 · DAY 23원래 회차 이어가기

연결 요소·커뮤니티 구분 · 9회차의 연결 요소와 22회차의 커뮤니티가 헷갈린다면, 두 개념이 언제 같고 언제 다른지 확인하고 돌아갑니다.

선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.

복귀: DAY 23 → 본과정 다음 회차: DAY 24

01 / UNDERSTAND

핵심 개념

블롱델 등(Blondel et al., 2008)이 제안한 Louvain 방법은 모듈러리티를 빠르게 키우는 근사 알고리즘입니다. 논문은 이 방법으로 노드 1억 1,800만 개, 링크 10억 개가 넘는 웹 그래프를 분석했다고 보고했습니다. Q가 가장 큰 나눔을 보장하지는 않지만, 큰 그래프에서도 쓸 만한 커뮤니티를 빠르게 찾습니다.

1단계(지역 이동)에서는 처음에 모든 노드가 혼자 커뮤니티입니다. 노드를 하나씩 보며, 이웃이 속한 커뮤니티로 옮겼을 때 Q가 얼마나 변하는지(ΔQ) 계산합니다. 증가가 가장 큰 곳으로 옮기되 양수인 곳이 없으면 그대로 두고, 아무도 움직이지 않을 때까지 모든 노드를 반복해서 훑습니다. 혼자인 노드 i를 커뮤니티 C로 옮길 때의 이득은 ΔQ = k_i,in/m − (Σ_tot × k_i)/(2m²)입니다. k_i,in은 i와 C 사이 엣지 수, Σ_tot는 C의 차수 합, k_i는 i의 차수입니다.

2단계(합치기)에서는 찾은 커뮤니티 하나를 노드 하나로 줄인 새 그래프를 만듭니다. 커뮤니티 사이 엣지 수는 새 엣지의 가중치가 되고, 내부 엣지는 자기 루프의 가중치로 남습니다. 이 축약 그래프에서 다시 1단계를 하고, 더 이상 Q가 오르지 않으면 멈춥니다. 합칠 때마다 커뮤니티가 커지므로 중간 결과를 모으면 작은 무리에서 큰 무리로 가는 계층이 생깁니다.

한계도 있습니다. 노드를 훑는 순서나 이득이 같을 때 고르는 규칙에 따라 결과가 달라질 수 있고, 한번 묶인 무리 안이 실제로 잘 이어져 있는지는 다시 확인하지 않습니다. 다음 회차의 Leiden이 이 약점을 고칩니다.

Louvain은 노드를 ΔQ가 양수인 이웃 커뮤니티로 옮기는 단계와 커뮤니티를 한 노드로 합치는 단계를 Q가 오르지 않을 때까지 반복합니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

동아리 네트워크(m=11)에서 모두 혼자인 상태의 Q는 약 −0.13입니다. 민수(차수 2)를 혼자인 지아(차수 3)의 커뮤니티로 옮기면 ΔQ = 1/11 − (3×2)/(2×121) ≈ 0.091 − 0.025 = 0.066으로 양수라 옮깁니다.

이름순(도윤, 민수, 보라, 서준, 유나, 지아, 태오, 하린)으로 훑고 이득이 같을 때 먼저 본 이웃 쪽을 고르면, 첫 바퀴가 끝났을 때 {민수, 지아, 서준, 하린}, {유나, 태오, 보라}, {도윤} 세 무리(Q≈0.33)가 됩니다. 두 번째 바퀴에서 도윤이 유나 쪽으로 옮겨 Q≈0.41이 됩니다.

2단계에서 두 무리를 각각 노드 하나로 합치면 내부 엣지 5개는 자기 루프 가중치 5가 되고, 하린–도윤은 두 노드 사이 가중치 1인 엣지가 됩니다. 두 노드를 더 합치면 Q가 0으로 떨어지므로 여기서 멈추고 최종 Q는 약 0.41입니다.

03 / EXPLORE

직접 실험해 보기

‘한 단계’를 누르기 전에 다음에 움직일 노드와 ΔQ의 부호를 먼저 예측해 보고, 1단계 이동이 끝난 뒤 축약 그래프의 엣지 가중치가 무리 사이 엣지 수와 같은지 확인하세요.

LIVE EXPERIMENT · LOUVAIN

Louvain으로 옮기고 합치기

같은 색 = 같은 커뮤니티(2명 이상)검토 중인 노드의 엣지

Q = −0.128시작: 모든 노드가 혼자 커뮤니티

이웃 커뮤니티로 옮겼을 때 Q가 가장 많이 오르는 곳(ΔQ > 0)으로 옮깁니다. ΔQ가 같으면 이웃을 가나다 순으로 훑을 때 먼저 만난 커뮤니티로.

현재 커뮤니티 8개

{민수}
{지아}
{서준}
{하린}
{도윤}
{유나}
{태오}
{보라}

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1

엣지가 m=10개인 그래프에서 혼자인 노드 i(차수 3)를 생각합니다. 커뮤니티 C1은 i와 엣지 2개로 이어져 있고 차수 합이 14, C2는 i와 엣지 1개로 이어져 있고 차수 합이 2입니다. 두 이동의 ΔQ를 구하고 Louvain이 i를 어디로 옮기는지 답하세요.

힌트 보기

ΔQ = k_i,in/m − (Σ_tot × k_i)/(2m²)이고 2m²=200입니다.

풀이와 비교하기

C1은 2/10 − (14×3)/200 = 0.20 − 0.21 = −0.01, C2는 1/10 − (2×3)/200 = 0.10 − 0.03 = 0.07입니다. 이어진 엣지는 C1 쪽이 더 많지만 C1이 이미 커서 무작위로도 많이 이어질 것으로 기대되므로, 양수인 C2로 옮깁니다.

내 풀이를 해설과 비교하고 다른 점을 확인했어요.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.

옮기고 합치기, Louvain