마르코프 클러스터링을 이용한 영향력 최대화 알고리듬

Abstract

최근들어 소셜 네트워크 서비스(SNS)가 확산됨에 따라 소셜 네트워크가 효과적인 광고 플랫폼으로 부상하였다. SNS는 구성원간 정보나 영향력을 쉽게 전파할 수 있는 매체로써 적은 비용으로 최대의 사람들에게 광고를 할 수 있기 때문이다. 따라서 사전에 구축된 소셜 네트워크 상에서 효율적으로 마케팅을 수행하는 것이 중요해졌으며, 이러한 문제를 영향력 최대화 문제라고 한다. 영향력 최대화 문제란 특정한 정보확산 모델을 가정할 때, 소셜 네트워크 상에서 영향력을 최대화하는 k개의 노드를찾는 방법이다. 영향력 최대화 문제에서 최적해를 찾는 것은 NP-Hard임이 증명되었기 때문에 근사해를 찾는 알고리듬이 연구되었다. 그러나 영향력 최대화 문제의 근사해를 찾는 탐욕적 알고리듬들은 영향력 계산에 몬테-카를로 시뮬레이션을 이용하기 때문에 높은 정확도를 위해서 여러번의 시뮬레이션을 수행 할 경우 실행속도가 매우 느리다. 몇몇 연구들은 알고리듬의 정확도를 다소 포기하더라고 실행속도를 최대한 개선하는 방향으로 연구를 진행하였다. 해당연구들은 영향력 최대화 문제에 알맞는 휴리스틱을 이용하여 정확성을 희생하면서 보다 빠르게 영향력이 높은 노드를 찾는 해법을 제시하고있다. 본 연구에서는 소셜 네트워크가 무수히 많은 소규모 집단으로 이루어진 점에서 착안하여, 소셜 네트워크 그래프를 여러 군집으로 클러스터링한 후 각 군집에서 가장 영향력있는 노드를 선택하는 방식으로 영향력 최대화 문제의 해법을 찾는다. 또한 마르코프 클러스터링을 수정하여 각 클러스터 내의 끌개를 빠르게 찾는 방법을 제시한다. 이를 이용해 얻은 끌개들을 이용하여 기존의 알고리듬을 개선하는 하이브리드 알고리듬을 제시한다. 본 논문에서 제시한 하이브리드 알고리듬들은 실제 데이터셋을 이용하여 검증한 결과, 더욱 빠른 시간 안에기존 탐욕적 알고리듬에 근사한 영향력을 갖는 k 개의 시드 노드들을 찾아내며, 기존의 휴리스틱보다 더욱 좋은 성능을 보이는 것으로 나타났다.

Social Network Services are known as a effective marketing platform in that the customers trust the advertisement provided by their friends and neighbors. Viral Marketing is a marketing technique that uses the pre-constructed social networks to perform maketing with small cost while maximizing the spread. Therefore, which seed user to select is the primary concern in viral marketing. Influence maximization problem is a well known problem to find the top-k seed users who can maximize the spread of information in a social network. Since obtaining the global optimal solution for the influence maximization problem is proven to be NP-Hard, many greedy as well as heuristic approach has been researched. However, greedy approaches take to much time to obtain the seed node, whereas the heuristic approaches show poor performance. To remedy such problems, we exploit the community structures in the social network to enhance the performance of the heuristic approaches. We perform markov clustering to find the natural communities in the social network and consider the most influential user in the community as the candidate for the top-k seeds. Also, we propose a novel attractor identification algorithm that finds the influential nodes in the community with reduced runtime, and 3 new hybrid approaches for influence maximization problem. Experiments show that the proposed algorithms are more scalable than the greedy approaches, whereas the influence spread obtained by those outperforms the heuristic approaches.