Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.14047 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929549583843328 |
|---|---|
| author | Göktürk, Gökhan Kaya, Kamer |
| author_facet | Göktürk, Gökhan Kaya, Kamer |
| contents | 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 inter-node 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.2x and 12x faster on average on a single GPU and 8 GPUs, respectively. It can achieve up to 8x and 233.7x speedup on the same hardware settings. Furthermore, thanks to its smart load-balancing mechanism, on 8 GPUs, it is on average 5.6x faster compared to its single-GPU performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14047 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | DiFuseR: A Distributed Sketch-based Influence Maximization Algorithm for GPUs Göktürk, Gökhan Kaya, Kamer Distributed, Parallel, and Cluster Computing Performance Social and Information Networks 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 inter-node 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.2x and 12x faster on average on a single GPU and 8 GPUs, respectively. It can achieve up to 8x and 233.7x speedup on the same hardware settings. Furthermore, thanks to its smart load-balancing mechanism, on 8 GPUs, it is on average 5.6x faster compared to its single-GPU performance. |
| title | DiFuseR: A Distributed Sketch-based Influence Maximization Algorithm for GPUs |
| topic | Distributed, Parallel, and Cluster Computing Performance Social and Information Networks |
| url | https://arxiv.org/abs/2410.14047 |