Research On Influence Maximization Problem In Social Networks

In recent years, with the rapid development of social-networking web sites, such as Weibo, facebook, twitter and so on, how to find useful information among the magna-nimity data has become a hot issue. For example, how the information spread through social networks, how to detect the communities among the networks, influence maxi-mization problem, and how to recommend useful information to users et al. As we all know, more and more attention has paid on the problem of influence maximization prob-lem. This problem is defined by Kempe et al. and can be described as follows:finding a small set of chosen nodes in a social network that maximize the spread of influence under certain influence cascade models. To tackle this issue, Kempe et al. proposed the natural greedy strategy, which has a much better performance than other heuristic algorithms on influence spreads. However, this algorithm suffers from high computa-tion cost on estimating the influence function, in order to overcome this defect,many researchers proposed different optimization methods. While all above methods should assign the size of the chosen set in advance,to address this challenge, we explore the relationship between the size of the chosen set and the influence spread of the chosen set. Also we should consider the performance of the chosen set, which can be described by the stability of the chosen set. Experimental results on two real networks show that the necessity of our research. Besides, we propose a new algorithm to tackle the influ-ence maximization problem, we combine the simulated annealing algorithm with tabu search. We also conduct a lot of experiments to verify the effectiveness of the algorithm.The main contributions of this thesis can be summarized as follows:1. Summarize existed algorithms for Influence Maximization Problem in So-cial Networks. Summarize the research background of the information spread and influence maximization problem, introduce several basic models of infor-mation spread in social networks. Summarize existed algorithms for influence maximization problem and analyze advantages and disadvantages of these algo-rithms.2. Propose a new algorithm based on simulated annealing and tabu search. Simulated annealing algorithm can optimize the solutions of NP-Hard problems. Based on the tabu search, unnecessary repeated computation of the influence spread can be avoided. So we propose a new algorithm to solve the influence maximization problem by combining advantages of simulated annealing algo-rithm with tabu search.3. Propose several factor metrics. We propose several indicators to analyze the factors of the influence maximization problem. We propose the terminal condi-tion of the algorithm by defining the influence spread and the gain of the influence spread of a node. We also consider the performance of the chosen set, which can be described by the stability of the chosen set.