Bring Order into the Samples: A Novel Scalable Method for Influence Maximization

摘要: As a key problem in viral marketing, influence maximization has been extensively studied the literature. Given positive integer $k$ , social network $\mathcal {G}$ and certain propagation model, it aims to find set of nodes that have largest spread. The state-of-the-art method IMM is based on reverse sampling (RIS) framework. By using martingale technique, greatly outperforms previous methods efficiency. However, still limitations scalability due high overhead deciding tight sample size. In this paper, instead spending effort size, we present novel bottom- k sketch RIS framework, namely BKRIS, which brings order samples into applying can derive early termination conditions significantly accelerate seed selection procedure. Moreover, provide cost-effective proper size bound quality returned result. addition, several optimization techniques reduce cost generating samples’ efficiently deal with worst-case scenario. We demonstrate efficiency effectiveness proposed over 10 real world datasets. Compared approach, BKRIS achieve up two orders magnitude speedup almost same dataset 1.8 billion edges, return 50 seeds 1.3 seconds 5,000 36.6 seconds. It takes 55.32 second 3,664.97 seconds, respectively.