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

作者：Xueqin Chang, Ruize Liu, Qing Liu, Baihua Zheng, Yunjun Gao · 年份：2026 · DOI：10.1145/3770855.3817870 · 被引用次数：1 · 研究领域：Computer science、Algorithm、Artificial intelligence、Machine learning、Theoretical computer science、Mathematical optimization

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.