Bring Order into the Samples: A Novel Scalable Method for Influence Maximization

Publication Type:
Journal Article
Citation:
IEEE Transactions on Knowledge and Data Engineering, 2017, 29 (2), pp. 243 - 256
Issue Date:
2017-02-01
Filename Description Size
2017_TKDE_influence_maximization.pdfPublished Version1.27 MB
Adobe PDF
Full metadata record
© 2016 IEEE. As a key problem in viral marketing, influence maximization has been extensively studied in the literature. Given a positive integer k, a social network G and a certain propagation model, it aims to find a set of k nodes that have the largest influence spread. The state-of-the-art method IMM is based on the reverse influence sampling (RIS) framework. By using the martingale technique, it greatly outperforms the previous methods in efficiency. However, IMM still has limitations in scalability due to the high overhead of deciding a tight sample size. In this paper, instead of spending the effort on deciding a tight sample size, we present a novel bottom-k sketch based RIS framework, namely BKRIS, which brings the order of samples into the RIS framework. By applying the sketch technique, we can derive early termination conditions to significantly accelerate the seed set selection procedure. Moreover, we provide a cost-effective method to find a proper sample size to bound the quality of returned result. In addition, we provide several optimization techniques to reduce the cost of generating samples' order and efficiently deal with the worst-case scenario. We demonstrate the efficiency and effectiveness of the proposed method over 10 real world datasets. Compared with the IMM approach, BKRIS can achieve up to two orders of magnitude speedup with almost the same influence spread. In the largest dataset with 1.8 billion edges, BKRIS can return 50 seeds in 1.3 seconds and return 5,000 seeds in 36.6 seconds. It takes IMM 55.32 second and 3,664.97 seconds, respectively.
Please use this identifier to cite or link to this item: