近十年来,Internet、社会网络、手机等信息技术的使用对广告行业产生了重大而深远的影响。它们不仅使广告的投放变得更容易、更便宜,其产生的大量用户数据也为广告策略的定量分析提供了机会。2008年在ACM-SIAM研讨会上提出的计算广告学,旨在通过用户数据提高广告收益,引起了信息学、计算机科学和传播学的高度重视。目前,相关研究大都关注于“一对一”场景下的广告投放,而对“一对多”投放研究不足。为此,本文将从数据驱动的角度,对广告“一对多”投放中的影响最大化和影响阻隔问题进行研究。本论文主要贡献可概括如下:1)提出了面向团体的影响最大化方法在社会网络中,影响最大化问题在病毒营销、疾病防治和在线推荐等多个方面具有较强的应用背景。现有工作主要关注高影响力个体的选择,不能有效的定位高影响力社群团体。然而,高影响力社群的发现在区域疾病防治和户外商业活动组织等方面有重要的作用。针对该问题,本文从团体粒度研究了影响传播,并形式化定义了面向团体的影响力最大化问题,旨在发现网络中具有影响力的top-k社群团体。为描述团体粒度的影响传播过程,我们从团体间的影响关联入手,首次提出了一种基于关联的团体影响级联模型。而后,我们在该模型上给出了一种近似的top-k影响力团体选择算法,并证明该算法能返回(1-1/e)的最优解。在人工数据集和真实数据集的实验结果显示,我们的方法能高效选择具有影响力的团体组合。2)提出了基于社会化浏览的影响最大化方法社会化浏览是由社会网络产生的一种全新的信息检索方式。针对该场景下的广告投放应用,本文提出基于社会化浏览的影响最大化问题(Social BrOwsing based InFluence MaximizatioN,SOFN)。与传统 IM 问题不同的是,SOFN 问题的影响力定义与用户访问广告的代价有关,其目的在于通过减少用户搜索广告的代价来最大化提高广告在检索中曝光率。为求解该问题,本文分别利用动态规划算法和矩阵运算对目标函数进行计算,并相应给出了两种贪心近似算法DpSel、MatrixSel。其时间复杂度分别为O(kCn2m)、O(kCnm)。此外,我们还通过建立候选结点边际收益的上界,提出了剪枝算法BoundSel。该算法能够显著加速MatrixSel算法的贪心过程。本研究在多个真实网络上进行了实验:分别从效果、效率、可扩展性、内存消耗几个方面对本文提出的算法进行了验证。结果显示,MatrixSel算法在时间开销和空间开销上明显好于度数优先算法和采样算法。3)提出了轨迹驱动的高影响力广告牌选址方法许多国际户外广告公司,如Larma和APN,利用车流量来评估广告牌的影响力。然而,这种做法常导致粗粒度估计和不理想的广告投放方案。本研究从真实车辆运行轨迹入手,首次研究了轨迹驱动的高影响力广告牌选址问题(TIP),旨在最大化广告牌对轨迹影响。受制于广告牌定价不同和其间影响力重叠两方面的挑战,TIP被证明是NP-hard的。为在有限时间内求解该问题,我们提出了基于划分的框架PartSel。PartSel首先利用车辆轨迹的局部特征将广告牌划分为影响相对独立的集合,而后采用枚举与贪心的组合方法对各个集合进行局部选择,最后通过动态规划算法将局部解合并成全局解。由于局部解相较全局解更容易计算,PartSel大大降低了计算开销,同时还能提供常数因子的近似保证。此外,我们还在PartSel的基础上进一步提出了 LazyProbe方法。该方法通对低边际影响的广告牌进行剪枝来加速PartSel的计算,且并不影响被优化算法的近似性能。实验表明,该方法的效果相对基于车流量的选址方法提升了 99%。而且该方法是一个空间选址的通用框架,可推广到解决汽车充电桩和便利店的选址问题中。4)提出了在线虚假广告影响阻隔方法在线网络的虚假广告的传播不仅导致金融财产的损失,而且可能威胁人身安全。为构建可靠的信息传播平台,本文采用建立(k个)保护结点方式来最大化阻隔用户对虚假广告的浏览,并提出了在线虚假广告影响阻隔问题(DeceptiveAds blocKing Placement,DAK)。与谣言控制的研究不同,在DAK问题中虚假广告对用户的影响是通过随机游走模型描述的,而非影响级联模型。据我们所知,本文是第一个从算法角度研究虚假广告阻隔机制的工作。理论分析表明,DAK问题具有子模性。因此,我们提出了两种基于蒙特卡洛模拟的贪心算法,该算法可以保证在常数(1-1/e)内逼近最优解。为减少MC模拟空间消耗,我们提出了一种基于排序的启发式方法RanSel,仅使用线性空间就可以高效求解DAK。实验表明,本文方法可以在合理的时间内取得满意的结果。