Research On Influence Maximization In Social Network Based On Three Degrees Of Influence Theory

Recently, the increasing popularity of many online social network sites, such as Twitter, Facebook, Flickr, SinaWeiBo and Zhihu, offers companies new opportunities for enabling large-scale viral marketing online through the powerful word-of-mouth effect. This makes the Influence Maximization become a hot research topic.The goal of the Influence Maximization is to make the influence maximize in the social network. To investigate the most influence users in real social network, we must know the way of the influence propagation first. Researchers have proposed many diffusion models to model real information diffusion, including Independent Cascade Model (ICM), which is the most widely studied theoretical diffusion model. However, until now it is unknown whether these purely theoretical models match 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 main contributions are as follows:● We analyze the background and current research status of influence maximization (IM) and discuss the problems of the IM.● We summarize the models under IM problem and some efficient algorithms for these different IM problems.● We collect Sina Weibo retweet trees. Through analyzing Weibo retweet trees, we propose Three Steps Cascade Model(TSCM). We devise TLLFGreedy algorithm to solve IM problem under this model. According to our experiments, we prove that:1. TSCM is more suitable for simulating information diffusion in real social networks than ICM.2. TLLFGreedy is efficient to solve IM problem under TSCM.