RIC Model-based Influence Maximization On Social Networks

Nowadays the social network plays an increasingly important role in people's daily life,so how to maximize the influence of information in social networks has attracted more and more attention.In order to propagate information through the social network,we can choose a small set of users(called seed set),then persuade them to accept the message.Once they accept the information,they will widely spread the information to their friends through their great influence,then the people who are influenced will also affect their friends.Through this word-of-mouth,the information is propagated in the network.Then how to choose the seed set so that the information can affect as many users as possible,namely influence maximization problem.A lot of works have been done on this problem,mainly including two aspects: establishing a reasonable information diffusion model and putting forward the appropriate seeding strategy.The main works in this paper is as follows:1.Since some existing models cannot fully capture the uncertainties of the information diffusion process in real-world social networks,in this paper,we consider these uncertainties and introduce the Realistic Independent Cascade(RIC)model.2.Based on the RIC model,the concept of node activity is proposed to measure the influence of nodes,then a greedy-degree seed search algorithm is proposed.Comparison experiments are made both on synthetic networks and real networks,and the results can show the superiority of greedy-degree algorithm.3.Based on the RIC model,R-greedy seed search algorithm completed in three steps is proposed,furthermore,M-greedy is proposed to optimize the time complexity of R-greedy.Comparison experiments both on synthetic networks and real networks show that R-greedy and M-greedy have similar effect,better than the existing comparison algorithms,and M-greedy is nearly half of R-greedy time cost.4.Based on the proposed RIC model,a seed search algorithm based on sketch is proposed,called D-greedy,to solve the problem of maximization of influence.It can directly guarantee the submodularity property of the influence function and save time consuming at the same time.Experiments on real networks and synthetic networks show that the D-greedy algorithm has obvious advantages.