Online Influence Maximization: Concept and Algorithm
摘要
Influence maximization (IM) is to select a small number of users to maximize the influence spread in social networks, which is a classical combinatorial optimization problem that can be used in viral marketing, rumor blocking, and social recommendation. But in real applications, even though we can assume a potential diffusion model, parameters in this diffusion model are usually not easy to obtain in advance. Online IM interacts with the environment for multiple rounds and gradually fits the diffusion parameters, so as to obtain the optimal solution and maximize the influence spread. In this chapter, we first systematically introduce the learning framework of online IM: combinatorial multiarmed bandit model. Then, we summarize online IM algorithms based on edge-level feedback, node-level feedback, and other feedback. Next, we consider generalizing online IM to other innovative and variant applications in social networks. Finally, we analyze the research development of online IM, and challenges and future research directions are provided.