Leiden 알고리즘 — Louvain이 남긴 '끊어진 모듈'을 정제 한 칸으로 막는 법

▶ 동영상 개요 — Leiden 알고리즘 — Louvain이 남긴 '끊어진 모듈'을 정제 한 칸으로 막는 법

6분 42초 — Leiden이 Louvain의 '옮기기→뭉치기' 사이에 끼워 넣은 '정제' 한 단계 — 무리 안에서 함수를 다시 혼자로 되돌린 뒤 '충분히 잘 연결됐나'라는 문… — NotebookLM 동영상 개요로 생성

🎧 오디오 개요 — Leiden 알고리즘 — Louvain이 남긴 '끊어진 모듈'을 정제 한 칸으로 막는 법

23분 32초 — Leiden이 Louvain의 '옮기기→뭉치기' 사이에 끼워 넣은 '정제' 한 단계 — 무리 안에서 함수를 다시 혼자로 되돌린 뒤 '충분히 잘 연결됐나'라는 문…. 화면은 이 글의 인포그래픽 한 장 고정 — NotebookLM 오디오 개요로 생성

어제 코드 그래프 도구의 속을 들여다보다 Louvain이라는 2008년생 알고리즘을 따라가 봤다. 함수 수천 개를 사람 손 없이 "인증", "결제" 같은 모듈로 갈라 주는 커뮤니티 탐지(community detection, 네트워크에서 서로 촘촘히 연결된 무리를 찾아내는 기법) 알고리즘이었다. 그런데 정작 코드 지도 도구 graphify의 소스를 보면, 커뮤니티 탐지의 1순위는 Louvain이 아니다. "Leiden이 깔려 있으면 Leiden을 쓰고, 없을 때만 Louvain으로 내려간다"는 식으로 짜여 있다. 멀쩡히 잘 도는 표준 알고리즘을 두고, 왜 굳이 다른 걸 먼저 세워 둘까.

그 1순위가 Leiden(레이던)이다. 2019년 네덜란드 레이던 대학(Leiden University)의 트라흐(Vincent Traag) 팀이 "From Louvain to Leiden: guaranteeing well-connected communities"라는 논문으로 발표했고(Scientific Reports 게재), 역시 대학 이름을 그대로 알고리즘 이름으로 썼다. 제목이 이미 모든 걸 말한다 — "Louvain에서 Leiden으로, 잘 연결된 커뮤니티를 보장하기". Louvain이 열어 둔 한 가지 구멍을 메우려고 나온 직계 후계자라는 뜻이다. 단일 세포 유전체 분석 도구(scanpy), 그래프 라이브러리(igraph) 같은 현역 도구들이 기본 커뮤니티 탐지를 Leiden으로 갈아탄 것도 같은 이유다. 그 구멍이 무엇이고, Leiden이 그걸 어떻게 막는지가 이 글의 전부다.

Louvain이 남긴 구멍 — '같은 모듈인데 서로 안 부르는 함수들'

Louvain은 모듈성(modularity)이라는 점수 하나 — "이 무리가 우연보다 얼마나 더 촘촘히 뭉쳐 있나"를 재는 숫자 — 를 탐욕적으로(greedy, 매 순간 당장 가장 이득인 선택을 집는 방식) 끌어올린다. 함수를 이웃 무리로 옮겨 보고 점수가 오르면 옮기는 걸 반복한다. 빠르고 단순한데, 바로 그 단순함이 고약한 부작용을 낳는다. Louvain은 함수 하나하나의 이동만 보지, 그 이동이 원래 무리에 무슨 일을 저지르는지는 보지 않는다.

문제가 되는 건 다리 역할을 하는 함수다. 어떤 무리가 두 덩어리로 이뤄져 있고, 그 둘을 이어 주는 함수가 딱 하나뿐이라고 하자. 이 다리 함수를 옆의 더 큰 무리로 옮기면 모듈성 점수가 오를 수 있다. Louvain은 점수만 보고 덥석 옮긴다. 그러면 남은 무리는 다리가 끊겨 두 조각으로 쪼개지는데, Louvain은 이걸 알아채지 못한 채 여전히 "한 모듈"로 기록한다.

