DiFuseR: a distributed sketch-based influence maximization algorithm for GPUs

Influence maximization (IM) aims to find a given number of “seed" vertices that can effectively maximize the expected spread under a given diffusion model. Due to the NP-hardness of finding an optimal seed set, approximation algorithms are often used for IM. However, these algorithms require a large number of simulations to find good seed sets. In this work, we propose DiFuseR, a blazing-fast, high-quality IM algorithm that can run on multiple GPUs in a distributed setting. DiFuseR is designed to increase GPU utilization, reduce internode communication, and minimize overlapping data/computation among the nodes. Based on the experiments with various graphs, containing some of the largest networks available, and diffusion settings, the proposed approach is found to be \(3.2\times\) $3.2\times$ and \(12\times\) $12\times$ faster on average on a single GPU and 8 GPUs, respectively. It can achieve up to \(8\times\) $8\times$ and \(233.7\times\) $233.7\times$ speedup on the same hardware settings. Furthermore, thanks to its smart load-balancing mechanism, on 8 GPUs, it is on average \(5.6\times\) $5.6\times$ faster compared to its single-GPU performance.