面向计算广告学的影响最大化及阻隔方法研究

发布时间：2020-03-23 16:16

【摘要】：近十年来,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。实验表明,本文方法可以在合理的时间内取得满意的结果。
【图文】：

广告市场,全球

用户的影响力进行分析，提升病毒营销的效果；车辆轨迹数据可以被用来对广告牌的影逡逑响进行量化，从而优化广告牌的投放策略。技术的进步使得人类在广告上的花费逐年增逡逑高。美国Ｓｔａｔｉｓｔａ的统计如图１．１所示，，２０１７年全球广告的总投入超过５５００亿美元，相逡逑较于２０１０年提高了邋３４％［１］。逡逑６００逡逑５５７．９９逡逑５３４．７９逡逑ｉｉｉｌｌｉｉｌｌ逡逑＿＾＾＾＾＾＾＾＾＾＿逡逑２０１０邋２０１邋１邋２０１２邋２０１３邋２Ｃ１４邋２０１５邋２Ｃ１５邋２０１７＾邋２０１８＊逡逑Ｆｉｇｕｒｅ邋１．１邋Ｇｌｏｂａｌ邋ａｄｖｅｒｔｉｓｉｎｇ邋ｓｐｅｎｄｉｎｇ邋２０１０－２０１８逡逑图１．１全球广告市场（２０１０－２０１８）逡逑然而，广告市场在迅速增长同时，也带来了大量的广告投放浪费。据统计，Ｇｏｏｇｌｅ逡逑公司５６％的广告在投放过程中没有被有效浏览；而对于传统媒介，仅２０１６年电视广告逡逑的无效投放就达到了邋６８０亿美元ＰＩ。对于全球广告市场５５００亿美元，如果能减少１０％逡逑的无效广告投放，就意味着我们每年将节省５５０亿美元的开支。不仅如此，在线媒体的逡逑扁平化管理也使得其上广告存在虚假和错误信息。这些广告严重的危害了市场的

子模,引理,函数,和函数

0＾／７0＝！／；0５）邋＋，（／？，）邋—邋＆（？２，，１？），因此有／／１？＾所，）－／；（习＜力（／？，）成立，力（＾）是逡逑子模函数。证毕。逡逑图２．３给出了引理２．５的一个直观解释。从图中可以直接看出逡逑Ｓ／；（ｗ，）成立。逡逑，．总－，逡逑＿逦”邋Ｖ＇逡逑逦Ｕ—－－－逦识吻，｝）逡逑ｖ＾／［．１逦，逡逑Ｆｉｇｕｒｅ邋２．３邋Ｔｈｅ邋ｉｎｆｌｕｅｎｃｅ邋ｏｆ邋Ｓ邋ａｎｄ邋ｍｊ邋ｉｎ邋ｔｒｉｊ逡逑图２．３邋５？和ｗ，对％的影响逡逑定理２．６邋是子模函数。逡逑证明：己知４句＝；＾＾＿／；0？），且根据引理２．５有＿／；⑶是子模函数。因为子模函逡逑数的和函数也是子模的
【学位授予单位】：武汉大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TP301.6

【参考文献】