Finding High-Influence Leader Based on Local Metrics

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. The existing greedy methods can guarantee the optimal influence spread, however, the time complexity is still very high. In this paper, we devote to further reduce the time complexity, and maintain a maximized influence spread. We propose a new way for tackling the efficiency issue of influence maximization, referred to as greedy algorithm based on local metrics (GBLM). Specifically, the major advantages of GBLM are that: 1) GBLM proposes the local metrics of vertex, which provide the finer-grained evaluation criteria for every vertex, 2) GBLM constructs the candidate vertices set by its local metrics from every community, which reduce the search scope compared to the whole vertices, 3) Based on the candidate vertices set, GBLM adopts greedy method based on sub modularity to find top-k seed vertices, which carry out global measure in the whole network to attain a maximized influence spread. We carry out experiment on the four real-world datasets, the results have verified that GBLM significantly reduce the running time, meanwhile maintain an approximate optimal influence spread.