Research On Influence Models And Algorithms Of Social Networks

"Word-of-mouth" and "viral marketing" effects in marketing have raised the problem of how to find the influential members of people. This problem highly corresponds to the research on influence models and algorithms of social networks. The maximization of influence has been a focus in academia in recent years since it was introduced in the field of social network analysis. Basing on disciplines of influence propagation in real network and combining with theoretical analysis, the researchers establish various communication models and translate the influence maximization problem into an algorithm problem of propagation models.At the beginning, this paper focuses on two kinds of basic influence propagation models, which are called the independent cascade model and the linear threshold model. We define the spread mechanism on the two propagation models. Meanwhile, the related property, way of investigation and classical algorithms of influence maximization are also described. By summarizing and contrasting the characteristics of the two classical algorithms, basing on the analysis of its advantages and disadvantages, this paper proposes a new algorithm which applies graph of strongly connected components decomposition to the influence maximization problem, and compares performance of our new algorithm with the two classical algorithms. The results show that the time complexity of the new algorithm is lower than the two classical algorithms. In this paper we use the project "User Behavior Analysis System" as our experimental platform, which is a cooperation project between our laboratory and China Mobile Communications Research Institute. We build propagation models and spread mechanism, implement the new algorithm and the two classical algorithms, and then do a series of experiments on several real-world social network data sets extracted from Stanford University and the University of Michigan.Experimental results show that our new algorithm can resolve the influence maximization problem more efficiently than the classical algorithms while the scale of the problem is very large. And this conclusion is completely consistent with the theoretical analysis in this paper.