에고-스플리팅 프레임워크: 겹치지 않는 클러스터에서 겹치는 클러스터로

우리는 복잡한 네트워크에서 클러스터를 탐지하기 위해 새로운 프레임워크인 Ego-Splitting을 제안한다. 이 프레임워크는 각 노드의 이웃 집합에 의해 유도되는 로컬 구조인 이고넷(ego-net, 즉 노드의 이웃에 의해 생성된 부분그래프)을 활용하여 겹치는 클러스터를 분리하는 방식을 취한다. Ego-Splitting은 이론적으로 입증 가능한 보장 조건을 갖추고 있으며, 매우 확장 가능하고 유연한 프레임워크로, 복잡한 겹치는 클러스터링 문제를 더 단순하고 다루기 쉬운 겹치지 않는(분할형) 문제로 전환한다. 본 연구에서는 수십십억 개의 엣지를 가진 그래프에서 커뮤니티 탐지 문제를 해결할 수 있으며, 기존의 이고넷 분석 기반 기법들을 능가하는 성능을 보인다.구체적으로, 본 프레임워크는 두 단계로 구성된다. 첫 번째 단계는 로컬 이고넷 분석 단계이며, 두 번째 단계는 글로벌 그래프 분할 단계이다. 로컬 단계에서는 먼저 분할 알고리즘을 사용하여 각 노드의 이고넷을 분할한다. 이후 계산된 클러스터 정보를 기반으로 각 노드를 그 노드가 속한 커뮤니티 내에서의 ‘개성 노드’(persona nodes)로 분리한다. 이후 글로벌 단계에서는 새로 생성된 그래프를 분할함으로써 원래 그래프에 대한 겹치는 클러스터링 결과를 도출한다.