Efficient Influence Minimization via Node Blocking

Summary: First data-dependent approximation framework for Influence Minimization via node blocking: derive submodular monotone lower/upper bounds via a Sandwich framework and prove computing those bounds is #P-hard. Introduce advanced sampling and martingale-based concentration to cut sample complexity and deliver (1-1/e-ε)-approx algorithms for the bounds, achieving up to two orders of magnitude speedup in experiments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13664
Venue: VLDB
Year: 2024
Pagerank: 5.3251649e-05
Overall Rank: 9,057 | 37.87%
DOI: 10.14778/3675034.3675042

Incoming Non-self Citations Over Time

Authors

1. Jinghao Wang (University of Technology Sydney; Zhejiang Gongshang University)
2. Yanping Wu (University of Technology Sydney)
3. Xiaoyang Wang (University of New South Wales)
4. Ying Zhang (Zhejiang Gongshang University)
5. Lu Qin (University of Technology Sydney)
6. Wenjie Zhang (University of New South Wales)
7. Xuemin Lin (Shanghai Jiao Tong University)

BibTeX Citation

@article{wang_vldb24,
        title = {{Efficient Influence Minimization via Node Blocking}},
        author = {Wang, Jinghao and Wu, Yanping and Wang, Xiaoyang and Zhang, Ying and Qin, Lu and Zhang, Wenjie and Lin, Xuemin},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {10},
        pages = {2501--2513},
        doi = {10.14778/3675034.3675042},
        url = {https://doi.org/10.14778/3675034.3675042},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,731	Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks	2024	VLDB	5.3766157e-05
9,688	Deep Overlapping Community Search via Subspace Embedding	2025	SIGMOD	5.2351259e-05
10,408	Time-Critical Influence Minimization via Node Blocking	2026	SIGMOD	5.093636e-05
10,611	Augmenting Social Influence of Uncertain Seeds via Probabilistic Link Insertion	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
194	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.000259047
315	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021436156
453	Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks	2016	SIGMOD	0.00018145895
1,478	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010651983
2,547	From Competition to Complementarity: Comparative Influence Diffusion and Maximization	2016	VLDB	8.4331576e-05
3,639	Revisiting the Stop-and-Stare Algorithms for Influence Maximization	2017	VLDB	7.2335041e-05
4,725	Efficient Location-Aware Influence Maximization	2014	SIGMOD	6.5373017e-05
6,415	Influence Maximization in Real-World Closed Social Networks	2023	VLDB	5.8830469e-05
7,157	Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties	2022	VLDB	5.6859641e-05
7,771	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB	5.5470467e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	296	A Data-Based Approach to Social Influence Maximization	2012	VLDB
2	5,920	Efficient Approximation Algorithms for Adaptive Seed Minimization	2019	SIGMOD
3	4,804	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB
4	11,409	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD
5	2,260	Online Topic-Aware Influence Maximization	2015	VLDB
6	315	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD
7	2,752	Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks	2020	VLDB
8	7,157	Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties	2022	VLDB
9	10,611	Augmenting Social Influence of Uncertain Seeds via Probabilistic Link Insertion	2026	VLDB
10	10,408	Time-Critical Influence Minimization via Node Blocking	2026	SIGMOD