다이어그램 설명. Louvain이 "내부가 끊어진 모듈"을 만드는 과정을 한 줄로 늘어놓은 것이다. 시작은 다리 함수 하나로 간신히 이어진 무리이고, 그 다리를 옆 무리로 옮기는 게 점수상 이득이라, Louvain은 원래 무리가 두 조각으로 갈라지는 걸 보지 못한 채 이동을 실행한다. 끝 칸이 핵심이다 — 결과물에는 서로 호출 한 번 안 하는 함수들이 "같은 모듈"이라는 딱지를 달고 들어 있다. 코드 지도에서 이건 단순한 품질 저하가 아니라 거짓말이다. "이 함수들은 한 기능 단위"라고 말해 놓고 실제로는 남남이니, 그 지도를 믿고 리팩터링하거나 코드를 탐색하는 쪽이 길을 잃는다. 트라흐 팀이 실제 네트워크들을 조사해 보니, Louvain이 만든 무리 중 최대 25%가 엉성하게 연결돼 있었고 최대 16%는 아예 내부가 끊어져 있었다 — 드문 예외가 아니라 구조적으로 반복되는 결함이었다.

Leiden의 발상 — 옮기기와 뭉치기 사이에 '정제' 한 칸

Leiden의 해법은 놀랄 만큼 외과적이다. Louvain의 뼈대("옮기고 → 뭉치고"의 반복)를 그대로 두되, 그 사이에 '정제(refinement)'라는 단계를 하나 끼워 넣는다. 두 단계짜리 알고리즘이 세 단계가 된다. 끼워 넣은 자리가 왜 하필 "옮긴 다음, 뭉치기 전"인지가 Leiden의 전부라 해도 좋다 — 끊어진 무리가 노드 하나로 압축돼 굳어 버리기 직전에 붙잡아 쪼개는 것이다.

다이어그램 설명. Leiden의 세 단계가 도는 순환이다. 첫 단계인 지역 이동은 Louvain과 똑같이 모듈성이 오르는 쪽으로 함수를 옮긴다 — 그래서 이 단계가 끝나면 앞 절의 "끊어진 무리"가 섞여 있을 수 있다. 이어지는 정제 단계가 Louvain에는 아예 없던 칸이고, 각 무리를 다시 들여다보며 "진짜로 잘 연결된 조각"만 추려 낸다. 그렇게 걸러 낸 조각을 마지막 뭉치기 단계에서 노드 하나로 압축한다. 순서가 결정적이다 — 정제가 압축보다 먼저 오므로, 끊어진 무리가 "되돌릴 수 없는 노드 하나"로 굳기 전에 쪼개진다. Louvain은 끊어진 무리를 통째로 압축해 버린 뒤라 되돌릴 방법이 없었다. Leiden은 그 사고가 일어날 자리에 검문소 하나를 세운 셈이다.

정제가 실제로 하는 일 — 무리 안에서 다시 혼자부터

정제 단계의 동작은 Louvain의 지역 이동을 작은 상자 안에서 한 번 더 돌리는 것에 가깝다. 다만 규칙 두 개가 결정적으로 다르다.

다이어그램 설명. 정제가 무리 하나를 다루는 방식이다. 먼저 그 무리에 속한 함수를 전부 다시 혼자짜리로 되돌린 뒤, 함수마다 "이웃과 충분히 잘 연결돼 있는가"를 따져 조건을 통과한 것만 같은 하위 조각으로 다시 뭉친다. 통과하지 못하면 억지로 붙이지 않고 혼자 남긴다. 여기서 규칙 두 개가 Louvain과 갈린다. 첫째, 뭉치기는 원래 무리의 경계 안에서만 일어난다 — 정제는 지역 이동이 그어 둔 큰 그림을 넘어 함수를 딴 데로 보내지 않고, 그 안을 더 정직하게 쪼갤 뿐이다. 둘째, 뭉칠지 말지를 탐욕적으로 결정하지 않는다. 모듈성이 오르기만 하면 무조건 붙이는 게 아니라, 점수가 많이 오르는 쪽일수록 더 높은 확률로 붙이는 식의 무작위 선택을 쓴다(그 무작위 정도를 조절하는 손잡이가 θ 파라미터다). 이 무작위성이 왜 중요한가 — 탐욕적으로만 가면 늘 똑같은 국소 최적(local optimum, 전체 최적이 아니라 근처에서만 가장 좋은 지점)에 갇히는데, 확률적으로 여러 갈래를 조금씩 열어 두면 더 나은 분할을 찾아낼 여지가 생긴다. 함정은 이 "충분히 잘 연결됐나"라는 기준에 있다 — 이게 단순한 휴리스틱이 아니라, 다음 절에서 볼 수학적 보장의 출발점이다.

왜 끊어진 무리가 아예 '불가능'해지나

