[[Clustering algorithm]] Leiden 알고리즘은 네트워크(그래프)에서 커뮤니티(클러스터)를 탐지하기 위한 대표적인 방법으로, Louvain 알고리즘의 한계를 개선하여 “모듈성(Modularity)” 또는 “커뮤니티 품질 함수”를 최적화하면서도 각 커뮤니티가 **연결성(connectedness)** 을 보장하도록 설계되었습니다. ## 1. 주요 개념 - **모듈성(Modularity)** 그래프 내에서 커뮤니티 내부의 엣지 밀도가 기대치보다 얼마나 높은지 측정하는 지표 - **품질 함수(Quality Function)** 모듈성뿐 아니라 Constant Potts Model(CPM) 등 다양한 함수를 사용할 수 있으며, 해상도 파라미터(resolution)를 통해 커뮤니티 크기를 조정 가능 - **잘 연결된 커뮤니티(Well-connectedness)** Louvain은 때로 내부가 분리된 서브그래프로 나뉘어도 하나의 커뮤니티로 묶이지만, Leiden은 최소 연결 조건을 보장 --- ## 2. 알고리즘 단계 1. **Local Moving 단계** - 초기에는 각 노드가 자기 자신만으로 하나의 커뮤니티를 이룸 - 노드를 임의 순서로 순회하며, 주변 커뮤니티에 소속을 옮겨가며 품질 함수 증가 방향으로 이동 - 더 이상 이동이 없을 때까지 반복 2. **Refinement 단계** - Louvain과 달리, 이 단계에서 각 커뮤니티를 내부적으로 더 작은 하위클러스터로 분할하여 **잘 연결된 서브커뮤니티**를 식별 - “잘 연결되지 않은” 노드 집합을 분리해내고, 커뮤니티 내부 연결성을 강화 3. **Aggregation 단계** - 정제된 커뮤니티를 하나의 “슈퍼노드”로 합쳐 새로운 축소된 그래프 생성 - 엣지 가중치는 원래 노드 간 엣지 가중치 합으로 설정 4. **반복** - 축소된 그래프에서 다시 Local Moving → Refinement → Aggregation 과정을 수행 - 품질 함수 개선이 멈출 때까지 반복 --- ## 3. Pseudocode ```text Leiden(graph, quality_function, resolution): # 초기: 각각의 노드를 독립된 커뮤니티로 partition = { node: node for node in graph.nodes } improved = true while improved: # 1. Local Moving partition = local_moving(graph, partition, quality_function, resolution) # 2. Refinement refined = refine_partition(graph, partition) # 3. Aggregation new_graph = aggregate_graph(graph, refined) # 기준: 축소 후 그래프에서 품질 향상이 더 있는지 검사 improved = (quality_function(new_graph, refined, resolution) > quality_function(graph, partition, resolution)) graph, partition = new_graph, refined return partition ``` - **local_moving**: 각 노드를 살펴보며 소속 커뮤니티 변경 시 품질 함수 이득이 있는지 확인 - **refine_partition**: 커뮤니티 내 연결성 검사 및 재분할 - **aggregate_graph**: 커뮤니티 단위로 노드 합병 --- ## 4. 장단점 및 활용 사례 |구분|장점|단점| |---|---|---| |성능|Louvain 대비 더 빠르고, 큰 그래프에서도 확장성 좋음|품질 함수 평가 비용이 커질 수 있어 매우 큰 그래프는 다소 느려질 수 있음| |품질|커뮤니티 내부 연결성 보장 → 더 일관된 클러스터링 결과|해상도 파라미터 설정에 민감 → 과도한 분할 또는 과소 분할 가능| |구현 난이도|오픈소스 패키지(예: Python의 `leidenalg`, R의 `leiden`)로 손쉽게 사용 가능|내부 세부 단계(Refinement 등)가 복잡하여 직접 구현 시 디버깅 어려움| |활용 사례|- 단일 세포 RNA-seq 데이터에서 세포 간 유사도 네트워크 클러스터링- 소셜 네트워크 커뮤니티 탐지- 웹 페이지 링크 구조 분석 등|| --- ## 5. 실제 사용 예시 (Python, `leidenalg`) ```python import igraph as ig import leidenalg # 그래프 로드 또는 생성 g = ig.Graph.Read_Ncol('edge_list.txt', directed=False) # 커뮤니티 탐지 partition = leidenalg.find_partition( g, leidenalg.RBConfigurationVertexPartition, resolution_parameter=1.0 ) # 결과: 각 노드의 커뮤니티 레이블 labels = partition.membership ``` - `RBConfigurationVertexPartition`은 모듈성 기반, 다른 파티셔닝 클래스도 선택 가능 - `resolution_parameter` 값을 조절해 커뮤니티 크기 변경 --- Leiden 알고리즘은 특히 **세포 간 유사도 네트워크**를 클러스터링할 때 널리 쓰이며, Louvain보다 안정적이고 계산 효율이 뛰어나 많은 `scanpy`, `Seurat` 등 도구의 백엔드로 채택되고 있습니다.