Research On The Influence Maximization Problem In Social Networks

Recently,with the rapid development of social networks such as Twitter and WeChat,social network has become an important platform for people to publish views or opinions.Information constantly spreads and propagates on the social networks,which has aroused more and more researchers' attention on the way of information propagation.Influence maximization problem as a key problem in the field of information propagation,it aims to find a small number of users with high influence to maximize the number of users that influenced by these users after propagation.The thesis mainly focuses on the propagation models and algorithms of influence maximization in social networks.Aiming at some shortcomings of previous work about this field,the thesis gives new ideas and studies the followings:(1)The thesis firstly introduces the influence maximization problem into the signed social networks.Because the IC model is not consistent with the actual propagation situation of signed social networks,the thesis introduces the quality factor q and polarity relationship to extend the IC model,and proposes a new IC-NP model.Because the influence maximization problem originals from viral marketing,which pays more attention to the positive influence.Thus,based on the IC-NP model,the thesis then proposes the positive influence maximization problem(Positive Influence Maximization,PIM)and proves the PIM to be NP-hard and positive influence spread function to be monotonous and submodular.Finally,the thesis proposes a new greedy algorithm GICNP to solve the PIM problem.Experimental results demonstrate the effectiveness of the proposed model and algorithm.(2)Because the above-proposed GICNP is a greedy-based algorithm,greedy algorithm uses Monte-Carlo simulation to evaluate the influence of nodes,when it be applied for large-scale social networks,it needs to cost much time.Therefore,to solve the time efficiency of the influence maximization in the unsigned and signed social networks,the thesis firstly analyzes the influence ranking and propagation paths on the unsigned social networks,and proposes a RankPaths algorithm based on ranking and propagation paths.Later,to apply RankPaths algorithm to the signed networks,the thesis improves the RankPaths algorithm by combing RankPaths algorithm and the above-proposed IC-NP model,and proposes RankPaths-NP algorithm.Finally,the extensive experiments conducted on the unsigned and signed social networks,which show that the proposed two algorithms are superior to related heuristic algorithms in time and space efficiencies and are close to the greedy algorithms in influence spread.