정제의 "충분히 잘 연결됐나"는 느낌이 아니라 부등식이다. 어떤 함수(또는 조각)를 한 하위 무리에 넣으려면, 그 함수가 무리의 나머지와 일정 문턱 이상으로 연결돼 있어야 한다 — 바꿔 말해, 나중에 그 함수를 도로 빼더라도 남은 무리가 끊어지지 않을 만큼은 이어져 있어야 통과시킨다. 다리 하나로 간신히 매달린 조각은 이 문턱을 못 넘으니 애초에 한 무리로 묶이지 않는다. 그래서 정제를 거친 무리는 정의상 내부가 연결돼 있다. Louvain에서 최대 16%씩 나오던 "내부가 끊어진 모듈"이 Leiden에서는 확률이 낮은 게 아니라 원천적으로 생길 수 없게 된다. 논문이 제목에 "guaranteeing(보장한다)"을 박은 게 과장이 아니다.

마지막 한 수가 영리하다. 뭉치기 단계는 정제가 걸러 낸 조각을 노드로 압축하지만, 압축된 그래프의 출발 분할은 정제 이전의 원래 무리를 그대로 쓴다. 말이 꼬여 보이니 풀어 쓰면 이렇다 — 지역 이동이 그린 "큰 그림"(이 함수들은 한 모듈)은 유지하되, 그 안을 "잘 연결된 작은 조각들"로 잘게 나눠 두는 것이다. 그래서 다음 바퀴에서 그 조각들은 처음부터 한 무리에 모여 출발하면서도, 각자는 독립된 노드라 필요하면 서로 갈라설 수도 있다. 큰 구조를 보존하면서도 내부를 언제든 재조정할 여지를 남기는, 이 "보존과 유연성의 동시 달성"이 Leiden이 Louvain보다 더 나은 분할로 수렴하는 이유다.

이 과정을 반복하면 또 하나가 따라온다. Leiden은 바퀴를 돌릴수록 모든 무리가 두 성질로 수렴한다 — 무리들끼리는 서로 넉넉히 떨어져 있고(잘 분리됨), 무리 안쪽은 끊긴 데 없이 이어져 있다(잘 연결됨). Louvain은 바퀴를 더 돌려도 끊어진 무리가 오히려 늘어날 수 있었는데, Leiden은 반대로 돌릴수록 품질이 단조롭게 좋아진다.

덤으로 빨라졌다 — 바뀐 자리만 다시 본다

정제 단계를 하나 더 얹었으니 느려졌을 것 같지만, Leiden은 오히려 Louvain보다 빠르다. 비결은 지역 이동을 "모든 함수를 매번 다시 훑는" 방식에서 바뀐 자리만 다시 보는 방식으로 바꾼 데 있다.

import igraph as ig
import leidenalg as la

# 1단: 함수 호출 그래프를 만든다 (노드=함수, 엣지=호출 관계)
#      graphify 같은 도구는 이 그래프를 코드 파싱으로 뽑아낸다
G = ig.Graph.TupleList([
    ("login", "verify_token"),
    ("verify_token", "issue_session"),
    # ... 실제로는 수천 개의 함수와 호출 엣지가 쌓인다
], directed=False)

# 2단: Leiden으로 모듈을 찾는다 — 끊어진 무리 없이, 결정적 재현을 위해 seed 고정
#      objective_function을 modularity/CPM 중에 고를 수 있다
partition = la.find_partition(
    G, la.ModularityVertexPartition, seed=42
)

# 3단: 각 무리를 함수 이름 목록으로 확인한다 (이름 붙이기는 다음 단계의 몫)
for i, community in enumerate(partition):
    names = [G.vs[v]["name"] for v in community]
    print(f"모듈 {i}: {names}")

코드 설명. 호출 그래프 하나를 넣으면 Leiden이 "끊어진 데 없는 무리들"을 돌려준다. Louvain을 부르던 세 줄과 겉모습은 거의 같아서, 코드 도구가 둘을 바꿔 끼우기 쉬운 것도 이 때문이다. 눈여겨볼 건 둘째 단의 seed=42다 — 정제 단계가 무작위성을 쓰기 때문에, 씨앗값을 고정해야 같은 입력에서 같은 결과가 재현된다. 어제 본 Louvain이 "대체로 결정적"이었다면 Leiden은 "씨앗을 고정하면 결정적"인 쪽이다. 코드 지도는 돌릴 때마다 모듈 경계가 출렁이면 곤란하니, 이 씨앗 고정이 실무에서 중요하다. 또 하나, objective_function을 모듈성 대신 CPM(Constant Potts Model)으로 고르면 어제 Louvain에서 봤던 해상도 한계(작은 무리가 큰 덩어리에 삼켜지는 현상)까지 비켜 갈 수 있다 — Leiden은 끊어진 무리뿐 아니라 이 문제에도 더 나은 선택지를 함께 쥐여 준다.

