Online Influence Maximization: Concept and Algorithm

Abstract

In this survey, we offer an extensive overview of the Online Influence Maximization (IM) problem by covering both theoretical aspects and practical applications. For the integrity of the article and because the online algorithm takes an offline oracle as a subroutine, we first make a clear definition of the Offline IM problem and summarize those commonly used Offline IM algorithms, which include traditional approximation or heuristic algorithms and ML-based algorithms. Then, we give a standard definition of the Online IM problem and a basic Combinatorial Multi-Armed Bandit (CMAB) framework, CMAB-T. Here, we summarize three types of feedback in the CMAB model and discuss in detail how to study the Online IM problem based on the CMAB-T model. This paves the way for solving the Online IM problem by using online learning methods. Furthermore, we have covered almost all Online IM algorithms up to now, focusing on characteristics and theoretical guarantees of online algorithms for different feedback types. Here, we elaborately explain their working principle and how to obtain regret bounds. Besides, we also collect plenty of innovative ideas about problem definition and algorithm designs and pioneering works for variants of the Online IM problem and their corresponding algorithms. Finally, we encapsulate current challenges and outline prospective research directions from four distinct perspectives.

References in corpus (8)

• Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case
• Online Influence Maximization (Extended Version)
• Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models
• ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning
• A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
• Factorization Bandits for Online Influence Maximization
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Online Influence Maximization in Non-Stationary Social Networks