The Analysis And Design Of Influence Maximization Algorithm Based On Cost-effective

As the development of the Internet, more and more online social networks emerge, such as Facebook and Twitter, Chinese renren and sina-weibo. The online social network provides a new social model to the people, and reflects the social relations in real life. At the same time, a new markeing mode called viral marketing was born, disseminating some information in the social networks based on the word-of-mouth, just as advertisement. How to select a set of seed nodes to disseminate the information that maximizes the total number of nodes influenced is a hot topic, called influence maximization problem.However, the research on classic influence maximization problem has ignored the differences between users when choosing the initial source of information. But differernt nodes have different costs to be selected, the actual marketing has budget constraints, how to get the best marketing effect in this condition needs to reconsider. Based on the above, this paper gives the definition of user cost, and puts forward the influence maximization problem based on cost-effective.To solve this problem, this paper combines the features of network topology and influence propagation model, and proposes a heuristic algorithm based on probability coverage (ProbCover Algorithm), then proposes the improved coverage algorithm (ProbCoverLF Algorithm) using submodular and lazy forward computing technology. Based on the research, a prototype system is designed and implementationed.In this paper, experiments were carried out on the three data sets and independent cascade model, and the independent cascade model uses fixed probability and variable probability respectively, the experimental results show that:(a) in the range of influence, the algorithms proposed in this paper is better than the traditional heuristic algorithm, especially in the variable probability independent cascade model; (b) in the time efficiency, although the running time of the algorithms proposed in this paper is long than the traditional heuristic algorithms, but is still in the acceptable range. Two aspects of the influence scope and time efficiency prove the effectiveness of the proposed algorithms in this paper.