레이블 확산을 기반으로 한 커뮤니티 추출 알고리즘의 성능 분석

Abstract

커뮤니티 추출은 그래프 분석 분야에서 그래프 매칭 등과 더불어 활용도가 높은 기법 중에 하나이다. 커뮤니티 추출은 소비자 분석, 웹, 소셜 네트워크, 생물 정보학 등에서 광범위하게 활용되고 있다. 이에 따라, 최소 컷 방법, 계층적 클러스터링, 게르반-뉴먼 방법, 모듈 방식 최대화 등 그래프로부터 커뮤니티 를 찾는 많은 방법들이 들이 제안되었다. 레이블 확산[1]은 커뮤니티 추출 알고리즘 중에서도 널리 사용되고 있는 알고리즘 중에 하나이다. 레 이블확산은 다른 알고리즘들에 비해 적은 실행 시간을 필요로 하며, 그래프의 구조 외에 다른 정보를 필요로 하지 않는다는 특징을 갖고 있다. 본 논문에서는 레이블 확산 알고리즘을 분석한 뒤, 이를 구현하고 충분한 메모리 공간 위에서 여러 데 이터에 대해 실험하여 성능을 확인하였다.