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: 12246
Venue: VLDB
Year: 2020
Pagerank: 8.1648436e-05
Overall Rank: 2,752 | 81.13%
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 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,408	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	5.8842681e-05
6,415	Influence Maximization in Real-World Closed Social Networks	2023	VLDB	5.8830469e-05
7,315	Analysis of Influence Contribution in Social Advertising	2022	VLDB	5.6470323e-05
7,810	Minimizing the Regret of an Influence Provider	2021	SIGMOD	5.5393525e-05
8,813	Efficient and Effective Algorithms for Revenue Maximization in Social Advertising	2021	SIGMOD	5.3652634e-05
8,913	Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee	2024	SIGMOD	5.3483178e-05
9,242	Managing Conflicting Interests of Stakeholders in Influencer Marketing	2023	SIGMOD	5.2993405e-05
9,849	Unconstrained Submodular Maximization with Modular Costs: Tight Approximation and Application to Profit Maximization	2021	VLDB	5.2094004e-05
10,809	Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint	2025	VLDB	5.093636e-05
11,286	Fast and Space-Efficient Parallel Algorithms for Influence Maximization	2024	VLDB	5.093636e-05
11,409	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD	5.093636e-05
11,734	Towards an Efficient Weighted Random Walk Domination	2021	VLDB	5.093636e-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
194	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD	0.000259047
296	A Data-Based Approach to Social Influence Maximization	2012	VLDB	0.00022220351
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
1,531	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00010472526
1,919	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD	9.4850778e-05

Semantically Similar Papers

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