A reversed node ranking approach for influence maximization in social networks

摘要

Influence maximization, i.e. to maximize the influence spread in a social network by finding a group of influential nodes as small as possible, has been studied widely in recent years. Many methods have been developed based on either explicit Monte Carlo simulation or scoring systems, among which the former perform well yet are very time-consuming while the latter ones are efficient but sensitive to different spreading models. In this paper, we propose a novel influence maximization algorithm in social networks, named Reversed Node Ranking (RNR). It exploits the reversed rank information of a node and the effects of its neighbours upon this node to estimate its influence power, and then iteratively selects the top node as a seed node once the ranking reaches stable. Besides, we also present two optimization strategies to tackle the rich-club phenomenon. Experiments on both Independent Cascade (IC) model and Weighted Cascade (WC) model show that our proposed RNR method exhibits excellent performance and outperforms other state-of-the-arts. As a by-product, our work also reveals that the IC model is more sensitive to the rich-club phenomenon than the WC model.