發(fā)布時(shí)間：2020-03-23 16:16

【摘要】：近十年來,Internet、社會(huì)網(wǎng)絡(luò)、手機(jī)等信息技術(shù)的使用對廣告行業(yè)產(chǎn)生了重大而深遠(yuǎn)的影響。它們不僅使廣告的投放變得更容易、更便宜,其產(chǎn)生的大量用戶數(shù)據(jù)也為廣告策略的定量分析提供了機(jī)會(huì)。2008年在ACM-SIAM研討會(huì)上提出的計(jì)算廣告學(xué),旨在通過用戶數(shù)據(jù)提高廣告收益,引起了信息學(xué)、計(jì)算機(jī)科學(xué)和傳播學(xué)的高度重視。目前,相關(guān)研究大都關(guān)注于“一對一”場景下的廣告投放,而對“一對多”投放研究不足。為此,本文將從數(shù)據(jù)驅(qū)動(dòng)的角度,對廣告“一對多”投放中的影響最大化和影響阻隔問題進(jìn)行研究。本論文主要貢獻(xiàn)可概括如下:1)提出了面向團(tuán)體的影響最大化方法在社會(huì)網(wǎng)絡(luò)中,影響最大化問題在病毒營銷、疾病防治和在線推薦等多個(gè)方面具有較強(qiáng)的應(yīng)用背景�，F(xiàn)有工作主要關(guān)注高影響力個(gè)體的選擇,不能有效的定位高影響力社群團(tuán)體。然而,高影響力社群的發(fā)現(xiàn)在區(qū)域疾病防治和戶外商業(yè)活動(dòng)組織等方面有重要的作用。針對該問題,本文從團(tuán)體粒度研究了影響傳播,并形式化定義了面向團(tuán)體的影響力最大化問題,旨在發(fā)現(xiàn)網(wǎng)絡(luò)中具有影響力的top-k社群團(tuán)體。為描述團(tuán)體粒度的影響傳播過程,我們從團(tuán)體間的影響關(guān)聯(lián)入手,首次提出了一種基于關(guān)聯(lián)的團(tuán)體影響級聯(lián)模型。而后,我們在該模型上給出了一種近似的top-k影響力團(tuán)體選擇算法,并證明該算法能返回(1-1/e)的最優(yōu)解。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果顯示,我們的方法能高效選擇具有影響力的團(tuán)體組合。2)提出了基于社會(huì)化瀏覽的影響最大化方法社會(huì)化瀏覽是由社會(huì)網(wǎng)絡(luò)產(chǎn)生的一種全新的信息檢索方式。針對該場景下的廣告投放應(yīng)用,本文提出基于社會(huì)化瀏覽的影響最大化問題(Social BrOwsing based InFluence MaximizatioN,SOFN)。與傳統(tǒng) IM 問題不同的是,SOFN 問題的影響力定義與用戶訪問廣告的代價(jià)有關(guān),其目的在于通過減少用戶搜索廣告的代價(jià)來最大化提高廣告在檢索中曝光率。為求解該問題,本文分別利用動(dòng)態(tài)規(guī)劃算法和矩陣運(yùn)算對目標(biāo)函數(shù)進(jìn)行計(jì)算,并相應(yīng)給出了兩種貪心近似算法DpSel、MatrixSel。其時(shí)間復(fù)雜度分別為O(kCn2m)、O(kCnm)。此外,我們還通過建立候選結(jié)點(diǎn)邊際收益的上界,提出了剪枝算法BoundSel。該算法能夠顯著加速M(fèi)atrixSel算法的貪心過程。本研究在多個(gè)真實(shí)網(wǎng)絡(luò)上進(jìn)行了實(shí)驗(yàn):分別從效果、效率、可擴(kuò)展性、內(nèi)存消耗幾個(gè)方面對本文提出的算法進(jìn)行了驗(yàn)證。結(jié)果顯示,MatrixSel算法在時(shí)間開銷和空間開銷上明顯好于度數(shù)優(yōu)先算法和采樣算法。3)提出了軌跡驅(qū)動(dòng)的高影響力廣告牌選址方法許多國際戶外廣告公司,如Larma和APN,利用車流量來評估廣告牌的影響力。然而,這種做法常導(dǎo)致粗粒度估計(jì)和不理想的廣告投放方案。本研究從真實(shí)車輛運(yùn)行軌跡入手,首次研究了軌跡驅(qū)動(dòng)的高影響力廣告牌選址問題(TIP),旨在最大化廣告牌對軌跡影響。受制于廣告牌定價(jià)不同和其間影響力重疊兩方面的挑戰(zhàn),TIP被證明是NP-hard的。為在有限時(shí)間內(nèi)求解該問題,我們提出了基于劃分的框架PartSel。PartSel首先利用車輛軌跡的局部特征將廣告牌劃分為影響相對獨(dú)立的集合,而后采用枚舉與貪心的組合方法對各個(gè)集合進(jìn)行局部選擇,最后通過動(dòng)態(tài)規(guī)劃算法將局部解合并成全局解。由于局部解相較全局解更容易計(jì)算,PartSel大大降低了計(jì)算開銷,同時(shí)還能提供常數(shù)因子的近似保證。此外,我們還在PartSel的基礎(chǔ)上進(jìn)一步提出了 LazyProbe方法。該方法通對低邊際影響的廣告牌進(jìn)行剪枝來加速PartSel的計(jì)算,且并不影響被優(yōu)化算法的近似性能。實(shí)驗(yàn)表明,該方法的效果相對基于車流量的選址方法提升了 99%。而且該方法是一個(gè)空間選址的通用框架,可推廣到解決汽車充電樁和便利店的選址問題中。4)提出了在線虛假廣告影響阻隔方法在線網(wǎng)絡(luò)的虛假廣告的傳播不僅導(dǎo)致金融財(cái)產(chǎn)的損失,而且可能威脅人身安全。為構(gòu)建可靠的信息傳播平臺,本文采用建立(k個(gè))保護(hù)結(jié)點(diǎn)方式來最大化阻隔用戶對虛假廣告的瀏覽,并提出了在線虛假廣告影響阻隔問題(DeceptiveAds blocKing Placement,DAK)。與謠言控制的研究不同,在DAK問題中虛假廣告對用戶的影響是通過隨機(jī)游走模型描述的,而非影響級聯(lián)模型。據(jù)我們所知,本文是第一個(gè)從算法角度研究虛假廣告阻隔機(jī)制的工作。理論分析表明,DAK問題具有子模性。因此,我們提出了兩種基于蒙特卡洛模擬的貪心算法,該算法可以保證在常數(shù)(1-1/e)內(nèi)逼近最優(yōu)解。為減少M(fèi)C模擬空間消耗,我們提出了一種基于排序的啟發(fā)式方法RanSel,僅使用線性空間就可以高效求解DAK。實(shí)驗(yàn)表明,本文方法可以在合理的時(shí)間內(nèi)取得滿意的結(jié)果。
【圖文】：

