Efficient influence maximization under TSCM: a suitable diffusion model in online social networks

详细信息    查看全文

• 作者：Yadong Qin ; Jun Ma ; Shuai Gao
• 关键词：Social networks ; Influence maximization ; Three degrees of influence ; Diffusion models
• 刊名：Soft Computing
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：21
• 期：4
• 页码：827-838
• 全文大小：
• 刊物类别：Engineering
• 刊物主题：Computational Intelligence; Artificial Intelligence (incl. Robotics); Mathematical Logic and Foundations; Control, Robotics, Mechatronics;
• 出版者：Springer Berlin Heidelberg
• ISSN：1433-7479
• 卷排序：21

文摘

The study on influence modeling is to understand the information diffusion and word-of-mouth marketing. Independent Cascade Model (ICM) is the most widely studied theoretical diffusion model. However, until now it is unknown whether ICM matches the real information diffusion in online social networks. In this paper, we demonstrate that ICM cannot model accurately for the structure of information diffusion over real networks through our experiments. Meanwhile, we propose a more suitable diffusion model named Three Steps Cascade Model (TSCM) to simulate information diffusion process in online social networks. We focus on the influence maximization problem under TSCM. First, we show that this optimization problem is NP hard. Then we prove that the greedy algorithm can guarantee an influence spread within 63 % of the optimal value. Finally we devise an efficient algorithm which is scalable for large social networks. The experiment results on large-scale real networks show the robustness and utility of our approach.