2016/05/25 by Hung T. Nguyen, My T. Thai, Nguyen, Hung T. +3 · 4 citations
Physics and Astronomy · Computer Science · #Complex Network Analysis Techniques #Spam and Phishing Detection #Advanced Clustering Algorithms Research
paper · pdf · doi:10.48550/arxiv.1605.07990
Influence Maximization (IM), that seeks a small set of key users who spread\nthe influence widely into the network, is a core problem in multiple domains.\nIt finds applications in viral marketing, epidemic control, and assessing\ncascading failures within complex systems. Despite the huge amount of effort,\nIM in billion-scale networks such as Facebook, Twitter, and World Wide Web has\nnot been satisfactorily solved. Even the state-of-the-art methods such as TIM+\nand IMM may take days on those networks.\n In this paper, we propose SSA and D-SSA, two novel sampling frameworks for\nIM-based viral marketing problems. SSA and D-SSA are up to 1200 times faster\nthan the SIGMOD'15 best method, IMM, while providing the same\n(1-1/e-\ε) approximation guarantee. Underlying our frameworks is an\ninnovative Stop-and-Stare strategy in which they stop at exponential check\npoints to verify (stare) if there is adequate statistical evidence on the\nsolution quality. Theoretically, we prove that SSA and D-SSA are the first\napproximation algorithms that use (asymptotically) minimum numbers of samples,\nmeeting strict theoretical thresholds characterized for IM. The absolute\nsuperiority of SSA and D-SSA are confirmed through extensive experiments on\nreal network data for IM and another topic-aware viral marketing problem, named\nTVM. The source code is available at https://github.com/hungnt55/Stop-and-Stare\n