The Influence Maximization Problem In Dynamic Social Networks

In recent years, with the popularity of twitter and other online social networking sites, the influence maximization problem has become increasingly important. That is, under the premise of a limited budget, how to select a number of the most influential social network users to start marketing activities and cover the scope of the market as large as possible by using "viral marketing" and "word of mouth". Currently the problem has been studied extensively and variety of relatively mature greedy and heuristics algorithms have been proposed by scholars. However, state-of-the-art works all assume that the network topology stays static while ignoring the fact that real-world social networks exhibit high-level dynamics. Because the interaction between individuals on the real social network is changing dynamically according to certain growth law over time. Thus, existing work in influence maximization, which focus on static network, exhibits limited applicability in real-word cases. So if you continue to use the seeds selected on the static network nodes may not be able to achieve satisfactory results in dynamic social network.In this paper, we proposed a novel algorithm to solve the influence maximization in the dynamic social networks by combining the influence maximization problem and the dynamic evolution of the social networks. Firstly, we introduce the theory of the influence maximization problem in the traditional static network, including the influence propagation models, seed nodes selection strategy as well as the classic greedy algorithms and heuristics ones. Secondly, we focus on the relevant theoretical knowledge dynamic network, including the characteristics of real network metrics, common network classification standards and ER, BA, FF and other classic dynamic network growth models. Finally, we proposed a novel algorithm D-MGreedy IC to solve the influence maximization in the dynamic social networks taking into account the evolution of the real social network. To achieve that, our algorithm introduces the Forest Fire Model into the influence propagation process to find seeds with more scalability and predictability comparing with those selected from existing algorithms.Finally, We analyze the time complexity and evaluate the proposed algorithm on both synthetic and real-word networks. Experimental results show that our proposed algorithm achieves a better performance in selecting high-quality seed nodes. Compared to the traditional ones in the static social networks, we take into account the dynamic factors of the real social network so that the chosen seeds are more scalability and predictability. Furthermore, it has better guidance for the actual social network product promotion. Meanwhile, it also has practical significance to apply the influence maximization problem to marketing, news dissemination and advertising.