링크 그래프 기반의 노드 중심 확장 기법을 사용한 중첩 커뮤니티 추출 연구

Abstract

다양한 종류의 네트워크 형태의 데이터가 존재할 때, 해당 네트워크에 존재하는 커뮤니티들을 찾는 것은 중요하다. 네트워크는 노드와 엣지로 구성되고 네트워크에서 커뮤니티란 내부적으로는 강한 연결을 가지고 외부와는 약한 연결을 가지는 노드와 노드 간 엣지들의 집합이다. 예를 들어 소셜 네트워크에서는 사람들이 커뮤니케이션을 하면서 관계들이 이루어지고 커뮤니티들을 이루기 때문에, 커뮤니티는 관계들이 모여 이루어진다고 볼 수 있다. 또한 어떤 두 사람의 관계가 한 커뮤니티에 속하고 이 관계는 다른 커뮤니티에도 등장할 수 있으므로 관계들은 여러 커뮤니티에 동시에 속할 수 있다. 즉, 하나의 관계가 하나 이상의 커뮤니티에서 등장할 수 있다. 실제 네트워크 내에서도 존재하는 커뮤니티들은 겹쳐 있는 경우가 많다. 그러므로 관계의 최소 단위인 엣지를 대상으로 오버래핑 커뮤니티 추출 알고리즘을 사용하여 관계의 최대 단위인 커뮤니티를 찾는다. 본 논문에서는 링크 그래프를 사용하여 엣지가 오버래핑 커뮤니티의 대상이 되도록 하고 링크 그래프를 대상으로 씨드 확장 방법을 적용해 오버랩되는 커뮤니티를 효과적으로 찾는 방안을 제안한다. 실험에서는 기존 방안과 제안하는 방안을 비교하고 최적의 제안방안을 찾는다. 이를 위해, (1) 씨드 추출 방안 2가지(한 단계 인접 노드 제거, 두 단계 인접 노드 제거)의 정확도와 커버리지 비율을 비교해서 데이터의 특성별 효과적인 방법을 찾고 (2) 적절한 씨드 추출의 시점을 확인한다. 실험 결과, 기존 방안에 비해 제안하는 방안이 우수함을 확인했다. 제안하는 방안은 커뮤니티 내부적 연결과 외부적 연결이 비교적 약한 데이터에서는 한 단계 인접 노드 제거가 좋은 결과를 보였다. 커뮤니티 내부적 연결과 외부적 연결이 강한 데이터에서는 두 단계 인접 노드 제거가 좋은 결과를 보였다. 또한 모든 데이터에 대해서 오리지널 그래프를 대상으로 씨드를 추출하는 것이 좋은 퀄리티의 커뮤니티를 도출하였다.