Efficient and effective influence maximization in large-scale social networks via two frameworks

Influence maximization is to find a small subset of nodes in a network so that the scope of influence spread can be maximized, and it is a significant optimization problem in rumor control and viral marketing. Although there have been a lot of research works for this problem, it is still difficult to design algorithms to meet three requirements simultaneously, i.e., fast computation, low memory consumption and guaranteed accuracy when scaling to large-scale networks. In this paper, we research the efficient and effective influence maximization algorithms from two directions. One is to design an effective similarity-based framework for enhancing the influence spread of the centrality-based heuristic algorithms, and another is to improve greedy algorithm for efficiency by a two-stage framework. The extensive experiments in undirected and directed networks all demonstrate that two heuristic algorithms using the proposed framework acquire comparable results to the state of the art and are two orders of magnitude faster than D-SSA in a million of network. Simultaneously, the improved greedy algorithm is 2 to 12 times faster than CELF with the almost same influence spread.