Real-time Targeted Influence Maximization for Online Advertisements

Advertising in social network has become a multi-billion-dollar industry. A main challenge is to identify key in-fluencers who can effectively contribute to the dissemina-tion of information. Although the influence maximization problem, which finds a seed set of k most influential users based on certain propagation models, has been well stud-ied, it is not target-aware and cannot be directly applied to online advertising. In this paper, we propose a new problem, named Keyword-Based Targeted Influence Max-imization (KB-TIM), to find a seed set that maximizes the expected influence over users who are relevant to a given advertisement. To solve the problem, we propose a sam-pling technique based on weighted reverse influence set and achieve an approximation ratio of (1−1/e−ε). To meet the instant-speed requirement, we propose two disk-based solu-tions that improve the query processing time by two orders of magnitude over the state-of-the-art solutions, while keep-ing the theoretical bound. Experiments conducted on two real social networks confirm our theoretical findings as well as the efficiency. Given an advertisement with 5 keywords, it takes only 2 seconds to find the most influential users in a social network with billions of edges. 1