Scalable and Parallelizable Influence Maximization with Random Walk Ranking and Rank Merge Pruning

Abstract

Influence maximization problem is to find the k most influential nodes(or individuals) on a social network G that maximize the influence spread with an underlying influence diffusion model. As the social network services take a large portion of modern life, influence maximization became an uprising important problem in viral marketing and many methods have been developed. Previous methods, however, commonly suffer from very low evaluation of influence spread. They use greedy approximation to deal with the NP-hardness of selecting k seed nodes, and to run the greedy method, they spend significant amount of time evaluating the influence spread of every individual nodes; which takes a big portion of the total execution time for the influence maximization problem.

In this paper, we propose an effective pruning method based on Random Walk and Rank Merge, which prunes out uninfluential nodes effectively and dramatically reduces the number of influence evaluations at the initial step. Our pruning method combined with IPA algorithm significantly reduces the total execution time of the algorithm by up to ten times, which becomes the fastest influence maximization among all the state-of–the-art methods (i.e. IPA [10], IRIE [8] and TIM+ [9]). Additionally, our method is easily parallelizable with few lines of OpenMP statements, and the parallel version of our method further speeds up the execution time by up to 5 times with 6-core CPU.