Influence Maximization Algorithm in Social Networks Based on Three Degrees of Influence Rule

摘要

Influence maximization algorithms in social networks are aimed at mining the most influential TOP-K nodes in the current social network, through which we will get the fastest spreading speed of information and the widest scope of influence by putting those nodes as initial active nodes and spreading them in a specific diffusion model. Nowadays, influence maximization algorithms in large-scale social networks are required to be of low time complexity and high accuracy, which are very hard to meet at the same time. The traditional Degree Centrality algorithm, despite of its simple structure and less complexity, has less satisfactory accuracy. The Closeness Centrality algorithm and the Betweenness Centrality algorithm are comparatively highly accurate having taken global metrics into consideration. However, their time complexity is also higher. Hence, a new algorithm based on Three Degrees of Influence Rule, namely, Linear-Decrescence Degree Centrality Algorithm, is proposed in this paper in order to meet the above two requirements for influence maximization algorithms in large-scale social networks. This algorithm, as a tradeoff between the low accuracy degree algorithm and other high time complexity algorithms, can meet the requirements of high accuracy and low time complexity at the same time.