An efficient and effective hop-based approach for influence maximization in social networks

• Published in: Social network analysis and mining 2018-12, Vol.8 (1), p.10, Article 10
• Main Authors: Tang, Jing, Tang, Xueyan, Yuan, Junsong
• Format: Article
• Language: English
• Subjects: Algorithms; Applications of Graph Theory and Complex Networks; Approximation; Climbing; Computer Science; Data Mining and Knowledge Discovery; Diffusion models; Economics; Efficiency; Game Theory; Heuristic; Heuristic methods; Humanities; Law; Maximization; Methodology of the Social Sciences; Monte Carlo simulation; Optimization; Original Article; Probability; Propagation; Simulation; Social and Behav. Sciences; Social networks; Statistics for Social Sciences; Viral marketing
• ISSN: 1869-5450; 1869-5469
• DOI: 10.1007/s13278-018-0489-y

Influence maximization in social networks is a classic and extensively studied problem that targets at selecting a set of initial seed nodes to spread the influence as widely as possible. However, it remains an open challenge to design fast and accurate algorithms to find solutions in large-scale social networks. Prior Monte Carlo simulation-based methods are slow and not scalable, while other heuristic algorithms do not have any theoretical guarantee and they have been shown to produce poor solutions for quite some cases. In this paper, we propose hop-based algorithms that can be easily applied to billion-scale networks under the commonly used Independent Cascade and Linear Threshold influence diffusion models. Moreover, we provide provable data-dependent approximation guarantees for our proposed hop-based approaches. Experimental evaluations with real social network datasets demonstrate the efficiency and effectiveness of our algorithms.