Online Influence Maximization: Concept and Algorithm
Jianxiong Guo
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.