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

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

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

【參考文獻】

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

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

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

本文編號：2596967