The International Conference for High Performance Computing, Networking, Storage, and Analysis
The International Conference for High Performance Computing, Networking, Storage, and Analysis
Workshop: IA^3 2025 — 15th Workshop on Irregular Applications: Architectures and Algorithms
Authors: Jacob Doney, Xin Huang, and Chul-Ho Lee (Texas State University)
Abstract: The influence maximization problem seeks to identify a subset of k vertices in a network that, when activated, maximizes the spread of influence under a given diffusion process. It is NP-hard to find the optimal set of influential vertices; thus, recent studies have focused on developing algorithms to find an approximate solution. The state-of-the-art parallel implementations leverage a sketch-based algorithm called influence maximization via martingales (IMM). However, IMM incurs significant memory overhead due to the storage requirements of graph traversal samples called random reverse reachable (RRR) sets. In this paper, we introduce efficient Influence Maximization (eIM), a novel GPU-accelerated IMM algorithm designed to improve the efficiency and scalability of IMM. Compared to two popular GPU implementations, eIM achieves similar accuracy with one to three orders of magnitude speedups while reducing the memory requirement to store network data and RRR sets up to 54%.
Back to IA^3 2025 — 15th Workshop on Irregular Applications: Architectures and Algorithms Archive Listing Back to Full Workshop Archive Listing