네트워크 데이터 분석을 위한 링크 그래프 기반 중첩 커뮤니티 탐색 방안

Abstract

현실 세계의 현상 중 다수는 네트워크 데이터로 모델링될 수 있다. 특히, 최근에는 소셜 네트워크 서비스(SNS)의 발달로 다양한 형태의 소셜 네트워크가 새로이 등장하고 있다. 이러한 네트워크 데이터에서 서로 깊은 관계를 갖는 커뮤니티(community)들을 찾아내는 커뮤니티 탐색 기술은 중요한 분석 도구의 하나로 사용된다. 커뮤니티는 노드 간의 관계의 집합으로 정의될 수 있다. 본 논문에서는 노드 간의 관계를 나타내는 엣지가 다수의 커뮤니티에 속할 수 있다는 점에 착안하여 링크 그래프(link-graph)를 바탕으로 seed 확장 기법을이용하여 엣지 중심적이며 각 엣지가 다수의 커뮤니티에 속하는 것을 허용하는 중첩 커뮤니티 탐색 방안을 제안한다. 이를 바탕으로 기존 중첩 커뮤니티 탐색 방안이 커뮤니티 간의 얕은 중첩만을 허용하는 문제를 해결하고 더 정확한 중첩 커뮤니티 탐색을 달성할 수 있다. 또한, 실험을 통해 제안하는 방법이 중첩 커뮤니티 탐색에 효과적임을 증명하였다. A number of phenomena in the real world can be modeled as network data. In particular, various types of social networks are emerging recently thanks to the rapid growth of social network services (SNS). Community detection is one of the most important analytic tools, which finds community structures that are densely connected set of nodes. A community can be defined as a set of relationships between nodes. In this paper, we focus on the fact that an edge that represents relationship between nodes can be part of multiple communities. Using link-graph, we adopt seed expansion method to achieve edge-centric overlapping community detection that allows an edge to be in multiple communities. With our proposed method, we can remedy the problem that some of existing overlapping community detection method only allows swallow overlapping and thus achieve more accurate overlapping community detection. We prove that the proposed method is efficient for searching overlapping communities from real world networks via a set of experiments.