Augmenting Social Influence of Uncertain Seeds via Probabilistic Link Insertion

Summary: Introduces IMAUS, inserting links incident to probabilistically active seeds to maximize diffusion—an NP-hard, non-submodular problem. A sandwich framework uses RIS-based unbiased submodular bounds and greedy optimization, scaling to billion-edge graphs with (1−1/e−ε) guarantees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14557
Venue: VLDB
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,611 | 27.20%
DOI: 10.14778/3785297.3785314

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Xiaolong Chen (Hong Kong University of Science and Technology)
2. Jing Tang (Hong Kong University of Science and Technology)

BibTeX Citation

@article{chen_vldb26,
        title = {{Augmenting Social Influence of Uncertain Seeds via Probabilistic Link Insertion}},
        author = {Chen, Xiaolong and Tang, Jing},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {4},
        pages = {753--766},
        doi = {10.14778/3785297.3785314},
        url = {https://doi.org/10.14778/3785297.3785314},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
5,710	Continuous Influence Maximization: What Discounts Should We Offer to Social Network Users?	2016	SIGMOD	6.1141071e-05
6,415	Influence Maximization in Real-World Closed Social Networks	2023	VLDB	5.8830469e-05
7,771	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB	5.5470467e-05
9,057	Efficient Influence Minimization via Node Blocking	2024	VLDB	5.3251649e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,547	From Competition to Complementarity: Comparative Influence Diffusion and Maximization	2016	VLDB
2	11,409	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD
3	10,809	Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint	2025	VLDB
4	2,320	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD
5	8,795	Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks	2018	SIGMOD
6	7,771	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB
7	6,415	Influence Maximization in Real-World Closed Social Networks	2023	VLDB
8	2,260	Online Topic-Aware Influence Maximization	2015	VLDB
9	2,752	Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks	2020	VLDB
10	9,057	Efficient Influence Minimization via Node Blocking	2024	VLDB