Cost aware Targeted Viral Marketing in billion scale networks
Online social networks have been one of the most effective platforms for marketing and advertising. Through the "world of mouth" exchanges, so called viral marketing, the influence and product adoption can spread from few key influencers to billions of users in the network. To identify those key influencers, a great amount of work has been devoted for the Influence Maximization (IM) problem that seeks a set of k seed users that maximize the expected influence. Unfortunately, IM encloses two impractical assumptions: 1) any seed user can be acquired with the same cost and 2) all users are equally interested in the advertisement. In this paper, we propose a new problem, called Cost aware Targeted Viral Marketing (CTVM) to find the most cost effective seed users who can influence the most relevant users to the advertisement. Since CTVM is NP hard, we design an efficient (1 1/e e) approximation algorithm, named BCT, to solve the problem in billion scale networks. Comparing with IM algorithms, we show that BCT is both theoretically and experimentally faster than the state of the arts while providing better solution quality. Moreover, we prove that under the Linear Threshold model, BCT is the first sub linear time algorithm for CTVM (and IM) in dense networks. In our experiments with a Twitter dataset, containing 1.46 billions of social relations and 106 millions tweets, BCT can identify key influencers in each trending topic in only few minutes.
IEEE INFOCOM 2016 The 35th Annual IEEE International Conference on Computer Communications