gIM: GPU Accelerated RIS-based Influence Maximization Algorithm

Abstract

Given a social network modeled as a weighted graph $G$, the influence maximization problem seeks $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-\frac{1}{e}-\epsilon )$-approximation ratio guarantee for any $\epsilon >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 paper, 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\times$. The source code of gIM is publicly available online.

arXiv commentAccepted for publication in IEEE Transactions on Parallel and Distributed Systems (TPDS)

References in corpus (7)

• Emergence of scaling in random networks
• Mean-field theory for scale-free random networks
• GraphSAINT: Graph Sampling Based Inductive Learning Method
• Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
• Time-Critical Influence Maximization in Social Networks with Time-Delayed Diffusion Process
• Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
• C-SAW: A Framework for Graph Sampling and Random Walk on GPUs

Cited by in corpus (2)

• Fused Breadth-First Probabilistic Traversals on Distributed GPU Systems
• BLEST: Blazingly Efficient BFS using Tensor Cores