EdMot: 모티프 인식 기반 커뮤니티 탐지 위한 엣지 강화 접근법

네트워크 커뮤니티 탐지(community detection)는 네트워크 분석 분야에서 주목받는 핫 이슈이다. 많은 커뮤니티 탐지 기법이 제안되었지만, 대부분은 노드와 엣지 수준의 저차원 구조만 고려하기 때문에, 작은 밀집 서브그래프 패턴(예: 모티프) 수준의 고차원 특성을 포착하지 못한다. 최근에는 고차원 구조를 고려하는 일부 방법들이 개발되었지만, 대부분 모티프 기반 하이퍼그래프(hypergraph)에 기반하며, 이 하이퍼그래프가 연결된 그래프(connected graph)라고 가정한다. 그러나 실제 네트워크에서는 이러한 가정이 항상 성립하지 않으며, 하이퍼그래프가 분리된 상태가 될 수 있다. 즉, 원래의 네트워크가 연결되어 있어도 하이퍼그래프는 수많은 연결 성분과 고립된 노드로 구성될 수 있다. 따라서 기존의 고차원 방법들은 이러한 분리 문제로 인해 심각한 성능 저하를 겪게 되며, 하이퍼그래프 내에서 연결되지 않은 노드는 동일한 커뮤니티에 속해 있어도 그룹화될 수 없게 된다. 위의 분리 문제를 해결하기 위해, 본 연구에서는 모티프 인식 기반 커뮤니티 탐지에 대한 엣지 강화 기법(Edge enhancement approach for Motif-aware community detection, EdMot)을 제안한다. 주요 아이디어는 다음과 같다. 먼저, 모티프 기반 하이퍼그래프를 구축하고, 하이퍼그래프 내에서 가장 큰 K개의 연결 성분을 모듈(module)로 분할한다. 이후 각 모듈 내부의 연결 구조를 강화하기 위해 엣지 집합을 구성하여 각 모듈에서 클리크(clique)를 형성한다. 이 새로운 엣지 집합을 바탕으로 원래 네트워크의 연결 구조를 보강하여 재연결된 네트워크(rewired network)를 생성함으로써, 모티프 기반 고차원 구조를 효과적으로 활용하고 하이퍼그래프의 분리 문제를 잘 해결할 수 있다. 마지막으로, 재연결된 네트워크를 기반으로 커뮤니티 구조를 분할하여 고차원 커뮤니티 구조를 도출한다.