Fast and Space-Efficient Parallel Algorithms for Influence Maximization

Summary: PaC-IM combines sketch compression for independent-cascade simulations with parallel data structures for greedy seed selection. It scales IM to 978M-vertex, 7.5B-edge graphs, delivering 5–18× speedups and substantial memory savings over parallel systems. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 13788
Venue: VLDB
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,286 | 22.57%
DOI: 10.14778/3632093.3632104

Incoming Non-self Citations Over Time

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

Authors

1. Letong Wang (University of California Riverside)
2. Xiangyun Ding (University of California Riverside)
3. Yan Gu (University of California Riverside)
4. Yihan Sun (University of California Riverside)

BibTeX Citation

@article{wang_vldb24,
        title = {{Fast and Space-Efficient Parallel Algorithms for Influence Maximization}},
        author = {Wang, Letong and Ding, Xiangyun and Gu, Yan and Sun, Yihan},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {3},
        pages = {400--413},
        doi = {10.14778/3632093.3632104},
        url = {https://doi.org/10.14778/3632093.3632104},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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
1,531	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD	0.00010472526
2,320	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD	8.7576221e-05
2,752	Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks	2020	VLDB	8.1648436e-05
3,850	Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization	2021	VLDB	7.0742748e-05
5,786	The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches	2020	SIGMOD	6.0890538e-05
6,415	Influence Maximization in Real-World Closed Social Networks	2023	VLDB	5.8830469e-05
7,181	Collective Influence Maximization for Multiple Competing Products with an Awareness-to-Influence Model	2021	VLDB	5.6794437e-05
7,315	Analysis of Influence Contribution in Social Advertising	2022	VLDB	5.6470323e-05
7,862	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	5.5302333e-05
9,396	Hindering Influence Diffusion of Community	2022	SIGMOD	5.2755515e-05
11,394	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,260	Online Topic-Aware Influence Maximization	2015	VLDB
2	315	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD
3	1,919	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD
4	2,320	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD
5	11,409	Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach	2023	SIGMOD
6	4,804	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB
7	296	A Data-Based Approach to Social Influence Maximization	2012	VLDB
8	3,989	Real-Time Influence Maximization on Dynamic Social Streams	2017	VLDB
9	194	Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency	2014	SIGMOD
10	7,963	Coarsening Massive Influence Networks for Scalable Diffusion Analysis	2017	SIGMOD