The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches

Summary: Implementation-agnostic study of Oneshot, Snapshot, RIS analyzes random-solution distributions and the impact of sample size on quality. With enough samples, solutions converge to a unique optimum; Oneshot for limited memory, RIS for large networks, Snapshot for small networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5839
Venue: SIGMOD
Year: 2020
Pagerank: 6.0890538e-05
Overall Rank: 5,786 | 60.31%
DOI: 10.1145/3318464.3380564

Incoming Non-self Citations Over Time

Authors

1. Naoto Ohsaka (NEC Corporation)

BibTeX Citation

@inproceedings{ohsaka_sigmod20,
        title = {{The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches}},
        author = {Ohsaka, Naoto},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380564},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380564},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,315	Analysis of Influence Contribution in Social Advertising	2022	VLDB	5.6470323e-05
8,813	Efficient and Effective Algorithms for Revenue Maximization in Social Advertising	2021	SIGMOD	5.3652634e-05
9,243	Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization	2023	SIGMOD	5.2993405e-05
11,216	Influence Maximization via Vertex Countering	2024	VLDB	5.093636e-05
11,286	Fast and Space-Efficient Parallel Algorithms for Influence Maximization	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 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,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB	0.00011112799
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
3,639	Revisiting the Stop-and-Stare Algorithms for Influence Maximization	2017	VLDB	7.2335041e-05
7,446	Dynamic Influence Analysis in Evolving Networks	2016	VLDB	5.6149944e-05
7,963	Coarsening Massive Influence Networks for Scalable Diffusion Analysis	2017	SIGMOD	5.5177915e-05
8,795	Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks	2018	SIGMOD	5.3704111e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,963	Coarsening Massive Influence Networks for Scalable Diffusion Analysis	2017	SIGMOD
2	2,320	Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened	2020	SIGMOD
3	3,989	Real-Time Influence Maximization on Dynamic Social Streams	2017	VLDB
4	7,771	Triangular Stability Maximization by Influence Spread over Social Networks	2023	VLDB
5	315	Influence Maximization in Near-Linear Time: A Martingale Approach	2015	SIGMOD
6	2,752	Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks	2020	VLDB
7	4,804	Efficient Algorithms for Adaptive Influence Maximization	2018	VLDB
8	1,531	Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study	2017	SIGMOD
9	1,919	Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models	2016	SIGMOD
10	296	A Data-Based Approach to Social Influence Maximization	2012	VLDB