Influence Maximization And Isolation Methods For Computational Advertising

In the past decades,the extensive use of information technology gives a significant impact on the advertising industry with the advent of Internet,social network and mo-bile device.While making the advertising easier and cheaper than before,these appli-cations also generate a massive amount of user data which provides a big opportunity for the quantitative analysis of advertising strategies.In 2008,computational advertis-ing was issued as an emerging scientific discipline at the ACM-SIAM conference.It aims to increase advertising revenue by leveraging the user data,and has received a lot of attentions from informatics,computer science and communication science.However,most of the existing works only focus on the "one-on-one" marketing and ignore the"one-to-many".To this end,this dissertation will study the influence maximization and isolation problems in advertising from a data-driven perspective,which aims to com-plement the shortage of the studies for "one-on-many" marketing.Specifically,our main contributions can be summarized as follows:1)Introduce a group-based method for Influence MaximizationThe problem of influence maximization on social networks has a lot of applica-tions such as viral marketing,disease prevention and online recommendation.Existing works focus on the selection of most influential individuals and cannot effectively tar-get high-impact groups.However,groups are only natural targets of initial convincing attempts in many real-world scenarios i.e.,Plague Prevention,Marketing Campaign&Promotion and etc.To overcome this issue,this work studies influence spread from a coarse perspective and formalizes the problem of Group-Based Influence Maximization aiming to discover most k-influential groups.In order to model the influence propaga-tion at group granularity,we first mine the association between groups from historical observable data,and propose an association-based group influence cascade model.Based on this model,we give a k-influential group selection algorithm and prove that the algorithm can approximate the optimal solution within the constant factor of(1-1/e).Experimental results on both synthetic and real datasets verify the effective-ness and efficiency of the presented method.2)Introduce influence maximization methods for ads placement in Social Brows-ingSocial browsing is a new retrieval method in social networks.Motivated by the ads placement in this retrieval process,this dissertation introduces Social BrOwsing based InFluence MaximizatioN(SOFN)which aims to maximum increase the visibility of ads by minimizing the retrieval cost of users to ads.Intuitively,our problem is dif-ferent to traditional IM problems as the influence of SOFN is related to the retrieval cost.To solve this problem,we give two algorithms,a dynamic programming and a matrix-based method,to compute the object function;as a result,two corresponding greedy solutions are proposed.In particular,the first greedy is DpSel and its time com-plexity is O(kCn2m);and the second one is called MatrixSel,which is O(n)time faster than the former one.Moreover,we also introduce a pruning method BoundSel to further speed up the selections of MatrixSel.The core idea is to establish the upper bound of the marginal gain for each candidate.Lastly,we conducted experiments on real world network to verify the effectiveness,efficiency,scalability and memory consumption of our methods.The result shows that MatrixSel can beat the baseline in efficiency,scala-bility and memory consumption.3)Introduce trajectory-driven methods for influential billboard placementMany international outdoor advertising companies,such as Larma and APN,only leverage traffic volume to assess the performance of billboards,which often leads to coarse-grained estimations and undesirable ad placement plans.This study starts with the real vehicle trajectory and studies the combination of trajectory-based billboard lo-cation(TIP)for the first time.By exploiting the locality property of billboards' influ-ence,we propose a partitionbased framework PartSel.PartSel partitions U into a set of small clusters,computes the locally influential billboards for each cluster,and merges them to generate the global solution.Since the local solutions can be obtained much more efficient than the global one,PartSel can reduce the computation cost greatly;meanwhile it achieves a non-trivial approximation ratio guarantee.Then we propose a LazyProbe method to further prune billboards with low marginal influence,while achieving the same approximation ratio as PartSel.Experiments on real datasets show that the improvement of PartSel and LazyProbe over TrafficVol exceeds 99%.Not only that,but the research is a general framework for space selection,which can also be extended to the location of car charging piles and convenience stores.4)Introduce blocking methods to limit the spread of online deceptive adsThe spread of deceptive ads through online networks not only threatens the human healthy but also results in loss of financial property.To serve as a reliable platform for spreading critical information,this dissertation tries to reduce the opportunities of users visiting deceptive ads to by embedding k guards in the network,and introduces a novel problem,called Deceptive Ads blocK(DAK).In our problem,we model the spread of deceptive ads by the random walk model,ranther than the cascade models used in the rumor control problems.To our best knowledge,this is the first work that studies the deceptive ads isolation mechanism in computer science.Theoretical analysis shows that DAK is submodular.Therefore,we propose two MC based greedy algorithms that can approximate DAK within a ratio of(1-1/e).Moreover,we further introduce a rank-ing based method RanSel to solve BUK heuristically,which only consumes a linear space to the graph size.The experiments reveal that the effectiveness of our methods outperforms the baseline by a large margin,and our methods can achieve such an ef-fective result in reasonable time.