# Leiden 알고리즘, Louvain의 끊긴 커뮤니티를 고치는 법

- 게시: 2026.07.15
- 원문(HTML): https://trendbrief.news/articles/leiden-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-louvain%EC%9D%98-%EB%81%8A%EA%B8%B4-%EC%BB%A4%EB%AE%A4%EB%8B%88%ED%8B%B0%EB%A5%BC-%EA%B3%A0%EC%B9%98%EB%8A%94-%EB%B2%95.html
- 발행: [트렌드브리프](https://trendbrief.news/)

> Leiden 알고리즘은 그래프를 커뮤니티로 나누는 클러스터링 방법이다. Traag 등이 2019년 발표해 Louvain의 끊긴 커뮤니티 결함을 고치고 연결성을 보장한다. 파이썬 leidenalg·igraph 실행법과 목적 함수 선택 기준을 정리했다.

## Leiden 알고리즘이 푸는 문제

Leiden 알고리즘은 큰 그래프를 서로 촘촘하게 연결된 덩어리, 곧 커뮤니티로 나누는 클러스터링 방법이다. Vincent Traag와 Ludo Waltman, Nees Jan van Eck가 2019년 학술지 Scientific Reports에 발표한 논문 'From Louvain to Leiden'에서 제안했고, 널리 쓰이던 Louvain 알고리즘이 이따금 내부가 끊긴 커뮤니티를 만드는 결함을 잡아 모든 커뮤니티가 하나로 연결되도록 보장한다. 2026년 7월 기준 파이썬에서는 논문 저자가 만든 leidenalg 패키지나 igraph의 내장 함수로 몇 줄이면 돌릴 수 있다.

이 글은 개발자 눈높이에서 Leiden이 무엇을 푸는지, Louvain과 어디가 다른지, 파이썬에서 어떻게 실행하는지를 실무 위주로 정리한다. 알고리즘 내부의 수학적 증명이나 GPU 가속 구현은 범위 밖이다.

먼저 용어부터 정리하자. 그래프는 점(노드)과 그 점을 잇는 선(엣지)으로 이뤄진 관계 데이터이고, 커뮤니티는 안쪽 연결은 빽빽하고 바깥과의 연결은 성긴 노드 집합이다. 친구 관계망에서 자주 어울리는 무리, 논문 인용망에서 같은 분야끼리 모인 군집이 흔한 예다. 노드가 수만 개를 넘어 눈으로 군집을 찾을 수 없을 때, 모듈러리티(modularity) 같은 점수를 최대화하도록 노드를 묶는 작업이 커뮤니티 탐지(community detection)다. 모듈러리티는 무작위로 연결된 그래프와 견줘 커뮤니티 안쪽 연결이 얼마나 더 빽빽한지를 재는 지표다.

## Louvain은 왜 끊긴 커뮤니티를 만드나

Louvain은 노드를 이웃 커뮤니티로 하나씩 옮겨 보며 점수가 오르면 옮기는 방식이라, 한 덩어리 안에서 다리 역할을 하던 노드가 다른 커뮤니티로 빠져나가도 남은 노드들은 그대로 한 커뮤니티로 남는다. 그래서 이름은 하나인데 내부가 두 조각으로 끊긴 커뮤니티가 생긴다.

Traag, Waltman, van Eck는 2019년 Scientific Reports에 실은 논문에서 이 결함을 정면으로 다뤘다. 저자들의 실험에 따르면 Louvain 결과에서 커뮤니티의 최대 25%가 제대로 연결되지 않았고, 최대 16%는 내부가 아예 끊겨 있었다. 같은 알고리즘을 여러 번 반복 적용하면 문제가 더 도드라졌다고 논문은 보고한다. 눈에 잘 안 띄던 이 약점을 처음으로 정량화한 셈이다.

## Leiden은 연결성을 어떻게 보장하나

Leiden은 Louvain의 두 단계 사이에 '정제(refinement)' 단계를 하나 더 끼워 넣어 끊긴 커뮤니티를 막는다. 한 번의 반복은 세 단계로 돈다.

- 지역 이동: 각 노드를 이웃 커뮤니티로 옮겨 점수가 오르는지 본다. Leiden은 방금 바뀐 노드의 이웃만 다시 검사해 불필요한 재계산을 줄인다.
- 정제: 이동으로 만들어진 각 커뮤니티를 다시 들여다보며 내부에서 잘 연결된 부분끼리만 하위 커뮤니티로 쪼갠다. 끊긴 조각이 한 이름 밑에 살아남지 못하게 막는 핵심 단계다.
- 집계: 정제된 커뮤니티를 하나의 노드로 압축해 더 작은 그래프를 만들고, 이 그래프에 같은 과정을 반복한다.

이 구조 덕분에 Leiden이 내놓는 모든 커뮤니티는 내부가 하나로 연결된다고 논문은 증명한다. 반복을 계속하면 어떤 노드를 다른 커뮤니티로 옮겨도 점수가 오르지 않는 안정된 분할로 수렴한다. 논문은 Leiden이 Louvain보다 더 빠르면서 더 나은 분할을 찾는다고 보고한다.

## 파이썬에서 Leiden 실행하기

가장 널리 쓰이는 구현은 논문 저자가 직접 만든 leidenalg 패키지로, 그래프 라이브러리 igraph 위에서 동작한다. 설치는 pip 한 줄이면 된다.

```
pip install leidenalg igraph
```

모듈러리티를 최대화하는 기본 사용법은 다음과 같다. 예제의 Zachary는 igraph에 내장된 유명한 테스트 그래프다.

```
import igraph as ig
import leidenalg as la

G = ig.Graph.Famous('Zachary')
partition = la.find_partition(G, la.ModularityVertexPartition)
print(partition)
```

클러스터 크기를 직접 조절하려면 CPM 계열 파티션에 resolution_parameter를 넘긴다. 값이 클수록 더 잘게 쪼갠 커뮤니티가 나온다.

```
partition = la.find_partition(
 G, la.CPMVertexPartition, resolution_parameter=0.05)
print(len(partition))
```

igraph에 내장된 community_leiden 함수로도 같은 일을 할 수 있다. python-igraph 문서에 따르면 이 함수의 기본 목적 함수는 CPM이고, 기본 resolution_parameter 값은 1.0이다.

## 목적 함수 고르기: CPM과 모듈러리티

Leiden은 무엇을 좋은 분할로 볼지 정하는 목적 함수를 골라 쓸 수 있고, 이 선택이 결과 클러스터의 개수와 크기를 크게 바꾼다. leidenalg 문서 기준 대표적인 세 가지는 다음과 같다.

| 목적 함수 | leidenalg 클래스 | 특징 |
| --- | --- | --- |
| CPM | CPMVertexPartition | 해상도 한계 없음, resolution_parameter로 크기 조절 |
| 모듈러리티 | ModularityVertexPartition | 익숙하지만 해상도 한계 존재 |
| RBConfiguration | RBConfigurationVertexPartition | Reichardt·Bornholdt 모델, 해상도 조절 가능 |

igraph와 leidenalg 문서는 모듈러리티에 '해상도 한계(resolution-limit)'가 있다고 설명한다. 그래프가 커지면 모듈러리티가 작은 커뮤니티들을 실제보다 큰 덩어리로 묶어 버리는 성질이다. CPM은 이 한계가 없어서 resolution_parameter만 조절하면 원하는 촘촘함으로 커뮤니티를 얻을 수 있다. leidenalg는 이 밖에도 Significance, Surprise 같은 목적 함수를 제공한다.

## 어디에 쓰고, 언제 고르나

Leiden은 커뮤니티 탐지가 필요한 곳이면 어디서든 Louvain을 대체할 후보다. 대표적으로 단일세포 유전체 분석 도구 scanpy가 세포를 유형별로 묶을 때 Leiden을 쓴다. scanpy 공식 문서 기준 sc.tl.leiden 함수의 기본 resolution 값은 1.0이고, 값을 키우면 더 잘게 나뉜 클러스터가 나온다. 소셜 그래프의 커뮤니티 분석, 추천 시스템의 사용자·아이템 군집화, 지식 그래프 정리에도 같은 알고리즘을 쓴다.

선택 기준은 단순하다. 이미 Louvain을 쓰는데 커뮤니티가 이따금 이상하게 갈라진다면 Leiden으로 갈아타는 편이 낫다. 결과의 연결성이 보장되고, 논문 기준으로 속도도 손해 보지 않기 때문이다. 처음부터 커뮤니티 탐지를 붙이는 프로젝트라면 leidenalg나 igraph의 Leiden 구현을 기본값으로 두고 목적 함수와 해상도만 데이터에 맞춰 조정하면 된다. 더 자세한 배경은 [Scientific Reports에 실린 원 논문](https://www.nature.com/articles/s41598-019-41695-z)과 [leidenalg 공식 저장소](https://github.com/vtraag/leidenalg)에서 확인할 수 있다.

## 관련 글

- [CS 학위는 죽지 않았다, 끊긴 건 신입 채용 통로다](https://trendbrief.news/articles/cs-%ED%95%99%EC%9C%84%EB%8A%94-%EC%A3%BD%EC%A7%80-%EC%95%8A%EC%95%98%EB%8B%A4-%EB%81%8A%EA%B8%B4-%EA%B1%B4-%EC%8B%A0%EC%9E%85-%EC%B1%84%EC%9A%A9-%ED%86%B5%EB%A1%9C%EB%8B%A4.md)
- [Papermake: 콘텐츠 주소로 관리하는 Typst PDF 렌더링 레지스트리](https://trendbrief.news/articles/papermake-%EC%BD%98%ED%85%90%EC%B8%A0-%EC%A3%BC%EC%86%8C%EB%A1%9C-%EA%B4%80%EB%A6%AC%ED%95%98%EB%8A%94-typst-pdf-%EB%A0%8C%EB%8D%94%EB%A7%81-%EB%A0%88%EC%A7%80%EC%8A%A4%ED%8A%B8%EB%A6%AC.md)
- [Article 구조화 데이터로 저자·발행일·이미지 마크업하기](https://trendbrief.news/articles/article-%EA%B5%AC%EC%A1%B0%ED%99%94-%EB%8D%B0%EC%9D%B4%ED%84%B0%EB%A1%9C-%EC%A0%80%EC%9E%90-%EB%B0%9C%ED%96%89%EC%9D%BC-%EC%9D%B4%EB%AF%B8%EC%A7%80-%EB%A7%88%ED%81%AC%EC%97%85%ED%95%98%EA%B8%B0.md)
- [MinIO 유지보수 종료 이후, S3 호환 스토리지 다시 고르기](https://trendbrief.news/articles/minio-%EC%9C%A0%EC%A7%80%EB%B3%B4%EC%88%98-%EC%A2%85%EB%A3%8C-%EC%9D%B4%ED%9B%84-s3-%ED%98%B8%ED%99%98-%EC%8A%A4%ED%86%A0%EB%A6%AC%EC%A7%80-%EB%8B%A4%EC%8B%9C-%EA%B3%A0%EB%A5%B4%EA%B8%B0.md)
- [Harmonize로 Swift 아키텍처 규칙을 유닛 테스트로 강제하기](https://trendbrief.news/articles/harmonize%EB%A1%9C-swift-%EC%95%84%ED%82%A4%ED%85%8D%EC%B2%98-%EA%B7%9C%EC%B9%99%EC%9D%84-%EC%9C%A0%EB%8B%9B-%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%A1%9C-%EA%B0%95%EC%A0%9C%ED%95%98%EA%B8%B0.md)