Graph

그래프 연산이나 저장 구조를 최적화할 때 빠지지 않고 등장하는 자료구조가 CSR(Compressed Sparse Row)입니다. 1977년 예일 대학교가 발표한 Yale Sparse Matrix Package 보고서에서 처음 소개되어 Yale Format이라고도 불리는데, 희소 행렬(sparse matrix)을 효율적으로 저장하고 처리하기 위해 고안되었습니다. 희소 행렬이란 희소 행렬은 대부분의 원소가 0인 행렬을 말합니다. 과학 계산, 그래프 이론, 머신러닝 등 현대 컴퓨팅의 거의 전 영역에서 마주치게 되는데, 현실의 데이터를 행렬로 옮기면 십중팔구 이런 모양이 됩니다. SNS를 예로 들면, 사용자가 100만 명이라 해도 한 사람의 친구 수는 보통 500명 안팎입니다. 그런데 이것을 그대로 행렬로 표현하려면 1조(10^12) 크기, 그러니까 7.3PB에 달하는 행렬이 필요해집니다. 실제 정보량에 비해 저장 공간이 터무니없이 커지는 셈입니다. ...

이 글은 구글이 2017년 KDD에서 발표한 논문 Ego-Splitting Framework: from Non-Overlapping to Overlapping Clusters를 정리한 글입니다. 왜 비중첩 클러스터링만으로는 부족한가 현실의 네트워크에는 보통 중간 크기(대략 100명 안팎)의 커뮤니티가 다수 존재하고, 하나의 노드가 여러 커뮤니티에 동시에 걸쳐 있는 경우가 흔합니다. 그런데 기존의 비중첩(non-overlapping) 클러스터링 알고리즘들은 각 노드를 정확히 하나의 커뮤니티에만 배정하기 때문에, 이런 실제 네트워크 구조를 제대로 포착하지 못합니다. 물론 중첩(overlapping) 클러스터링을 시도하는 알고리즘들도 이미 여럿 있었지만, 대체로 지나치게 복잡하거나 유연성이 떨어졌고, 이론적인 보장도 부족했습니다. ...

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