## 1. 배경: 커뮤니티 탐지(Community Detection) 대규모 네트워크(소셜 네트워크, 생물학 네트워크, 인용 네트워크 등)에서는 노드들이 서로 조밀하게 연결된 집단, 즉 **커뮤니티(community)**를 형성하는 경우가 많다. 이러한 커뮤니티 구조는 데이터의 의미를 해석하는 데 중요한 단서가 된다. 대표적인 방법 중 하나는 **모듈러리티(Modularity)** 기반 최적화이며, 이를 빠르게 근사하는 알고리즘으로 **Louvain 알고리즘**이 널리 사용되어 왔다. 하지만 2019년 Traag, Waltman, van Eck의 연구에 따르면 Louvain 알고리즘에는 구조적으로 심각한 문제가 존재한다. --- ## 2. Louvain 알고리즘의 근본적 문제 ### 2.1 Louvain 알고리즘의 개요 Louvain 알고리즘은 두 단계로 구성된다. 1. **Local moving 단계** 각 노드를 개별적으로 다른 커뮤니티로 이동시키면서 품질 함수(모듈러리티 또는 CPM)를 증가시키는 방향으로 최적화한다. 2. **Aggregation 단계** 탐지된 커뮤니티들을 하나의 노드로 묶어 새로운 축약 네트워크를 만든다. 이 과정을 품질 함수가 더 이상 증가하지 않을 때까지 반복한다. --- ### 2.2 핵심 문제: 내부적으로 끊어진 커뮤니티 Louvain 알고리즘은 다음과 같은 심각한 결함을 가진다. - 하나의 커뮤니티 내부가 **연결이 끊어진 상태**가 될 수 있다. - 더 나아가, 커뮤니티가 형식상 연결되어 있더라도 실제로는 **매우 약하게 연결된 구조**가 될 수 있다. - 알고리즘을 여러 번 반복(iteration)할수록 이 문제는 악화된다. 즉, Louvain은 "커뮤니티 간 분리"는 보장하지만, "커뮤니티 내부의 연결성"은 전혀 보장하지 않는다. --- ### 2.3 왜 이런 문제가 발생하는가? Louvain 알고리즘의 설계상 한계는 다음과 같다. - 개별 노드 단위 이동만 고려한다. - 특정 노드가 커뮤니티 내부에서 **브리지 역할**을 하던 경우, 이 노드가 이동하면 기존 커뮤니티는 둘로 나뉘게 된다. - 그러나 나머지 노드들이 여전히 "지역적으로 최적"인 상태라면, 알고리즘은 이를 고치지 않는다. - 이후 Aggregation 단계에서 끊어진 커뮤니티가 하나의 노드로 축약되면서, 다시 분할할 기회조차 사라진다. 결과적으로, Louvain은 **구조적으로 잘못된 커뮤니티**를 그대로 확정해버릴 수 있다. --- ## 3. Leiden Algorithm의 등장 이 문제를 해결하기 위해 제안된 알고리즘이 바로 **Leiden Algorithm**이다. Leiden 알고리즘은 기존 Louvain 알고리즘을 확장하되, 다음과 같은 목표를 가진다. - 커뮤니티가 반드시 내부적으로 연결되도록 보장 - 최적화 품질 개선 - 실행 속도 향상 --- ## 4. Leiden Algorithm의 구조 Leiden은 Louvain과 달리 **세 단계 구조**를 가진다. ### 4.1 1단계: Local Moving - 기본 구조는 Louvain과 동일 - 단, **Fast Local Move 기법**을 도입하여, 주변 구조가 바뀐 노드만 재검사함으로써 속도를 대폭 개선함 ### 4.2 2단계: Refinement (정제 단계) Leiden의 핵심이다. - 각 커뮤니티를 내부적으로 다시 검사하여 - 연결성이 약하거나, 분리 가능한 부분이 있는지를 분석 - 필요한 경우 커뮤니티를 **자동 분할** - 이 과정에서 무작위성(randomness)을 일부 도입하여 로컬 최적해(local optimum)에 빠지는 것을 방지 ### 4.3 3단계: Aggregation - 정제된 커뮤니티를 기반으로 축약 네트워크 생성 - 이후 다시 1단계로 돌아가 반복 --- ## 5. Leiden Algorithm의 이론적 보장 Leiden 알고리즘은 Louvain과 달리 명확한 이론적 보장을 제공한다. ### 5.1 매 반복 이후 보장 사항 모든 반복(iteration) 후 다음이 보장된다. 1. **γ-분리성 (γ-separation)** 서로 다른 커뮤니티는 합쳐질 수 없는 상태 2. **γ-연결성 (γ-connectivity)** 모든 커뮤니티는 내부적으로 연결됨 --- ### 5.2 안정 상태(stable iteration) 이후 보장 안정 상태란, 더 이상 노드 이동이 발생하지 않는 상태를 의미한다. 이때 다음 성질을 만족한다. 3. **노드 지역 최적성 (node optimality)** 어떤 노드도 이동하면 품질이 증가하지 않음 4. **부분집합 γ-밀도 (subpartition γ-density)** 커뮤니티 내부에 분리 가능한 느슨한 구조가 없음 --- ### 5.3 충분히 반복 수행 시 최종 보장 Leiden 알고리즘을 계속 실행하면 다음 상태로 수렴한다. 5. **Uniform γ-density** 어떤 방식으로 나누어도 내부 연결이 유지됨 6. **Subset optimality** 어떤 서브셋도 다른 커뮤니티로 이동하는 것이 이득이 되지 않음 이는 Louvain이 **절대** 제공할 수 없는 보장이다. --- ## 6. 실험 결과 ### 6.1 잘못된 커뮤니티 비율 실험 결과: - Louvain 알고리즘: - 최대 25%의 커뮤니티가 구조적으로 잘못됨 - 최대 16%가 내부적으로 완전히 끊어진 상태 - Leiden 알고리즘: - 모든 커뮤니티 연결 보장 - 반복할수록 잘못된 커뮤니티 비율 감소 - 충분히 반복하면 0% 도달 --- ### 6.2 성능 비교 (속도) - Leiden은 Louvain보다 다음과 같이 빠름: - 소형 네트워크: 약 2배 - 대형 네트워크: 최대 20~100배 이상 빠름 - 극단적인 경우 Louvain이 2일 걸릴 작업을 Leiden은 수 분 만에 완료 --- ### 6.3 품질 비교 - Leiden이 항상 모듈러리티/CPM 관점에서 더 높은 해를 발견 - Louvain은 몇 회 후 더 이상 개선되지 않음 - Leiden은 수백 회 반복에서도 품질 지속 개선 --- ## 7. 결론 Leiden 알고리즘은 다음 이유로 Louvain을 대체하는 표준 알고리즘이 되었다. - 커뮤니티 내부 연결성 보장 - 이론적으로 증명된 최적성 - 대규모 네트워크에서도 강력한 성능 - 실제 데이터에서도 높은 정확도 --- ## 8. 활용 예시 Leiden 알고리즘은 현재 다음 분야에서 표준 도구로 사용된다. - 단일 세포 RNA-seq 클러스터링 (Scanpy, Seurat 연동) - 소셜 네트워크 분석 - 인용 네트워크 및 토픽 모델링 - 단백질 상호작용 네트워크 분석 - 추천 시스템 [[Single cell analysis]]