Community Detection
그래프 안에서 서로 밀접하게 연결된 노드들의 집합, 즉 커뮤니티를 찾아내는 문제를 Community Detection이라고 부릅니다. 일종의 클러스터링 문제로 볼 수 있는데, GraphRAG 같은 방법론이 지식 그래프를 다룰 수 있는 단위로 쪼개는 데 바로 이 기법을 사용합니다. 이 글에서는 Community Detection에서 가장 널리 쓰이는 지표인 Modularity가 어떤 발상에서 나왔는지, 그리고 이를 최적화하는 대표적인 알고리즘인 Louvain과 Leiden이 어떻게 다른지 살펴보겠습니다. Modularity: 커뮤니티가 잘 만들어졌는지 재는 법 커뮤니티를 하나 만들었다고 해봅시다. 이 커뮤니티가 “잘” 만들어졌다는 건 어떤 의미일까요? Community Detection에서 가장 널리 쓰이는 답은 Modularity라는 지표입니다. 직관은 단순합니다. 만약 그래프의 엣지들이 완전히 무작위로 연결되어 있었다면 이 커뮤니티 안에 몇 개의 엣지가 있었을지 계산해두고, 실제로 관찰된 엣지 수가 그 기댓값보다 얼마나 더 많은지를 재는 것입니다. 우연이라고 보기 힘들 정도로 연결이 조밀하다면, 그건 진짜 커뮤니티라고 볼 근거가 됩니다. ...