← 研踪 PaperTrailarXiv:2611.15949 · v1
Efficient Influence Minimization via Source-Integrated Sampling
首次提交 2026-11-12 03:41
版本更新 2026-11-12 03:41
雷达观测 2026-11-13 14:16
摘要
Influence minimization by node blocking is a fundamental problem in graph data management that seeks a small set of vertices whose removal minimizes the expected spread from a fixed source set. It supports decisions about where to intervene in large interaction networks to control harmful propagation, such as the spread of rumors and infectious diseases. Under the Independent Cascade (IC) model, selecting blockers requires comparing a large number of candidate sets, and estimating their effects on propagation can be costly. We propose SIG (Source-Integrated Greedy), a sampling framework for efficiently finding high-quality approximate solutions. Our key idea is to group the possible sets of neighbors directly activated by the sources according to their effects on blocker selection. SIG represents these groups in a compact weighted tree and computes their probabilities directly, allowing each sample to account for all source outcomes without enumerating them. We prove that SIG produces unbiased estimates of the lower-bound objective without increasing variance for fixed blocking plans, and establish a high-probability quality guarantee through independent validation. Extensive experiments on real-world networks show that SIG has the lowest mean total running time in all main comparisons, with speedups of up to 583x over the fastest baseline. SIG produces solutions competitive with those of prior methods and achieves the highest influence reduction in multiple settings, including on many of the largest networks, where several baselines exceed the runtime limit. Additional experiments show that SIG maintains consistently low running times as graph size and the blocking budget increase, while delivering stronger blocking solutions at larger budgets.
作者备注：14 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-12 03:41 · 最新观测版本
Efficient Influence Minimization via Source-Integrated Sampling
Influence minimization by node blocking is a fundamental problem in graph data management that seeks a small set of vertices whose removal minimizes the expected spread from a fixed source set. It supports decisions about where to intervene in large interaction networks to control harmful propagation, such as the spread of rumors and infectious diseases. Under the Independent Cascade (IC) model, selecting blockers requires comparing a large number of candidate sets, and estimating their effects on propagation can be costly. We propose SIG (Source-Integrated Greedy), a sampling framework for efficiently finding high-quality approximate solutions. Our key idea is to group the possible sets of neighbors directly activated by the sources according to their effects on blocker selection. SIG represents these groups in a compact weighted tree and computes their probabilities directly, allowing each sample to account for all source outcomes without enumerating them. We prove that SIG produces unbiased estimates of the lower-bound objective without increasing variance for fixed blocking plans, and establish a high-probability quality guarantee through independent validation. Extensive experiments on real-world networks show that SIG has the lowest mean total running time in all main comparisons, with speedups of up to 583x over the fastest baseline. SIG produces solutions competitive with those of prior methods and achieves the highest influence reduction in multiple settings, including on many of the largest networks, where several baselines exceed the runtime limit. Additional experiments show that SIG maintains consistently low running times as graph size and the blocking budget increase, while delivering stronger blocking solutions at larger budgets.
查看此版本解读 →查看此版本原文 ↗