Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
Summary: TIM bridges theory and practice for influence maximization under IC, LT, and triggering models. Near-optimal O((k+l)(n+m) log n / e^2) time with (1-1/e - e)-approx and practical heuristics; scales to very large graphs on commodity hardware, beating prior guaranteed methods by orders of magnitude. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Youze Tang (Nanyang Technological University)
- 2. Xiaokui Xiao (Nanyang Technological University)
- 3. Yanchen Shi (Nanyang Technological University)
BibTeX Citation
@inproceedings{tang_sigmod14,
title = {{Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency}},
author = {Tang, Youze and Xiao, Xiaokui and Shi, Yanchen},
series = {{SIGMOD} '14},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/2588555.2593670},
url = {https://dl.acm.org/doi/10.1145/2588555.2593670},
year = {2014}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 53 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,403 | Mitigating Filter Bubbles Under a Competitive Diffusion Model | 2023 | SIGMOD | 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 1 of 1 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 296 | A Data-Based Approach to Social Influence Maximization | 2012 | VLDB | 0.00022220351 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 8,595 | Maximizing Social Welfare in a Competitive Diffusion Model | 2021 | VLDB |
| 2 | 11,286 | Fast and Space-Efficient Parallel Algorithms for Influence Maximization | 2024 | VLDB |
| 3 | 2,752 | Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks | 2020 | VLDB |
| 4 | 296 | A Data-Based Approach to Social Influence Maximization | 2012 | VLDB |
| 5 | 3,989 | Real-Time Influence Maximization on Dynamic Social Streams | 2017 | VLDB |
| 6 | 2,260 | Online Topic-Aware Influence Maximization | 2015 | VLDB |
| 7 | 4,804 | Efficient Algorithms for Adaptive Influence Maximization | 2018 | VLDB |
| 8 | 2,320 | Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened | 2020 | SIGMOD |
| 9 | 7,963 | Coarsening Massive Influence Networks for Scalable Diffusion Analysis | 2017 | SIGMOD |
| 10 | 315 | Influence Maximization in Near-Linear Time: A Martingale Approach | 2015 | SIGMOD |