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

In this paper, we propose an effective pruning method for the influence maximization problem based on Random Walk and Rank Merge. The key idea is to efficiently find and prune out uninfluential nodes in order to dramatically reduce the amount of computation for evaluating influence spread. Our experimental results demonstrate the efficiency of the proposed method compared to previous state-of-the-art methods. Additionally, our method is easily parallelizable, resulting in further speed up.