Modularity와 알고리즘 선택

Modularity: 커뮤니티 품질 측정

핵심 질문

"이 커뮤니티 분할이 얼마나 좋은가?"

Modularity 공식

직관적 의미:

Q 값	해석
Q < 0	커뮤니티 구조 없음
0 < Q < 0.3	약한 구조
0.3 < Q < 0.7	뚜렷한 구조
Q > 0.7	매우 강한 구조

예시

Louvain 알고리즘

동작 원리

Phase 1: Local Moving

Phase 2: Aggregation

GDS에서 Louvain

Label Propagation (LPA)

동작 원리

장단점

장점	단점
매우 빠름 O(E)	비결정적 (매번 다른 결과)
대규모 처리 가능	작은 커뮤니티 놓칠 수 있음
단순한 구현	수렴 보장 안 됨

GDS에서 LPA

알고리즘 선택 가이드

Connected Components

WCC (Weakly Connected Components)

방향을 무시하고 연결된 노드 그룹:

SCC (Strongly Connected Components)

양방향 도달 가능한 노드만:

Resolution 파라미터

Louvain의 resolution 파라미터로 커뮤니티 크기 조절:

resolution	효과
< 1.0	큰 커뮤니티 선호
= 1.0 (기본)	표준
> 1.0	작은 커뮤니티 선호