Affiliations: College of Computer Science & Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, China
Correspondence:
[*]
Corresponding author. Li Yan, College of Computer Science & Technology, Nanjing University of Aeronautics and Astronautics, Nanjing, 211106, China. E-mail: yanli@nuaa.edu.cn.
Abstract: Influence maximization is a fundamental problem, which is aimed to specify a small number of individuals as seed set to influence the largest number of individuals under a certain influence cascade model. Most existing works on influence maximization may have either high effectiveness or good efficiency,which can not balance both the effectiveness and efficiency. One of the reason is that they do not consider the effect of influence overlap on the effectiveness. That is, these works ignore the phenomenon that the same set of nodes may be influenced by a subset of different influential nodes. To tackle the effectiveness of heuristic algorithm, we propose a three-phase-based heuristic algorithm, called Three-Phase-based Heuristic (TPH), which uses K-shell method to find influential nodes firstly. Moreover, we utilize weighed degree to make up for the coarse-grained of K-shell method. At last, we take advantage of similarity index to reduce the effect of influence overlap by covering the similar neighbor nodes with low influence. Furthermore, exhaustive experiments indicate that the proposed algorithm outperforms the other baseline algorithms in the aspects of influence spread and running time.
Keywords: Influence maximization, similarity index, influence overlap, social networks
