Treffer: Sequential and Parallel Algorithms in Influence Maximization: An Investigation

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.