그래프 간략화를 통한 커뮤니티 검출 성능 개선

Abstract

모바일 인터넷 환경의 발전으로 어느 곳에서나 인터넷 접속이 가능하게 되었다. 사용자들은 시간과 공간의 제약 없이 커뮤니케이션을 할 수 있게 되었으며, 커뮤니케이션의 요구에 의해서 Social Network Service (SNS)와 같은 서비스들이 모바일 서비스의 중심으로 자리 잡았다. 이러한 SNS 네트워크가 커짐에 따라서 social network의 정보들은 점점 더 많이 축적이 되어가고 있다. 기업들은 자신들의 제품과 서비스에 관심이 있는 커뮤니티를 발굴하려고 한다. 왜냐하면 개인 맞춤형 광고 혹은 마케팅을 위한 추천 서비스에 활용이 가능하기 때문이다. 많은 그래프 클러스터링 알고리즘이 제안되어 왔지만, 큰 규모의 네트워크에서 커뮤니티를 찾아내는 것은 여전히 큰 문제이다. 게다가 이전 연구는 낮은 정확도와 여러 가지 파라미터에 민감한 경향을 가지고 있다. 본 논문에서는 커뮤니티 검출에 있어서 좀 더 나은 성능을 위하여 그래프를 간략하게 하는 방법을 제안한다. 제안하는 방법은 커뮤니티 검출 시에 높은 정확도를 유지하고, 커뮤니티 검출 알고리즘의 다양한 파라미터에 민감하지 않은 간략한 그래프를 산출한다.