用戶的影響力進(jìn)行分析，提升病毒營銷的效果；車輛軌跡數(shù)據(jù)可以被用來對廣告牌的影逡逑響進(jìn)行量化，從而優(yōu)化廣告牌的投放策略。技術(shù)的進(jìn)步使得人類在廣告上的花費(fèi)逐年增逡逑高。美國Ｓｔａｔｉｓｔａ的統(tǒng)計(jì)如圖１．１所示，，２０１７年全球廣告的總投入超過５５００億美元，相逡逑較于２０１０年提高了邋３４％［１］。逡逑６００逡逑５５７．９９逡逑５３４．７９逡逑ｉｉｉｌｌｉｉｌｌ逡逑＿＾＾＾＾＾＾＾＾＾＿逡逑２０１０邋２０１邋１邋２０１２邋２０１３邋２Ｃ１４邋２０１５邋２Ｃ１５邋２０１７＾邋２０１８＊逡逑Ｆｉｇｕｒｅ邋１．１邋Ｇｌｏｂａｌ邋ａｄｖｅｒｔｉｓｉｎｇ邋ｓｐｅｎｄｉｎｇ邋２０１０－２０１８逡逑圖１．１全球廣告市場（２０１０－２０１８）逡逑然而，廣告市場在迅速增長同時(shí)，也帶來了大量的廣告投放浪費(fèi)。據(jù)統(tǒng)計(jì)，Ｇｏｏｇｌｅ逡逑公司５６％的廣告在投放過程中沒有被有效瀏覽；而對于傳統(tǒng)媒介，僅２０１６年電視廣告逡逑的無效投放就達(dá)到了邋６８０億美元ＰＩ。對于全球廣告市場５５００億美元，如果能減少１０％逡逑的無效廣告投放，就意味著我們每年將節(jié)�。担担皟|美元的開支。不僅如此，在線媒體的逡逑扁平化管理也使得其上廣告存在虛假和錯(cuò)誤信息。這些廣告嚴(yán)重的危害了市場的

0＾／７0＝�。�；0５）邋＋，（／？，）邋—邋＆（？２，，１？），因此有／／１？＾所，）－／；（習(xí)＜力（／？，）成立，力（＾）是逡逑子模函數(shù)。證畢。逡逑圖２．３給出了引理２．５的一個(gè)直觀解釋。從圖中可以直接看出逡逑Ｓ／；（ｗ，）成立。逡逑，．總－，逡逑＿邐”邋Ｖ＇逡逑邐Ｕ—－－－邐識吻，｝）逡逑ｖ＾／［．１邐，逡逑Ｆｉｇｕｒｅ邋２．３邋Ｔｈｅ邋ｉｎｆｌｕｅｎｃｅ邋ｏｆ邋Ｓ邋ａｎｄ邋ｍｊ邋ｉｎ邋ｔｒｉｊ逡逑圖２．３邋５？和ｗ，對％的影響逡逑定理２．６邋是子模函數(shù)。逡逑證明：己知４句＝；＾＾＿／；0？），且根據(jù)引理２．５有＿／；⑶是子模函數(shù)。因?yàn)樽幽：义蠑?shù)的和函數(shù)也是子模的
【學(xué)位授予單位】：武漢大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2018
【分類號】：TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 曹玖新;董丹;徐順;鄭嘯;劉波;羅軍舟;;一種基于k-核的社會(huì)網(wǎng)絡(luò)影響最大化算法[J];計(jì)算機(jī)學(xué)報(bào);2015年02期

2 周傲英;周敏奇;宮學(xué)慶;;計(jì)算廣告:以數(shù)據(jù)為核心的Web綜合應(yīng)用[J];計(jì)算機(jī)學(xué)報(bào);2011年10期

本文編號：2596967