속도 이야기로 돌아오면, 핵심은 큐(대기열) 하나다. 함수 하나를 다른 무리로 옮기면, 그 변화에 영향받는 건 그 함수의 이웃들뿐이다. 멀리 떨어진 함수들의 최적 소속은 그대로다. 그래서 Leiden은 옮긴 함수의 이웃만 "다시 검토할 목록"에 넣고, 아무 변화도 없는 나머지는 건너뛴다. Louvain이 매 바퀴 전체 함수를 다시 훑던 걸, Leiden은 흔들린 자리 주변만 다시 보는 것으로 줄였다. 그 결과 논문의 실측에서 Leiden은 Louvain보다 빠르면서 동시에 더 나은 — 그리고 끊어지지 않은 — 분할을 내놨다. 보통은 품질과 속도가 맞바꿈 관계인데, 여기서는 둘을 같이 가져갔다.

graphify가 Leiden을 1순위로 세우는 자리

이제 처음 질문으로 돌아온다. 낯선 저장소를 처음 여는 코딩 에이전트에게, graphify는 "이 코드베이스가 실제로 어떤 기능 단위로 뭉쳐 있나"를 사람이 붙인 폴더 라벨 없이 보여 주는 지도를 그린다. 그 지도의 뼈대가 바로 커뮤니티 탐지다. 함수 호출 그래프를 Leiden에 통과시키면 인증에 얽힌 함수끼리·결제에 얽힌 함수끼리 알아서 갈라지고, 그다음 단계에서 각 무리에 "인증 모듈" 같은 이름을 붙인다.

여기서 Louvain의 결함이 단순한 학술적 흠이 아니라 실질적 문제가 된다. 지도의 한 블록이 "이 함수들은 한 모듈"이라고 말하는데 실제로는 서로 호출조차 안 하는 두 조각이라면, 그 지도를 믿고 코드를 탐색하는 에이전트는 엉뚱한 맥락을 한 덩어리로 집어넣는다. 코드 지도의 가치는 정확히 "진짜 구조를 비춘다"는 데 있는데, 끊어진 모듈은 그 신뢰를 깨뜨린다. 그래서 graphify는 가능하면 Leiden을 먼저 세우고, 환경에 Leiden이 없을 때만 Louvain으로 내려가는 우아한 성능 저하(graceful degradation)를 택한다 — 최선을 기본으로 두되, 최선이 없는 환경에서도 지도는 그려야 하니 차선을 받침대로 깔아 두는 것이다.

정리 — 한 칸을 '어디에' 끼우느냐의 문제

Leiden을 끝까지 따라가 보니, 그 개선은 완전히 새로운 알고리즘이 아니었다. Louvain이라는 검증된 뼈대를 거의 그대로 두고, "옮긴 다음, 뭉치기 전"이라는 딱 한 자리에 정제라는 칸을 끼워 넣은 것이 전부였다. 그 한 칸이 끊어진 무리가 되돌릴 수 없게 굳기 직전에 붙잡아 쪼개고, "잘 연결됐나"라는 수학적 문턱으로 내부 연결을 보장하며, 바뀐 자리만 다시 보는 큐로 속도까지 끌어올렸다. 작은 수술 하나가 품질과 속도를 동시에 가져간 보기 드문 사례다.

코드베이스를 다룰 때 가져갈 교훈은 이것이다 — 알고리즘이 그어 준 모듈 경계를 받아 들 때, "이 묶음이 정말 내부적으로 이어져 있나"를 한 번은 의심하는 게 좋다. 사람이 믿어 온 폴더 구조가 실제 결합도와 어긋나 있는 것처럼, 자동으로 그어진 경계도 그 경계가 거짓말을 하고 있지는 않은지 — 같은 모듈이라면서 정작 서로를 부르지 않는 함수가 섞여 있지는 않은지 — 를 보장해 주는 도구를 고르는 것이, 지도를 믿을 수 있게 만드는 출발점이다.

---

참고한 공개 자료:

• Leiden 원 논문 — Traag, Waltman, van Eck, "From Louvain to Leiden: guaranteeing well-connected communities" (2019, Scientific Reports) — nature.com/articles/s41598-019-41695-z (프리프린트 arxiv.org/pdf/1810.08473)
• Louvain 원 논문 — Blondel, Guillaume, Lambiotte, Lefebvre, "Fast unfolding of communities in large networks" (2008) — arxiv.org/abs/0803.0476
• Leiden 알고리즘 개요 — Wikipedia: Leiden algorithm
• 파이썬 구현 — leidenalg 문서, igraph cluster_leiden 레퍼런스

---

이 글은 생성형 AI의 도움을 받아 작성되었습니다. 원본 자료를 기반으로 AI가 초안을 생성하고, 작성자가 검토·편집하였습니다.