Leiden과 계층 커뮤니티
Louvain이 찾은 커뮤니티가 속으로는 끊어져 있을 수 있습니다. 이를 고친 Leiden과, 해상도에 따라 달라지는 커뮤니티의 층을 봅니다.
이번 회차, 내 속도로.
기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 24로 돌아옵니다.
난이도·관심 주제 고르기
1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.
이렇게 다녀와요 1단계 · 약 12분
- 출발 · DAY 24Leiden·계층
- 1. 관심 주제연결 요소·커뮤니티 구분추가 09 · 새 추가 수업
- 복귀 · DAY 24원래 회차 이어가기
- 연결 요소·커뮤니티 구분 · 9회차의 연결 요소와 22회차의 커뮤니티가 헷갈린다면, 두 개념이 언제 같고 언제 다른지 확인하고 돌아갑니다.
선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.
핵심 개념
트라그 연구진(Traag, Waltman & van Eck, 2019)은 Louvain이 내부 연결이 매우 약한 커뮤니티를 만들 수 있고, 최악의 경우 서로 이어지지 않은 조각들이 한 커뮤니티로 묶일 수 있음을 보였습니다. 커뮤니티 안에서 두 조각을 잇던 노드가 다른 커뮤니티로 옮겨 가도, 남은 노드들이 각자 그 자리에 머무는 편이 이득이면 끊어진 채로 남고, 합치기 단계에서 한 노드로 굳어 버리기 때문입니다. 논문의 실험에서는 커뮤니티의 최대 25%가 연결이 약했고 최대 16%는 끊어져 있었습니다.
Leiden 알고리즘은 노드 이동과 합치기 사이에 정제(refinement) 단계를 넣습니다. 각 커뮤니티 안에서 노드를 작은 부분 무리로 다시 묶되 같은 커뮤니티 안에서 잘 이어진 노드끼리만 합치고, 이 정제된 부분 무리를 기준으로 축약 그래프를 만듭니다. 그 결과 Leiden이 내놓는 커뮤니티는 연결되어 있음이 보장되고, 반복하면 모든 커뮤니티의 모든 부분 집합이 국소적으로 최적 배치된 나눔으로 수렴합니다. 논문은 Leiden이 Louvain보다 빠르면서 더 좋은 나눔을 찾았다고 보고했습니다.
커뮤니티의 크기는 해상도(resolution) γ로 조절할 수 있습니다. Q = Σ_c [L_c/m − γ(d_c/2m)²]에서 γ를 키우면 큰 커뮤니티의 벌점이 커져 작은 무리로 쪼개지고, 줄이면 큰 무리로 합쳐집니다. 해상도를 바꿔 가며, 또는 찾은 커뮤니티 안에서 다시 커뮤니티를 찾아 가며 결과를 쌓으면 ‘큰 주제 → 세부 주제’ 같은 계층이 생깁니다.
88회차에서 볼 Microsoft GraphRAG는 문서에서 뽑은 엔티티 그래프에 계층 Leiden을 적용해, 커뮤니티가 정한 크기 아래로 작아질 때까지 커뮤니티 안을 다시 나누고 레벨마다 요약 보고서를 씁니다. 어느 레벨이 ‘정답’인지는 데이터가 아니라 질문의 범위가 정합니다.
작은 예제로 따라가기
동아리 네트워크에서 γ=1이면, 8명을 나누는 4,140가지 방법 중 Q가 가장 큰 것은 두 무리 나눔(Q≈0.41)입니다.
γ=2로 올리면 두 무리 나눔은 2×(5/11 − 2×0.25) ≈ −0.09로 떨어지고, {민수, 지아, 서준}, {하린, 도윤}, {유나, 태오, 보라} 세 무리가 약 −0.04로 가장 높아집니다. γ가 1이 아니면 값 자체보다 나눔끼리의 순위를 봅니다.
반대로 γ를 약 0.18보다 낮추면 모두 한 무리(1−γ)가 두 무리(10/11 − γ/2)보다 높아집니다. 해상도를 낮출수록 큰 무리, 높일수록 작은 무리가 됩니다.
직접 실험해 보기
해상도(또는 레벨)를 낮은 값에서 높은 값으로 바꿔 가며 커뮤니티 수와 구성원이 어떻게 쪼개지는지 기록하고, 작은 무리가 큰 무리 안에 그대로 들어가는지 확인하세요.
해상도를 바꿔 큰 무리와 작은 무리 보기
같은 색 = 같은 커뮤니티 · 점선 = 커뮤니티 사이 엣지. 각 소그룹(A~D)은 4명이 모두 연결된 K4입니다.
- 레벨 0 · 전체16명 전체
- 레벨 1 · 큰 무리A+B (8명)C+D (8명)
- 레벨 2 · 작은 무리A (4명)B (4명)C (4명)D (4명)
Louvain은 노드를 옮기다 내부가 끊어진 커뮤니티를 만들 수 있습니다. Leiden(Traag 2019)은 정제 단계로 각 커뮤니티가 내부에서 연결되도록 보장하고, GraphRAG는 이 계층 Leiden을 씁니다. 지금 결과의 내부 연결: 4/4.
이번에는 직접 풀어 보세요
정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.
힌트 보기
다가 빠진 뒤 {가, 나}와 {라, 마} 사이에 남은 엣지가 있는지 보세요.
풀이와 비교하기
다가 빠지면 K 안에는 가–나와 라–마만 남아, {가, 나}와 {라, 마}가 서로 이어지지 않은 두 조각인데도 같은 커뮤니티로 묶여 있습니다. Louvain은 이를 그대로 합칠 수 있지만, Leiden의 정제 단계는 커뮤니티 안에서 이어진 노드끼리만 부분 무리를 만들므로 두 조각이 서로 다른 축약 노드가 되고, 끊어진 채 한 커뮤니티로 남지 않습니다.
풀이와 확인 표시는 이 브라우저에 저장됩니다.
오늘 이해한 것과 다시 볼 것
계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.
메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.오늘의 이해 확인
Leiden이 Louvain에 더한 정제 단계가 보장하는 것은?
완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1
더 깊이 읽기
예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.
From Louvain to Leiden: guaranteeing well-connected communitiesTraag, Waltman & van Eck (2019)Fast unfolding of communities in large networksBlondel et al. (2008)GraphRAG DocumentationMicrosoft이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.