Complex Contagion Influence Maximization: A Reinforcement Learning Approach

Complex Contagion Influence Maximization: A Reinforcement Learning Approach

Haipeng Chen, Bryan Wilder, Wei Qiu, Bo An, Eric Rice, Milind Tambe

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 5531-5540. https://doi.org/10.24963/ijcai.2023/614

In influence maximization (IM), the goal is to find a set of seed nodes in a social network that maximizes the influence spread. While most IM problems focus on classical influence cascades (e.g., Independent Cascade and Linear Threshold) which assume individual influence cascade probability is independent of the number of neighbors, recent studies by sociologists show that many influence cascades follow a pattern called complex contagion (CC), where influence cascade probability is much higher when more neighbors are influenced. Nonetheless, there are very limited studies for complex contagion influence maximization (CCIM) problems. This is partly because CC is non-submodular, the solution of which has been an open challenge. In this study, we propose the first reinforcement learning (RL) approach to CCIM. We find that a key obstacle in applying existing RL approaches to CCIM is the reward sparseness issue, which comes from two distinct sources. We then design a new RL algorithm that uses the CCIM problem structure to address the issue. Empirical results show that our approach achieves the state-of-the-art performance on 9 real-world networks.
Keywords:
Search: S: Combinatorial search and optimisation
Machine Learning: ML: Reinforcement learning
Multidisciplinary Topics and Applications: MDA: Web and social networks