Database Paper Browser

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
4955
Venue
SIGMOD
Year
2015
Pagerank
0.00026987013
Overall Rank
338 | 97.66%
DOI
10.1145/2723372.2723734

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank Citing Paper Year Venue Pagerank
437 Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks 2016 SIGMOD 0.00023237348
1,652 Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study 2017 SIGMOD 0.00010999442
1,798 Online Processing Algorithms for Influence Maximization 2018 SIGMOD 0.00010500792
2,226 Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models 2016 SIGMOD 9.2532857e-05
2,375 From Competition to Complementarity: Comparative Influence Diffusion and Maximization 2016 VLDB 8.9401216e-05
2,485 Efficient Algorithms for Budgeted Influence Maximization on Massive Social Networks 2020 VLDB 8.6657901e-05
2,668 Influence Maximization Revisited: Efficient Reverse Reachable Set Generation with Bound Tightened 2020 SIGMOD 8.3432296e-05
3,622 Efficient and Effective Algorithms for Clustering Uncertain Graphs 2019 VLDB 6.9021704e-05
4,219 Revisiting the Stop-and-Stare Algorithms for Influence Maximization 2017 VLDB 6.3432726e-05
4,284 CHASSIS: Conformity Meets Online Information Diffusion 2020 SIGMOD 6.2824978e-05
4,369 Real-Time Influence Maximization on Dynamic Social Streams 2017 VLDB 6.2399378e-05
5,083 Revenue Maximization in Incentivized Social Advertising 2017 VLDB 5.705337e-05
5,092 Efficient Algorithms for Adaptive Influence Maximization 2018 VLDB 5.6987819e-05
5,170 Pricing Influential Nodes in Online Social Networks 2020 VLDB 5.6416844e-05
5,355 Discovering Your Selling Points: Personalized Social Influential Tags Exploration 2017 SIGMOD 5.5518336e-05
5,940 Maximizing Welfare in Social Networks under A Utility Driven Influence Diffusion model 2019 SIGMOD 5.2600149e-05
6,091 Continuous Influence Maximization: What Discounts Should We Offer to Social Network Users? 2016 SIGMOD 5.2141312e-05
6,159 The Solution Distribution of Influence Maximization: A High-level Experimental Study on Three Algorithmic Approaches 2020 SIGMOD 5.1751218e-05
6,181 Efficient Approximation Algorithms for Adaptive Seed Minimization 2019 SIGMOD 5.1641945e-05
6,522 Clustering Uncertain Graphs 2018 VLDB 5.0230003e-05
6,669 Influence Maximization in Real-World Closed Social Networks 2023 VLDB 4.9629357e-05
7,266 Misinformation Mitigation under Differential Propagation Rates and Temporal Penalties 2022 VLDB 4.7774097e-05
7,320 Dynamic Influence Analysis in Evolving Networks 2016 VLDB 4.7579928e-05
7,393 Collective Influence Maximization for Multiple Competing Products with an Awareness-to-Influence Model 2021 VLDB 4.7373814e-05
7,450 Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks 2023 SIGMOD 4.7218383e-05
7,800 Triangular Stability Maximization by Influence Spread over Social Networks 2023 VLDB 4.6437574e-05
7,903 Coarsening Massive Influence Networks for Scalable Diffusion Analysis 2017 SIGMOD 4.6170606e-05
7,938 Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation 2023 SIGMOD 4.6089395e-05
8,007 Analysis of Influence Contribution in Social Advertising 2022 VLDB 4.604154e-05
8,589 Maximizing Social Welfare in a Competitive Diffusion Model 2021 VLDB 4.4853244e-05
8,626 Finding Seeds and Relevant Tags Jointly: For Targeted Influence Maximization in Social Networks 2018 SIGMOD 4.4774498e-05
8,737 Efficient Approximation Algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee 2024 SIGMOD 4.4520434e-05
8,808 Efficient and Effective Algorithms for Revenue Maximization in Social Advertising 2021 SIGMOD 4.4413146e-05
8,904 Efficient Influence Minimization via Node Blocking 2024 VLDB 4.4229886e-05
9,094 Managing Conflicting Interests of Stakeholders in Influencer Marketing 2023 SIGMOD 4.3925641e-05
9,095 Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization 2023 SIGMOD 4.3925641e-05
9,096 Minimum Vertex Augmentation 2021 VLDB 4.3925641e-05
10,120 Time-Critical Influence Minimization via Node Blocking 2026 SIGMOD 4.1905499e-05
10,206 Robust Fair Influence Maximization under Multiple Community Partitions 2026 SIGMOD 4.1905499e-05
10,325 Augmenting Social Influence of Uncertain Seeds via Probabilistic Link Insertion 2026 VLDB 4.1905499e-05
10,546 Efficient and Effective Algorithms for A Family of Influence Maximization Problems with A Matroid Constraint 2025 VLDB 4.1905499e-05
11,008 Influence Maximization via Vertex Countering 2024 VLDB 4.1905499e-05
11,075 A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs 2024 VLDB 4.1905499e-05
11,083 Fast and Space-Efficient Parallel Algorithms for Influence Maximization 2024 VLDB 4.1905499e-05
11,142 Host Profit Maximization: Leveraging Performance Incentives and User Flexibility 2024 VLDB 4.1905499e-05
11,204 Mitigating Filter Bubbles Under a Competitive Diffusion Model 2023 SIGMOD 4.1905499e-05
11,210 Efficient Algorithm for Budgeted Adaptive Influence Maximization: An Incremental RR-set Update Approach 2023 SIGMOD 4.1905499e-05
11,468 To Intervene or Not To Intervene: Cost based Intervention for Combating Fake News 2021 SIGMOD 4.1905499e-05
Previous Page 1 / 1 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
90 A Data-Based Approach to Social Influence Maximization 2012 VLDB 0.00052018478
180 Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency 2014 SIGMOD 0.00037101192
Previous Page 1 / 1 Next

Semantically Similar Papers