Beyond Node Influence: Activating Nested Subgraphs in Propagation Networks
ACM Transactions on Knowledge Discovery from Data · 31.08.2026 · 20 (7) · 1-37
DOI: 10.1145/3828169 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Knowledge Discovery from Data, online erschienen am 06.08.2026. Verfasst von Tianyou Gao und 1 weiteren Autor:innen. Die Arbeit nennt 74 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: Japan Society for the Promotion of Science.
Abstract (Originalsprache)
We investigate a practical yet underexplored variant of the influence maximization problem, in which the goal is to activate a given sequence of nested subgraphs as far outward as possible. A subgraph is considered activated if either it reaches a prescribed influence threshold within itself, or a larger subgraph containing it in the nested sequence is activated. We formally define this problem as Structure-Aware Influence Maximization (SAIM) and show that it is NP-hard and its objective function is non-submodular. To tackle SAIM, we propose a decomposition framework that reduces it to a sequence of subproblems, each called Target Subgraph Activation Probability Maximization (TSAPM) . For TSAPM, we propose two oracles: a Sandwich Approximation (SA) framework with data-dependent guarantees, and a heuristic algorithm tailored to the TSAPM objective. Combined with the SA-based oracle, the overall decomposition framework provides a solution-dependent approximation guarantee for the SAIM problem. Extensive experiments on six real-world datasets validate the effectiveness and efficiency of our proposed methods.
Förderung
- Japan Society for the Promotion of Science
Zitieren
APA
Gao, T., & Ito, T. (2026). Beyond Node Influence: Activating Nested Subgraphs in Propagation Networks. ACM Transactions on Knowledge Discovery from Data, 20(7), 1-37. https://doi.org/10.1145/3828169
Vancouver
Gao T, Ito T. Beyond Node Influence: Activating Nested Subgraphs in Propagation Networks. ACM Transactions on Knowledge Discovery from Data. 2026;20(7):1-37. doi:10.1145/3828169
BibTeX
@article{Gao2026,
author = {Gao, Tianyou and Ito, Takayuki},
title = {Beyond Node Influence: Activating Nested Subgraphs in Propagation Networks},
journal = {ACM Transactions on Knowledge Discovery from Data},
year = {2026},
volume = {20},
number = {7},
pages = {1--37},
doi = {10.1145/3828169}
}
EUVIMED