DBScholar

Back to papers

Influence Maximization in Near-Linear Time: A Martingale Approach

Summary: Near-linear-time influence maximization using martingale-based estimators. Maintains the same (1-1/e-ε)-approx guarantees as the state of the art, while delivering orders-of-magnitude speedups and broader diffusion-model support on networks up to 1.4B edges. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
ha3719ca0edf1c0bb
Venue
SIGMOD
Year
2015
Pagerank
0.00021567807
Overall Rank
305 | 97.96%
DOI
10.1145/2723372.2723734

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{tang_sigmod15,
        title = {{Influence Maximization in Near-Linear Time: A Martingale Approach}},
        author = {Tang, Youze and Shi, Yanchen and Xiao, Xiaokui},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2723734},
        url = {https://dl.acm.org/doi/10.1145/2723372.2723734},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 51 citing papers.

Rank Citing Paper Year Venue Pagerank
441 Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks 2016 SIGMOD 0.00018233755
1,396 Online Processing Algorithms for Influence Maximization 2018 SIGMOD 0.00010774759
1,545 Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study 2017 SIGMOD 0.00010270407
1,946 Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models 2016 SIGMOD 9.3059083e-05
2,171 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD 8.9117572e-05
2,589 From Competition to Complementarity: Comparative Influence Diffusion and Maximization 2016 VLDB 8.2390055e-05
2,698 Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks 2020 VLDB 8.1020179e-05
3,320 Revisiting the Stop-and-Stare Algorithms for Influence Maximization 2017 VLDB 7.4137064e-05
3,644 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 7.1224321e-05
4,031 Real-Time Influence Maximization on Dynamic Social Streams 2017 VLDB 6.8273933e-05
4,469 Revenue Maximization in Incentivized Social Advertising 2017 VLDB 6.5725381e-05
4,635 Efficient Algorithms for Adaptive Influence Maximization 2018 VLDB 6.4757053e-05
5,209 Pricing Influential Nodes in Online Social Networks 2020 VLDB 6.2146527e-05
5,322 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 6.1663105e-05
5,669 Efficient Approximation Algorithms for Adaptive Seed Minimization 2019 SIGMOD 6.0271116e-05
5,803 Continuous Influence Maximization: What Discounts Should We Offer to Social Network Users? 2016 SIGMOD 5.9716815e-05
5,849 The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches 2020 SIGMOD 5.9530603e-05
5,990 Maximizing Welfare in Social Networks under A Utility Driven Influence Diffusion model 2019 SIGMOD 5.9061293e-05
6,356 CHASSIS: Conformity Meets Online Information Diffusion 2020 SIGMOD 5.78729e-05
6,437 Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties 2022 VLDB 5.7680303e-05
6,489 Clustering Uncertain Graphs 2018 VLDB 5.7517943e-05
6,510 Influence Maximization in Real-World Closed Social Networks 2023 VLDB 5.7449624e-05
6,537 Analysis of Influence Contribution in Social Advertising 2022 VLDB 5.7352831e-05
7,316 Collective Influence Maximization for Multiple Competing Products with an Awareness-to-Influence Model 2021 VLDB 5.5415122e-05
7,604 Dynamic Influence Analysis in Evolving Networks 2016 VLDB 5.4703743e-05
7,624 Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks 2023 SIGMOD 5.4661079e-05
7,933 Triangular Stability Maximization by Influence Spread over Social Networks 2023 VLDB 5.4072642e-05
8,073 Coarsening Massive Influence Networks for Scalable Diffusion Analysis 2017 SIGMOD 5.3795016e-05
8,398 Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation 2023 SIGMOD 5.3237162e-05
8,519 Efficient Influence Minimization via Node Blocking 2024 VLDB 5.3100264e-05
8,628 Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization 2023 SIGMOD 5.2848769e-05
8,765 Maximizing Social Welfare in a Competitive Diffusion Model 2021 VLDB 5.2704231e-05
8,846 Fast and Space-Efficient Parallel Algorithms for Influence Maximization 2024 VLDB 5.2498988e-05
8,986 Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks 2018 SIGMOD 5.2311279e-05
9,007 Efficient and Effective Algorithms for Revenue Maximization in Social Advertising 2021 SIGMOD 5.2250638e-05
9,106 Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee 2024 SIGMOD 5.208561e-05
9,452 Managing Conflicting Interests of Stakeholders in Influencer Marketing 2023 SIGMOD 5.1608635e-05
9,453 Minimum Vertex Augmentation 2021 VLDB 5.1608635e-05
9,692 Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach 2023 SIGMOD 5.1258854e-05
9,993 Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint 2025 VLDB 5.0845476e-05
10,381 Approximating Contribution in Misinformation Mitigation 2027 SIGMOD 4.9605343e-05
10,384 Break Iteration Barrier: Parallelize Priority-Based Graph Processing 2027 SIGMOD 4.9605343e-05
10,672 Time-Critical Influence Minimization via Node Blocking 2026 SIGMOD 4.9605343e-05
10,754 Robust Fair Influence Maximization under Multiple Community Partitions 2026 SIGMOD 4.9605343e-05
10,941 Efficient GPU-Accelerated Adaptive Minimum Cost Seed Selection 2026 VLDB 4.9605343e-05
11,128 Augmenting Social Influence of Uncertain Seeds via Probabilistic Link Insertion 2026 VLDB 4.9605343e-05
11,609 Influence Maximization via Vertex Countering 2024 VLDB 4.9605343e-05
11,657 A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs 2024 VLDB 4.9605343e-05
11,715 Host Profit Maximization: Leveraging Performance Incentives and User Flexibility 2024 VLDB 4.9605343e-05
11,770 Mitigating Filter Bubbles Under a Competitive Diffusion Model 2023 SIGMOD 4.9605343e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
187 Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency 2014 SIGMOD 0.00025945191
290 A Data-Based Approach to Social Influence Maximization 2012 VLDB 0.00021935235
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,171 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD
2 2,589 From Competition to Complementarity: Comparative Influence Diffusion and Maximization 2016 VLDB
3 4,031 Real-Time Influence Maximization on Dynamic Social Streams 2017 VLDB
4 2,698 Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks 2020 VLDB
5 8,765 Maximizing Social Welfare in a Competitive Diffusion Model 2021 VLDB
6 8,519 Efficient Influence Minimization via Node Blocking 2024 VLDB
7 8,073 Coarsening Massive Influence Networks for Scalable Diffusion Analysis 2017 SIGMOD
8 290 A Data-Based Approach to Social Influence Maximization 2012 VLDB
9 4,635 Efficient Algorithms for Adaptive Influence Maximization 2018 VLDB
10 187 Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency 2014 SIGMOD