Scalable and parallelizable influence maximization with Random Walk Ranking and Rank Merge Pruning

Abstract

As social networking services become a large part of modern life, interest in applications using social networks has rapidly increased. One interesting application is viral marketing, which can be formulated in graph theory as the influence maximization problem. Specifically, the goal of the influence maximization problem is to find a set of k nodes(corresponding to individuals in social network) whose influence spread is maximum. Several methods have been proposed to tackle this problem but to select the k most influential nodes, they suffer from the high computational cost of approximating the influence spread of every individual node.