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

Official URL: https://dx.doi.org/10.1007/s11227-024-06566-z

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× and 12× faster on average on a single GPU and 8 GPUs, respectively. It can achieve up to 8× and 233.7× speedup on the same hardware settings. Furthermore, thanks to its smart load-balancing mechanism, on 8 GPUs, it is on average 5.6× faster compared to its single-GPU performance.