TipTop: (Almost) Exact Solutions for Influence Maximization in Billion-Scale Networks

• DOI: 10.1109/tnet.2019.2898413
• Publication Date: 2019-03-06T20:46:26Z
• Authors: Xiang Li; J. David Smith; Thang N. Dinh; My T. Thai
• Keywords: Maximization; Benchmark (surveying)

In this paper, we study the cost-aware target viral marketing (CTVM) problem, a generalization of influence maximization. CTVM asks for most cost-effective users to relevant users. contrast vast literature, attempt offer exact solutions. As problem is NP-hard, thus, solutions are intractable, propose TipTop, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$(1-\epsilon)$ </tex-math></inline-formula> -optimal solution arbitrary notation="LaTeX">$\epsilon &gt;0$ that scales very large networks, such as Twitter. At heart TipTop lies an innovative technique reduces number samples much possible. This allows us exactly solve on smaller space generated using integer programming. Furthermore, lends tool researchers benchmark their against optimal one in large-scale which currently not available.