EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Beyond Node Influence: Activating Nested Subgraphs in Propagation Networks

Tianyou Gao, Takayuki Ito

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →