# Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks

arXiv: https://arxiv.org/abs/1605.07990 · HTML: https://mlsanity.com/paper/1605.07990/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2016.

## Built on by (most cited first, 15 of 15)

- [Deep Graph Representation Learning and Optimization for Influence Maximization](https://mlsanity.com/paper/2305.02200/) (2023)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning](https://mlsanity.com/paper/2210.07500/) (2022)
- [IM-META: Influence Maximization Using Node Metadata in Networks With Unknown Topology](https://mlsanity.com/paper/2106.02926/) (2021)
- [FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks](https://mlsanity.com/paper/2111.00463/) (2021)
- [Influence Maximization via Graph Neural Bandits](https://mlsanity.com/paper/2406.12835/) (2024)
- [Graph Representation Learning for Popularity Prediction Problem: A Survey](https://mlsanity.com/paper/2203.07632/) (2022)
- [Finding Influencers in Complex Networks: An Effective Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2309.07153/) (2023)
- [DSCom: A Data-Driven Self-Adaptive Community-Based Framework for Influence Maximization in Social Networks](https://mlsanity.com/paper/2311.11080/) (2023)
- [MIM-Reasoner: Learning with Theoretical Guarantees for Multiplex Influence Maximization](https://mlsanity.com/paper/2402.16898/) (2024)
- [DQ4FairIM: Fairness-aware Influence Maximization using Deep Reinforcement Learning](https://mlsanity.com/paper/2512.00545/) (2025)
- [Online Influence Maximization: Concept and Algorithm](https://mlsanity.com/paper/2312.00099/) (2023)
- [Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem](https://mlsanity.com/paper/2511.00869/) (2025)
- [Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search](https://mlsanity.com/paper/2608.08406/) (2026)
- [Network World Models as Environments for Algorithm Design on Complex Systems](https://mlsanity.com/paper/2610.01048/) (2026)

## Abstract (arXiv)

Influence Maximization (IM), that seeks a small set of key users who spread the influence widely into the network, is a core problem in multiple domains. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, IM in billion-scale networks such as Facebook, Twitter, and World Wide Web has not been satisfactorily solved. Even the state-of-the-art methods such as TIM+ and IMM may take days on those networks. In this paper, we propose SSA and D-SSA, two novel sampling frameworks for IM-based viral marketing problems. SSA and D-SSA are up to 1200 times faster than the SIGMOD'15 best method, IMM, while providing the same (1-1/e-ε) approximation guarantee. Underlying our frameworks is an innovative Stop-and-Stare strategy in which they stop at exponential check points to verify (stare) if there is adequate statistical evidence on the solution quality. Theoretically, we prove that SSA and D-SSA are the first approximation algorithms that use (asymptotically) minimum numbers of samples, meeting strict theoretical thresholds characterized for IM. The absolute superiority of SSA and D-SSA are confirmed through extensive experiments on real network data for IM and another topic-aware viral marketing problem, named TVM. The source code is available at https://github.com/hungnt55/Stop-and-Stare