An Efficient GPU-CPU Monte Carlo Simulation Algorithm for Influence Maximization in Large Scale Graphs

Influence maximization is an NP-hard problem to find a small set of highly influential individuals in a social network to maximize the influence spread under a specific information propagation model. While the Monte-Carlo-simulation-based algorithms produce near-optimal solutions with a theoretical guarantee, these algorithms run extremely slow for large-scale networks. Therefore, many heuristic algorithms have been proposed without theoretical guarantee, compromising the quality of solution with time efficiency. On the other hand, graphics processing unit (GPU) has recently been widely used as a popular general-purpose computing device and shown promising potential in accelerating the computation of some graph algorithms. In addition, the development of heterogeneous computing frameworks such as OpenCL and HSA makes the collaboration of CPU and GPU much more easily than before. As a result, we propose an efficient GPU-CPU algorithm for influence maximization problem on heterogeneous platform, which is based on the Monte-Carlo-simulation-based approach, where we leverage the parallel processing capability of GPU for large number of independent influence spread calculations. Moreover, several techniques are presented in this paper to accelerate the algorithm. The experimental results show the speedup over the state-of-the-art Monte-Carlo-simulation-based algorithms for CPU and GPU respectively with up to two orders of magnitude while maintaining the quality of solution.