Approximation and Learning-based Algorithms for Influence Maximization in Multilayer Social Networks

Abstract

Motivated by the observation that users in the real world often engage across multiple social networks simultaneously, we study the problem of influence maximization in multilayer social networks (Mlim), aiming to select a small set of nodes that maximizes the total influence spread across all layers. To this end, we introduce a hybrid propagation model that jointly captures layer-specific diffusion dynamics and probabilistic cross-layer propagation. Based on this model, we formally define the Mlim problem and establish its NP-hardness, monotonicity, and submodularity. To address the Mlim problem, we first propose a greedy baseline Mlim-Greedy, which achieves a (1-1/e) approximation. Since exact influence computation in Mlim-Greedy is #P-hard,we propose STARIM, a scalable algorithm with layer-weighted influence sampling that guarantees a (1 - 1/e - 𝔖) approximation. To further enhance efficiency, we design LGQIM, a two-stage framework where multilayer representation learning predicts influence spread from network structure, enabling deep reinforcement learning for adaptive seed selection. Extensive experiments on nine real-world datasets demonstrate that (1) STARIM is up to 2 orders of magnitude faster than the baselines while yielding 10%-30% improvement in influence spread, and (2) LGQIM further achieves an average 10× speedup over STARIM while maintaining comparable influence spread.