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

• DOI: 10.48550/arxiv.1605.07990
• Publication Date: 2016-01-01
• Authors: Hung T. Nguyen; My T. Thai; Thang N. Dinh
• Keywords: Viral marketing

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