DBScholar

Back to papers

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)

Paper ID
hce56d86f0fc83ae5
Venue
SIGMOD
Year
2014
Pagerank
0.00025522558
Overall Rank
199 | 98.67%
DOI
10.1145/2588555.2593670

Incoming Non-self Citations Over Time

Authors

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 50 of 54 citing papers.

Rank Citing Paper Year Venue Pagerank
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
2,229 Real-time Targeted Influence Maximization for Online Advertisements 2015 VLDB 8.8000047e-05
2,278 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD 8.7070902e-05
2,306 Online Topic-Aware Influence Maximization 2015 VLDB 8.6680219e-05
2,587 From Competition to Complementarity: Comparative Influence Diffusion and Maximization 2016 VLDB 8.2550609e-05
2,697 Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks 2020 VLDB 8.1202432e-05
3,554 Revisiting the Stop-and-Stare Algorithms for Influence Maximization 2017 VLDB 7.2088217e-05
4,047 Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret 2015 VLDB 6.8312773e-05
4,054 Real-Time Influence Maximization on Dynamic Social Streams 2017 VLDB 6.8274063e-05
4,652 Efficient Algorithms for Adaptive Influence Maximization 2018 VLDB 6.485164e-05
4,911 Revenue Maximization in Incentivized Social Advertising 2017 VLDB 6.3580802e-05
5,202 Pricing Influential Nodes in Online Social Networks 2020 VLDB 6.2317454e-05
5,301 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 6.189668e-05
5,383 GetReal: Towards Realistic Selection of Influence Maximization Strategies in Competitive Networks 2015 SIGMOD 6.1543948e-05
5,688 Efficient Approximation Algorithms for Adaptive Seed Minimization 2019 SIGMOD 6.0356384e-05
5,823 Continuous Influence Maximization: What Discounts Should We Offer to Social Network Users? 2016 SIGMOD 5.9821401e-05
5,872 The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches 2020 SIGMOD 5.9639045e-05
5,951 Shortest Paths and Centrality in Uncertain Networks 2021 VLDB 5.9366845e-05
6,506 Influence Maximization in Real-World Closed Social Networks 2023 VLDB 5.7608239e-05
7,294 Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties 2022 VLDB 5.5635731e-05
7,310 Collective Influence Maximization for Multiple Competing Products with an Awareness-to-Influence Model 2021 VLDB 5.5566021e-05
7,445 Analysis of Influence Contribution in Social Advertising 2022 VLDB 5.5247739e-05
7,586 Dynamic Influence Analysis in Evolving Networks 2016 VLDB 5.4896843e-05
7,589 Spheres of Influence for More Effective Viral Marketing 2016 SIGMOD 5.4882381e-05
7,742 Towards Best Region Search for Data Exploration 2016 SIGMOD 5.4614459e-05
7,913 Triangular Stability Maximization by Influence Spread over Social Networks 2023 VLDB 5.4277727e-05
8,127 Coarsening Massive Influence Networks for Scalable Diffusion Analysis 2017 SIGMOD 5.3940983e-05
8,316 ThriftLLM: On Cost-Effective Selection of Large Language Models for Classification Queries 2025 VLDB 5.3561732e-05
8,375 Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation 2023 SIGMOD 5.3439079e-05
8,496 Efficient Influence Minimization via Node Blocking 2024 VLDB 5.3301662e-05
8,603 Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization 2023 SIGMOD 5.3049212e-05
8,702 Community Level Diffusion Extraction 2015 SIGMOD 5.2905577e-05
8,958 Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks 2018 SIGMOD 5.250435e-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,416 Minimum Vertex Augmentation 2021 VLDB 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,600 Time-Critical Influence Minimization via Node Blocking 2026 SIGMOD 4.9793485e-05
10,682 Robust Fair Influence Maximization under Multiple Community Partitions 2026 SIGMOD 4.9793485e-05
10,871 Efficient GPU-Accelerated Adaptive Minimum Cost Seed Selection 2026 VLDB 4.9793485e-05
11,058 Augmenting Social Influence of Uncertain Seeds via Probabilistic Link Insertion 2026 VLDB 4.9793485e-05
11,554 Influence Maximization via Vertex Countering 2024 VLDB 4.9793485e-05
11,604 A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs 2024 VLDB 4.9793485e-05
Previous Page 1 / 2 Next

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
299 A Data-Based Approach to Social Influence Maximization 2012 VLDB 0.00021812174
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,757 Maximizing Social Welfare in a Competitive Diffusion Model 2021 VLDB
2 9,963 Fast and Space-Efficient Parallel Algorithms for Influence Maximization 2024 VLDB
3 2,697 Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks 2020 VLDB
4 299 A Data-Based Approach to Social Influence Maximization 2012 VLDB
5 4,054 Real-Time Influence Maximization on Dynamic Social Streams 2017 VLDB
6 2,306 Online Topic-Aware Influence Maximization 2015 VLDB
7 4,652 Efficient Algorithms for Adaptive Influence Maximization 2018 VLDB
8 2,278 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD
9 8,127 Coarsening Massive Influence Networks for Scalable Diffusion Analysis 2017 SIGMOD
10 320 Influence Maximization in Near-Linear Time: A Martingale Approach 2015 SIGMOD