Approximation and learning-based algorithms for influence maximization in multilayer social networks
Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
8-2026
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.
Keywords
Influence maximization, Multilayer social networks, Theoretical analysis, Graph embedding, Deep reinforcement learning
Discipline
Artificial Intelligence and Robotics | Databases and Information Systems
Research Areas
Intelligent Systems and Optimization
Areas of Excellence
Digital transformation
Publication
KDD '26: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, Jeju Island, South Korea, August 9-13
First Page
354
Last Page
365
Identifier
10.1145/3770855.3817870
Publisher
ACM
City or Country
New York
Citation
CHANG, Xueqin; LIU, Ruize; LIU, Qing; ZHENG, Baihua; and GAO, Yunjun.
Approximation and learning-based algorithms for influence maximization in multilayer social networks. (2026). KDD '26: Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2, Jeju Island, South Korea, August 9-13. 354-365.
Available at: https://ink.library.smu.edu.sg/sis_research/11298
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1145/3770855.3817870