이번에 더 배울 것
포르투나토와 바르텔레미(Fortunato & Barthélemy, 2007)는 모듈러리티 최적화가 그래프 전체의 엣지 수 L과 무리 사이의 연결 정도에 따라 정해지는 어떤 크기보다 작은 무리를 구별하지 못할 수 있음을 보였습니다. 무리가 분명하게 정의된 경우에도 그렇습니다. 논문은 내부 엣지 수가 대략 √(2L) 이하인 무리가 더 작은 구조를 숨기고 있을 가능성이 가장 높다고 정리했습니다.
원인은 Q의 기대값 항에 있습니다. 두 무리 A와 B 사이에 무작위로 기대되는 엣지 수는 d_A×d_B÷2m입니다. 두 무리는 그대로인데 그래프의 나머지가 커져 m이 늘면 이 기대값이 1보다 작아질 수 있습니다. 그러면 실제로 있는 엣지 1개가 ‘기대보다 많은 연결’로 계산되어 두 무리를 합치는 쪽이 Q를 올립니다. 같은 두 무리라도 그래프의 다른 부분이 커질수록 합쳐지기 쉬워진다는 뜻입니다.
대응책으로는 해상도 γ를 높여 작은 무리를 드러내거나, 찾은 커뮤니티 안에서 다시 커뮤니티를 찾거나, Leiden 논문이 함께 다루는 CPM(Constant Potts Model)처럼 해상도 한계를 겪지 않는 품질 함수를 쓰는 방법이 있습니다. 어떤 크기가 맞는지는 결국 분석 목적이 정하므로, 커뮤니티 결과는 여러 해상도에서 비교해 보는 습관이 필요합니다.
작은 예제로 따라가기
삼각형 10개를 고리처럼 이어 붙인 그래프를 생각합니다. 각 삼각형은 내부 엣지 3개와 이웃 삼각형으로 가는 엣지 1개씩을 가져 m = 30+10 = 40이고, 삼각형 하나의 차수 합은 8입니다.
삼각형 하나씩을 커뮤니티로 두면 Q = 10×(3/40 − (8/80)²) = 10×(0.075 − 0.01) = 0.65입니다.
이웃한 삼각형을 두 개씩 묶으면 5개 무리가 각각 내부 엣지 7, 차수 합 16이라 Q = 5×(7/40 − (16/80)²) = 5×(0.175 − 0.04) = 0.675로 더 큽니다. 엣지 하나로만 이어진 두 삼각형이 Q로는 한 무리가 되는 편이 낫다고 판정됩니다.
삼각형 고리를 키워 보기
삼각형 수를 늘릴 때, ‘삼각형 하나씩’과 ‘두 개씩 묶기’ 중 어느 나눔의 Q가 더 커질지 먼저 예상하세요.
이웃한 두 삼각형 사이의 기대 엣지 수가 8×8÷48≈1.33으로 실제 1개보다 많아, 따로 두는 쪽이 낫습니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.