gIM: GPU Accelerated RIS-Based Influence Maximization Algorithm.

Given a social network modeled as a weighted graph $G$ G , the influence maximization problem seeks $k$ k vertices to become initially influenced, to maximize the expected number of influenced nodes under a particular diffusion model. The influence maximization problem has been proven to be NP-hard, and most proposed solutions to the problem are approximate greedy algorithms, which can guarantee a tunable approximation ratio for their results with respect to the optimal solution. The state-of-the-art algorithms are based on Reverse Influence Sampling (RIS) technique, which can offer both computational efficiency and non-trivial $(1-{1}/{e}-\epsilon)$ (1 - 1 / e - ε) -approximation ratio guarantee for any $\epsilon >0$ ε > 0 . RIS-based algorithms, despite their lower computational cost compared to other methods, still require long running times to solve the problem in large-scale graphs with low values of $\epsilon$ ε . In this article, we present a novel and efficient parallel implementation of a RIS-based algorithm, namely IMM, on GPU. The proposed GPU-accelerated influence maximization algorithm, named gIM, can significantly reduce the running time on large-scale graphs with low values of $\epsilon$ ε . Furthermore, we show that gIM algorithm can solve other variations of the IM problem, only by applying minor modifications. Experimental results show that the proposed solution reduces the runtime by a factor up to 220 ×. The source code of gIM is publicly available online. [ABSTRACT FROM AUTHOR]