Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks

Summary: Improves BIM’s guarantee to ~0.355−ε (from ~0.316−ε). Combines reverse sampling with tighter greedy bounds and seed-set-independent selection strategies, yielding substantially faster influence maximization on massive networks. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h6883d1bca46037ab
Venue: VLDB
Year: 2020
Pagerank: 8.1202432e-05
Overall Rank: 2,697 | 81.87%
DOI: 10.14778/3397240.3397244

Incoming Non-self Citations Over Time

Authors

1. Song Bian (Chinese University of Hong Kong)
2. Qintian Guo (Chinese University of Hong Kong)
3. Sibo Wang (Chinese University of Hong Kong)
4. Jeffrey Xu Yu (Chinese University of Hong Kong)

BibTeX Citation

@article{bian_vldb20,
        title = {{Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks}},
        author = {Bian, Song and Guo, Qintian and Wang, Sibo and Yu, Jeffrey Xu},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {9},
        pages = {1498--1510},
        doi = {10.14778/3397240.3397244},
        url = {https://doi.org/10.14778/3397240.3397244},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,506	Influence Maximization in Real-World Closed Social Networks	2023	VLDB	5.7608239e-05
6,526	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	5.7559739e-05
7,445	Analysis of Influence Contribution in Social Advertising	2022	VLDB	5.5247739e-05
7,971	Minimizing the Regret of an Influence Provider	2021	SIGMOD	5.4150644e-05
8,978	Efficient and Effective Algorithms for Revenue Maximization in Social Advertising	2021	SIGMOD	5.2448813e-05
9,076	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	5.2283159e-05
9,415	Managing Conflicting Interests of Stakeholders in Influencer Marketing	2023	SIGMOD	5.1804375e-05
9,952	Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint	2025	VLDB	5.1038322e-05
9,963	Fast and Space-Efficient Parallel Algorithms for Influence Maximization	2024	VLDB	5.1038322e-05
10,033	Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization	2021	VLDB	5.0925155e-05
10,871	Efficient GPU-Accelerated Adaptive Minimum Cost Seed Selection	2026	VLDB	4.9793485e-05
11,723	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD	4.9793485e-05
12,037	Towards an Efficient Weighted Random Walk Domination	2021	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
199	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.00025522558
299	A Data-Based Approach to Social Influence Maximization	2012	VLDB	0.00021812174
320	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD	0.00021143147
455	Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks	2016	SIGMOD	0.0001796092
1,474	Online Processing Algorithms for Influence Maximization	2018	SIGMOD	0.00010556999
1,553	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.0001027493
1,964	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD	9.3059474e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,819	Efficient Location-Aware Influence Maximization	2014	SIGMOD
2	2,306	Online Topic-Aware Influence Maximization	2015	VLDB
3	299	A Data-Based Approach to Social Influence Maximization	2012	VLDB
4	320	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD
5	199	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD
6	5,688	Efficient Approximation Algorithms for Adaptive Seed Minimization	2019	SIGMOD
7	8,496	Efficient Influence Minimization via Node Blocking	2024	VLDB
8	2,278	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD
9	4,652	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB
10	11,723	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD