Research Of Influence Maximization Algorithms In Social Networks

In the marketing field, while promoting a product, it is a problem for a company that how to spend limited budget to find some influential individuals to test the free samples so that these individuals can eventually influence the largest number of people with the strategies of "Word-of-mouth" and "Viral-marketing". This is the initial motivation of the influence maximization problem. This problem has become a focus in academia since it was introduced to the field of social network by Domingos and Richardson, and scholars have proposed different algorithms to resolve it.Firstly, this thesis introduces the relevant theoretical knowledge of the influence maximization problem, including social networks and community structure and so on, and mainly researches the IC and LT spread models. Secondly, this thesis introduces the existing algorithm in detail, such as the greedy, MDA and OASNET algorithm. After analyzing the drawback of these algorithms, we propose a CPWM algorithm based on the community structure. On one hand, the CPWM algorithm overcomes the high time complexity problem of the greedy algorithm, and the overlapping problem of the MDA algorithm which caused by the selection of initial nodes, and the loss of edges problem when we take communities as independent networks in the OASNET algorithm. On the other hand, while many other algorithms only take node degree as the influence, the CPWM algorithm not only considers the degree of one node but also its pointing node's degree, and this is more according with the actual situations.Finally this thesis compares the CPWM algorithm with the greedy, OASNET, MDA and Random algorithm in effect and time complexity both on real social networks and artificial networks. The experimental shows that the CPWM algorithm can greatly reduce the time complexity under the case of the same effect of the greedy algorithm, and the CPWM algorithm improves the effect and efficiency compared with the OASNET algorithm, and the CPWM algorithm improves the effect and has the similar time complexity compared with the MDA and Random algorithm. In a word, the CPWM algorithm is an effective algorithm for resolving the influence maximization problem.