Sequential and Parallel Algorithms in Influence Maximization: An Investigation
MSU Affiliation
James Worth Bagley College of Engineering; Department of Computer Science and Engineering
Creation Date
2025-11-14
Abstract
Influence Maximization (IM) involves identifying the most influential individuals within a network to maximize the spread of influence. This problem is critical for applications such as viral marketing, epidemic control, and social media, but it is a challenging NP-hard problem. Consequently, several approximation algorithms have been developed, both sequential and parallel. This investigation explores IM algorithms, categorizing them into simulation-based, proxy-based, and sketch-based approaches. We examine the theoretical foundations, computational efficiencies, and practical applications of these algorithms. Additionally, we explore recent developments in machine learning, reinforcement learning, and quantum computing-based methods. We compare the performance and efficiency of sequential, parallel (including multithreaded), distributed implementations, and GPU-accelerated solutions. Finally, we discuss potential future research directions, emphasizing the need for comprehensive benchmarking and the trade-offs between time and space complexity in IM algorithms.
Publication Date
10-31-2025
Publication Title
SMBD '25: Proceedings of the 2025 International Conference on Simulation, Modeling and Big Data
Publisher
ACM
First Page
230
Last Page
237
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Recommended Citation
Zhang, Z. (2025). Sequential and Parallel Algorithms in Influence Maximization: An Investigation. Proceedings of the 2025 International Conference on Simulation, Modeling and Big Data, 230–237. https://doi.org/10.1145/3768740.3768776
