링크 속성 기반 분류를 통한 커뮤니티 발견

김정선, 정수환, 임성수

http://doi.org/10.5626/JOK.2021.48.8.959

빠르고 복잡하게 진화하는 세상을 이해하기 위하여 데이터를 통해 지식을 발견하는 시도는 점차 다양화되고 있다. 개체들이 관계를 갖고 얽혀있는 데이터를 그래프로 모델링하고 분석하는 그래프 데이터 분석은 최신 기계학습 기법과 접목되면서 많은 관심을 끌고 있다. 본 논문에서는 그래프 커뮤니티 구조를 발견하기 위한 새로운 방법론을 제안한다. 커뮤니티 내부 및 외부에 존재하는 링크들이 다른 속성값을 갖도록 하는 유사도, 곡률 기반 속성들에 대해 분석하고, 이를 활용하여 커뮤니티 구조에 영향을 덜 끼치는 링크를 제거하여 더 희소한 그래프에서 더 향상된 커뮤니티 구조를 찾아내는 알고리즘을 설계 및 분석한다.