Influence Learning and Maximization

Open Access

Abstract

International audience ; The problem of maximizing or minimizing the spreading in a social network has become more timely than ever with the advent of fake news and the coronavirus epidemic. The solution to this problem pertains to influence maximization algorithms that identify the right nodes to lockdown for epidemic containment, hire for viral marketing campaigns, block for online political propaganda etc. Though these algorithms have been developed for many years, the majority of the literature focuses on scalability issues and relaxing the method's assumptions. In the recent years, the emergence of new complementary data and more advanced machine learning methods for decision have guided part of the literature towards learning-based approaches. These can range from learning how information spreads over a network, to learning how to solve the combinatorial optimization problem itself. In this tutorial, we aim to dissentangle and clearly define the different tasks around learning for influence applications in social networks. More specifically, we start from traditional influence maximization algorithms, describe the need of influence estimation and delineate the state-of-the-art on influence and diffusion learning. Subsequently, we delve into the problem of learning while optimizing the influence spreading which is based on online learning algorithms. Finally, we describe the latest approaches on learning influence maximization with graph neural networks and deep reinforcement learning.