Finding High Influence Vertices Based on Candidate Set

Influence maximization is the problem of finding a small set of seed vertices in a social network, so that the accumulated influence under certain propagation models is maximized. There are two problems about the existing methods: the influence spread of heuristic method is not stable, and the time complexity of greedy method is very high. In this paper, we devote to further reduce the gap between influence spread and running time. Firstly, we assess the comprehensive measurement of vertex, which provide a lightweight evaluation criterion rapidly for every vertex, Next, we construct the candidate vertices set from the communities, which reduce the search scope compared to the whole vertices, Finally, we tackle the efficiency issue of influence maximization from two complementary views. One is to propose the heuristic algorithm based on community candidate vertices (HBCC), attain a more competitive and stable influence spread. The other is to propose greedy algorithm based on community candidate vertices (GBCC), significantly reduce the running time. We carry out experiments on three real-world public datasets, the experiments have verified the effectiveness of the proposed methods compared to the baseline methods.