Real-time targeted influence maximization for online advertisements

• Main Authors: LI, Yuchen, ZHANG, Dongxiang, TAN, Kian-Lee
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Advertising and Promotion Management; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/4022; https://ink.library.smu.edu.sg/context/sis_research/article/5024/viewcontent/p1070_li.pdf
• Institution: Singapore Management University

Advertising in social network has become a multi-billion dollar industry. A main challenge is to identify key influencers who can effectively contribute to the dissemination 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 studied, 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 Maximization (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 sampling 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 solutions that improve the query processing time by two orders of magnitude over the state-of-the-art solutions, while keeping 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.