Research On Propagation Model And Algorithm For Influence Maximization In Social Network

With the emergence and rapid proliferation of social network applications in21stcentury, such as Twitter, Facebook, Flickr and so on, people are acquiring informationnot just from newspapers, broadcasting and TV any more. Nowadays, social networkis becoming a more and more important medium that conveys information. As theresearch of influence maximization in social network plays a very important role forguiding practical application, it has become a concerned problem in computer sciencefield. We focus our attention on the models and algorithms of influence maximizationto display our research as follows.First of all, we formulate the problem of influence maximization in socialnetwork in details. In order to know how the information propagates in social network,some important information spread models and corresponding definitions areanalyzed, and some algorithms are summarized so as to build the theoreticalfoundation for our research on propagation model and algorithm of influencemaximization in social network.Secondly, we point out the irrationality about the assumption of those basicmodels. As we know, different parent nodes have different influence on their childnode. Based on this idea, we propose a new PRP model in which the correlation andauthority of nodes are considered. The experimental results show that our proposedmodel is more effective than traditional Linear Threshold Model, Weighted CascadeModel and Independent Cascade Model in solving the influence maximizationproblem. As PRP model put the practical problems into consideration, it is of muchgreater value.Finally, greedy algorithm and advanced greedy algorithm both have a very hightime complexity for very large-scale social network as analyzed in solving theinfluence maximization problem. Thus, an advanced linear threshold propagationmodel and a new algorithm named PTMA are proposed to solve the influencemaximization problem based on the idea of probability transfer matrix. As PTMAalgorithm could save the time that is used to count the number of active nodes everytime interval in other algorithms, it is more efficient than other algorithms and has amuch lower time complexity. And it’s suitable for the very large-scale social network.