Influence Maximization in Unknown Social Networks: A Contextual Bandit Approach (Extended Abstract)

The Influence Maximization (IM) problem is a fundamental problem on social networks where you are required to choose a set of few seeds from which to start an information campaign aiming to reach as many nodes as possible in the network. In this work, we consider the IM problem in a setting where neither network nodes nor their relationships are known, except for very few samples. Thus, you have to orchestrate the campaign while learning information about the network. This problem has been recently showed to have applications in public health: e.g., to maximize the diffusion of HIV prevention information among marginalized people, such as homeless. In this work we propose a two-level bandit approach to address the IM problem with partially observed networks: the lower layer implements a contextual bandit that selects nodes to query based on the current observed subgraph, available nodes, and edge discovery rewards; the upper meta-layer dynamically chooses between two exploration strategies: a global approach maximizing immediate edge discovery, and a component-focused strategy targeting the least-explored connected component. This dual approach prevents local over-exploitation while maintaining efficient global exploration. The proposed method outperforms the state-of-the-art method and shows robustness across diverse network topologies.