Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

9-2015

Abstract

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.

Discipline

Advertising and Promotion Management | Databases and Information Systems

Research Areas

Data Science and Engineering

Publication

Proceedings of the VLDB Endowment: 41st International Conference on VLDB Endowment, Kohala Coast, Hawaii, 2015 August 31-September 4

Volume

8

First Page

1070

Last Page

1081

Identifier

10.14778/2794367.2794376

Publisher

VLDB Endowment

City or Country

Stanford, CA

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

Additional URL

https://www.vldb.org/pvldb/vol8/p1070-li.pdf

Download

Share

COinS