Skip to content
Spread & networksDetection methods graph algorithmssamplingcascade models

Efficient Influence Minimization via Source-Integrated Sampling

arXiv cs.SI · 2026

In brief

This paper proposes SIG (Source-Integrated Greedy), a sampling framework for influence minimization—selecting nodes to block in a network to minimize harmful information spread. SIG groups source-edge outcomes by influence on targets, represents these groups in compact weighted trees, and evaluates blocking plans efficiently without enumerating all possibilities. Experiments show SIG achieves 583× speedups over existing baselines while maintaining high-quality solutions across large social networks.

Summary figure for Efficient Influence Minimization via Source-Integrated Sampling

Contributions

  • A sampling framework (SIG) that groups source-edge outcomes by their effects on blocked targets within weighted trees, enabling efficient estimation of blocking plan quality without exponential enumeration.
  • Unbiased estimation of lower-bound objectives via source-integration; high-probability bounds on solution quality for fixed blocking plans.
  • Extensive experiments on real-world networks (Twitter, YouTube, email, social graphs) showing SIG runs faster than every baseline with speedups up to 583× and achieves strong influence reduction across multiple settings.
  • Analysis of SIG's sensitivity to parameters (approximation ratio, sample size) and ablation studies demonstrating robustness to design choices.

Method

The influence minimization problem under the Independent Cascade (IC) model seeks to select k nodes to block such that the expected number of nodes reachable from a fixed source set is minimized. Blocking a node removes it and its incident edges; the challenge is that the IC model requires averaging over all possible propagation outcomes, making brute-force enumeration infeasible.

SIG addresses this in three stages:

  1. Build weighted samples: For each of j training rounds, sample live edges and summarize which nodes from the source set can reach the targets via positive-probability edges. Represent this as a weighted tree rooted at each target, storing probabilities that targets are reachable given each blocking choice.

  2. Select blockers: Greedily pick vertices that maximize the marginal reduction in expected reachability, using the weighted trees to estimate influence reduction without re-sampling.

  3. Validate and stop: Draw independent samples from the reverse reachability graph to bound the selected set's true influence reduction and the optimum. If bounds certify the solution meets the requested approximation ratio, stop; otherwise increase sample size.

The key innovation is representing source-edge outcomes compactly within weighted trees: each fixed target and live-edge configuration defines a path structure in a single tree, allowing one sample to score many candidate blocking sets without exponential blowup.

Results

On seven SNAP networks ranging from 6,301 to 1.13M vertices:

  • Running time: SIG achieves the lowest total time in all main comparisons, with speedups up to 583× over the fastest completing baseline (at budget k=20). At k=100, SIG takes 2.30s vs. 1,531.8s for SandIMIN.
  • Influence reduction: SIG reaches at least 97.1% of the highest estimated influence reduction in every comparison, matching or exceeding prior methods on all tested networks.
  • Scalability: Speedup increases from 1.47× on small graphs (6,301 vertices) to 583× on large ones; SIG maintains low running times as budget increases (20 to 1,000).
  • Solution quality: On social networks (Twitter, YouTube) with large blocking budgets, SIG delivers stronger solutions than greedy baselines while maintaining significantly lower running times.

Notes

Strengths: The source-integration insight is novel—grouping outcomes by their path structure in trees is elegant and enables significant computational savings. Extensive experiments on real networks with multiple baselines, parameter sensitivity studies, and ablations. Clear presentation of the algorithm and theoretical bounds.

Weaknesses: Paper focuses on the algorithmic problem (how to select blockers efficiently) rather than the information integrity problem (which information should be blocked, how to detect misinformation). The IC model is a simplification; real propagation involves homophily, bot activity, and content visibility algorithms that may not match uniform edge probabilities. Experiments use synthetic source sets; real misinformation detection requires identifying which content/accounts warrant blocking.

Open questions: How does SIG perform when edge probabilities are learned from data and subject to model uncertainty? Can the framework handle time-varying or adaptive networks where information sources evolve during intervention? Integration with fact-checking or credibility assessment to prioritize which information sources should be blocked.

Similar papers

Summarized from the full text. Added 2026-11-15 by weekly discovery. Every statement on this page traces back to the source.