Presentation
eIM: GPU-Accelerated Efficient Influence Maximization in Large-Scale Social Networks
DescriptionThe 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%.
Event Type
Workshop
TimeSunday, 16 November 202510:30am - 10:55am CST
Location232