Deterministic label propagation algorithm for community detection

Abstract

레이블 전파 알고리즘은 그 단순성과 훌륭한 성능으로 인하여 커뮤니티 식별 문제에서 대표적으로 사용되어지는 알고리즘이다. 그러나 이러한 레이블 전파 알고리즘은 알고리즘에 내재되어있는 임의성에 의하여 종종 지역 최적화 문제에 빠지거나 모든 레이블이 같은 값을 갖는 값을 도출한다. 더불어 작은 사이즈의 커뮤니티를 식별하기 위하여 알고리즘을 여러번 수행해야 하는 문제점이 존재한다. 이러한 문제를 해결하기 위하여 특정 평가값을 최적화 하는 방법의 알고리즘들이 제안되었다. 이 논문에서 우리는 특정 값에 최적화되어진 알고리즘이 아닌 레이블 전파 알고리즘의 임의성을 제거할 수 있도록 업데이트 규칙을 변경한 알고리즘을 제안한다. 핵심 아이디어는 다수결에 의하여 레이블이 결정되는 것이 아닌 가장 친한 사람을 따라가는 방식이다 이러한 알고리즘은 결정적이며 똑같은 방법을 여러번 수행시킬 필요가 없다. 게다가 이는 레이블 전파 알고리즘에서 발생하는 전체 노드가 같은 레이블을 갖는 문제 혹은 지역 최적화 문제를 해결한다. 더욱이, 이는 특정 평가값에서 발생되어지는 문제에 대하여 견고하며 작은 커뮤니티를 찾기 위하여 여러번 알고리즘을 수행할 필요가 없다. 우리는 실생활 네트워크와 임의 네트워크를 이용하여 다양한 환경에서 실험을 수행하였고 이 결과는 제안하는 알고리즘이 다른 레이블 전파 알고리즘 보다 우수하고 최신 알고리즘들과 유사한 성능을 냄을 확인할 수 있다.