Research On Algorithms And Diffusion Models In Influence Maximization Problem

In recent years, with the rapid growth of Internet, the increased popularity of online social network sites, such as Weibo, Wechat and Facebook, have pervaded nearly every aspect of our daily lives. The generated large-scale social data has brought in many opportunities as well as challenges for researchers. The information diffusion has attracted a great deal of attention and the influence maximization is one of the most interesting problems in viral marketing. Simply, the influence maximization is to choose a tiny set of seed users, with the word of mouth of these seed users, to maximize the influence spread.This paper focuses on the influence maximization problem in two aspects. One is to propose a greedy algorithm based on the Activation Set and the other is to study the influence maximization problem in signed social networks.Greedy-based methods and heuristics-based methods are two directions to solve influence maximization problem. The greedy-based methods, using Monte-Carlo simulations to estimate influence spread, are not scalable for large social networks. The heuristics-based methods with heuristic strategies are faster but the performance cannot be guaranteed. This paper proposes a greedy algorithm based on the Activation Set to improve both performance and effectiveness. The influence spread function based on the Activation Set is proved to be monotone and submodular. And the UserGreedy algorithm is implemented with an influence path based method to obtain the Activation Set. Experiments in this paper show that our algorithm is faster than existing greedy-based algorithms and have better performance than heuristics-based algorithms.Other work is to study the influence maximization problem in signed social networks and proposes the linear threshold model in signed social networks (LT-S). LT-S model extends linear threshold model with both positive and negative relationships and opinions. The influence spread function under the LT-S model is proved to be neither monotone nor submodular and an improved R-Greedy algorithm, RLP, is proposed. Extensive experiments demonstrate that RLP algorithm outperforms the baseline algorithms.