地理社交網(wǎng)絡中重疊種子的廣告博弈決策機制

于亞新 王 磊

(東北大學計算機科學與工程學院 沈陽 110169)

隨著Twitter、Facebook、微博等社交應用的興起，社交網(wǎng)絡已成為信息傳播的重要媒介，許多公司也開始將其作為廣告推廣和產(chǎn)品營銷的主要工具.與傳統(tǒng)大眾營銷方式不同，作為數(shù)字廣告領域中發(fā)展最快的行業(yè)，社交廣告不僅關注消費者的固有價值，還注重其在信息傳播中的作用.在現(xiàn)實世界中，人們對于是否購買一種產(chǎn)品或接受一種想法多受其朋友、同事或同齡人的影響.因此一些公司會采用免費試用或利益回報的方式在整個網(wǎng)絡中尋找意見領袖，即尋找最具影響力的種子，以便通過這些種子個體的社交影響力來擴大產(chǎn)品或廣告的影響范圍，從而獲得更大收益.這種基于“口碑”[1]的營銷方式，利用成員間推介的“級聯(lián)”效應使產(chǎn)品的潛在客戶不斷增多.與影響力最大化(influence maximization, IM)問題[2-3]類似，社交廣告要解決的問題是,在特定傳播模型下，找到k個最具影響力的節(jié)點集合，從而最大化產(chǎn)品或廣告的影響范圍.近年來，病毒營銷[4]中的影響力最大化問題被廣泛研究，但由于所用數(shù)據(jù)集的限制，大多數(shù)現(xiàn)有研究成果只能用于分析用戶在虛擬世界中的行為，而忽略了位置信息的作用.幸運的是，隨著無線通信設備和定位技術的發(fā)展，人們可以通過網(wǎng)絡隨時分享位置和想法，由此產(chǎn)生了海量的時空數(shù)據(jù)，從而使得在傳統(tǒng)社交網(wǎng)絡中加入空間這一維度成為可能.

舉個例子，許多現(xiàn)實世界中的營銷活動都增加了對營銷位置[5-6]這一因素的考量，比如，圖1解釋了與營銷位置有關的用戶進行信息傳播的過程,其中u1和u2分別代表2個傳播種子，他們可以繼續(xù)向自己的下層傳播，如黑線所示.當營銷活動主辦方在位置V進行營銷活動時，距離V較近的用戶(如圖1中的u1)，相比距離V較遠的用戶(如圖1中的u2)，往往更有可能成為營銷活動的成功推廣者或參與者，因為較近的距離是影響決策的重要因素之一.此時，距離營銷位置不同的用戶應給予不同權重的考慮.類似地，在信息傳播過程中，與u1距離較近的朋友(圓圈所示)，因同處于營銷位置附近而更可能受其影響成為潛在顧客.進一步而言，用戶間的影響概率也應根據(jù)二者間的物理距離進行動態(tài)推演，但遺憾的是，現(xiàn)有IM模型由于未考慮空間位置信息，因此不能直接用于解決該問題.

Fig. 1 Location-aware promotion圖1 考慮位置信息的營銷活動示意圖

基于上述問題，本文首先提出一種位置敏感獨立級聯(lián)模型(distance-aware independent cascade, DAIC)，并基于該模型對地理社交網(wǎng)絡中的影響力最大化(location-aware influence maximization, LAIM)問題進行了重新定義，進而提出一種在貪婪框架下的位置敏感影響力最大化算法LA_Greedy(location-aware greedy).

值得注意的是，大多數(shù)IM問題的研究工作是在“忽略競爭”情況下展開[7-9]，即假定1家公司可以在網(wǎng)絡中獨立于其他公司進行種子挑選，但實際上幾家公司常常在同一市場相互競爭(例如寶馬、奔馳、奧迪在汽車市場中的競爭)，并在同一網(wǎng)絡挑選種子，由此，針對競爭網(wǎng)絡的影響力最大化問題得到了廣泛關注與研究[10-11].雖說如此，研究者們在解決競爭環(huán)境下的IM問題時，做出了許多不切實際的假設[12-13]，比如1家公司可以在知道競爭對手的種子挑選結(jié)果后再做出最有利本公司的選擇.然而在現(xiàn)實世界中，公司的營銷策略和種子選擇結(jié)果都是重要的商業(yè)秘密，不可能輕易地被他人獲知.因此，同一領域的2家公司常常要在無任何輔助信息情況下完成種子挑選工作，這往往會導致種子重疊現(xiàn)象[14]，使得一些種子個體不能實現(xiàn)預期的傳播范圍，從而造成影響力的損失[15].

考慮圖2(a)中的無競爭網(wǎng)絡，為了擴大新款車型的影響，假定公司甲選擇節(jié)點A和節(jié)點B作為初始推廣者，期待利用A和B的個人影響擴大該款汽車的市場影響力，進而得到更多消費者青睞，并最終可以影響到7人.在圖2(b)所示的競爭網(wǎng)絡中，假設甲公司競爭對手即乙公司，也要推出一款新車型，在無法獲知競爭對手甲公司的選擇結(jié)果下，同樣可將節(jié)點A和節(jié)點B作為推銷甲公司的車的初始推廣者，繼而在信息傳播過程中，二級推廣者C將受到A和B的共同影響.但由于受到現(xiàn)有廣告?zhèn)鞑C制的限制，C往往只會選擇一款汽車進行推薦，因為公司只與初始推廣者(即種子個體)存在利益交互(如免費試用或根據(jù)最終影響范圍給予一定利益回報)，二級推廣者C僅僅靠與種子個體之間的往來關系決定是否繼續(xù)進行推薦.因此相對自由的二級推廣者在做推薦選擇時會受到更多因素的影響(如對重疊種子的信任程度，甚至可能直接被其他競爭公司選為其產(chǎn)品或廣告的推廣者).

Fig. 2 Information propagation in social network圖2 社交網(wǎng)絡信息傳播示意圖

綜上所述，無論是重疊種子個體(overlapping seeds)A與B的出現(xiàn)，還是二級推廣者C不確定的選擇結(jié)果，都會使同一網(wǎng)絡中相互競爭的2家公司不能達到預期的影響力傳播范圍.同樣地，作為被公司寄予厚望的種子個體也會因其推廣效果不佳而受到相應損失.為解決該問題，本文通過分析重疊種子與其鄰居節(jié)點的支付矩陣,首次為重疊種子個體提供了選擇公司的博弈決策機制,使重疊種子在博弈中找到納什均衡點，進而決策出將為其推銷產(chǎn)品的最佳公司，相應地，該博弈決策機制也降低了種子集合的重疊率和影響力的損失.

綜上所述，本文主要貢獻有3個方面:

1) 提出了一種距離敏感獨立級聯(lián)模型DAIC，該模型將用戶間物理距離引入獨立級聯(lián)模型(independent cascade， IC)中，量化了距離因素對傳播概率的影響，解決了地理社交網(wǎng)絡中用戶間影響力概率的動態(tài)推演問題.

2) 提出了一種貪婪框架下位置敏感影響力最大化算法LA_Greedy，該算法基于DAIC模型將營銷物理位置引入影響力最大化(IM)的定義中，解決了傳統(tǒng)IM由于未考慮位置信息所導致的影響力傳播范圍與實際可用范圍間的距離偏差問題.

3) 提出了一種面向重疊種子的競爭博弈決策機制(game decision-making mechanism， GDMM)，該機制首次立足廣告重疊種子角度，通過分析重疊種子與其鄰居節(jié)點的支付矩陣，對競爭選擇進行決策博弈，最終找到納什均衡點，從而降低了種子重疊率和影響力損失.

1 基于DAIC模型的IM問題

本節(jié)首先介紹距離敏感獨立級聯(lián)模型DAIC，然后基于該模型重新定義了地理社交網(wǎng)絡中的影響力最大化問題.為清楚起見，表1給出了本文用到的一些符號及其含義：

Table 1 Notation of Symbols表1 符號及含義

1.1 距離敏感獨立級聯(lián)模型DAIC

網(wǎng)絡用戶間影響概率的大小是決定傳播范圍的關鍵因素之一，同一節(jié)點其傳播能力在不同的影響概率下具有很大差異.在IC模型中，用戶間的影響概率通常被隨機指定，但在攜帶位置信息的地理社交網(wǎng)的營銷活動中，用戶間影響概率還會受到彼此間物理距離的作用，因此，不能直接套用IC模型對影響概率值的隨機指派方法.基于此，本文提出一種距離敏感獨立級聯(lián)模型DAIC，旨在有效量化位置距離對傳播概率的影響.直觀地，當用戶u要在位置lu進行產(chǎn)品推薦時，在其朋友中，與之距離較近的用戶會因同處于營銷位置附近而更可能被影響，從而成為潛在顧客，因此有理由認為，u對鄰居v的影響力會隨著彼此間物理距離的增加而減弱，即用戶間位置距離與影響概率成反比.下面，對用戶間影響概率的理論計算推演過程做詳細闡述.

不失一般性，假定地理社交網(wǎng)絡中u對v的影響概率為puv，u的地理位置為lu，pu→v(l,lu)表示當用戶v處在位置l時u對v的影響概率，簡寫為p(l).令dl>0表示一個極小的距離增量，則當用戶v處在位置l+dl時，u對v的影響概率為p(l+dl)，影響概率的改變量則為dp=p(l+dl)-p(l).如前所述，節(jié)點u對v的影響力會隨著距離的增加而減弱,于是有dp=p(l+dl)-p(l)<0，表示對應于距離增量dl的影響概率損失.與放射性衰變[16-17]類似(微粒越大，衰變越快)，理論上, dp正比于p(l)：

(1)

等式形式:

(2)

其中,負號表示p(l)隨著距離的增加而減小，比例常數(shù)為τ，整理式(2),得：

(3)

整理式(3)，得：

(4)

將式(4)兩邊同時積分，得：

(5)

整理式(5)，得：

(6)

整理式(6)，得：

(7)

其中，c為積分常數(shù)，整理式(7),得：

(8)

令l(u)=0，則在式(8)中，Δ=l-lu=l(在二維空間中Δ表示l與lu之間的歐氏距離),即式(8)從理論上證明了u對v的影響概率隨著距離的增加呈指數(shù)衰減.通過簡化，定義用戶間位置敏感的影響概率計算公式為

puv=e-α l.

(9)

與IC模型類似，DAIC模型的信息傳播過程如下：給定初始活躍集合A，當不活躍節(jié)點u在時間步t變?yōu)榛钴S狀態(tài)后，該節(jié)點將嘗試激活每個處在不活躍狀態(tài)的鄰居.但無論激活結(jié)果如何，在以后的時間步中，u都不會再對其鄰居產(chǎn)生任何影響.若成功，則鄰居節(jié)點v在時間步t+1變?yōu)榛钴S狀態(tài).當節(jié)點v有多個鄰居節(jié)點變?yōu)榛钴S狀態(tài)時，這些節(jié)點可以按任意順序嘗試激活v.當不再存在激活可能時，傳播過程結(jié)束.

1.2 基于DAIC模型的影響力最大化問題

在社交網(wǎng)絡研究中，通常將有向圖G(V,E)作為抽象研究對象，其中V為節(jié)點的集合，E為邊的集合.

定義2.位置敏感影響力傳播范圍.給定一個地理社交網(wǎng)絡G(V,E)和一個營銷位置l,以及集合S?V.考慮位置的影響力傳播范圍

其中，w(v,l)表示節(jié)點v對應營銷位置l的權值.

如上所述，營銷位置附近的用戶應該具有更高的權值，即w(v,l)與v和l間的距離成反比.為了簡化，本文令w(v,l)=ce-β d(v,l)，其中c>0表示節(jié)點能夠達到的最大權值，d(v,l)為節(jié)點v與營銷位置l間的歐氏距離，β>0為衰減速率.

問題1.影響力最大化(IM)問題. 給定一個社交網(wǎng)絡G(V,E)和種子個數(shù)k，求一個節(jié)點集合S?V，|S|=k，使得以S作為初始種子集合時，在特定信息傳播模型下具有最大的影響力傳播范圍，即對于任意大小為k的節(jié)點集合S′，I(S)≥I(S′)，集合S為

(10)

問題2.位置敏感影響力最大化(LAIM)問題. 給定一個地理社交網(wǎng)絡G(V,E)、營銷位置l及種子個數(shù)k，要求找到一個節(jié)點集合S?V，|S|=k，使得以S作為初始種子集合在DAIC模型上進行影響力最大化傳播時，其位置敏感的影響力傳播范圍σ(S)最大，即對于任意大小為k的節(jié)點集合S′，σ(S)≥σ(S′)，集合S為

(11)

2 位置敏感影響力最大化算法LA_Greedy

算法1.LA_Greedy算法.

輸入:地理社交網(wǎng)絡G、種子集合大小k、營銷位置l;

輸出:種子集合S.

① Off-line computepuvforu,v∈E;*計算每對用戶間影響概率puv*

② computew(v,l) forv∈V;*為用戶分配不同權值*

③S←?;*給定種子集合S，初始為空*

④ fori=1 tokdo*根據(jù)種子個數(shù)k進行循環(huán)計算*

⑥S←S∪{u};*將u加入種子集合S*

⑦ end for

⑧ returnS.

在位置敏感影響力最大化問題LAIM中，當權值函數(shù)w(v,l)=ce-β d(v,l)的參數(shù)c=1，β=0時，網(wǎng)絡中所有節(jié)點的權值都變?yōu)榕c位置無關的常量1，這時LAIM就等價于IM，因此，LAIM問題是NP-難的[19].類似地，可以證明計算位置敏感的影響力傳播范圍也是一個NP-難問題[20].基于影響力傳播函數(shù)的性質(zhì)，本文提出一種貪婪框架下位置敏感影響力最大化算法LA_Greedy，算法1給出了其詳細步驟.

步驟1. 以網(wǎng)絡個體間的位置距離為輸入，利用式(9)計算每對用戶u和v間的影響概率puv；

步驟2. 根據(jù)網(wǎng)絡中各用戶v與特定營銷推廣位置l之間的距離，為用戶分配不同的權值，即w(v,l)=ce-β d(v,l).

步驟3. 給定種子集合S，初始為空，根據(jù)種子個數(shù)k進行循環(huán)運算.

步驟4. 基于目標函數(shù)σ(S)，在每次迭代過程中，將具有最大邊際收益的節(jié)點u加入到集合S中.

步驟5. 循環(huán)結(jié)束，將集合S作為初始種子集合返回.

3 重疊種子個體的博弈決策機制GDMM

現(xiàn)實世界同一領域中不可避免的競爭往往引發(fā)種子重疊現(xiàn)象，導致一些種子個體不能實現(xiàn)預期的傳播范圍，造成影響力損失.通過分析重疊種子與其鄰居節(jié)點的支付矩陣,本文首次為重疊種子個體制定選擇公司的博弈決策機制GDMM,使其在博弈中找到納什均衡點并作出最佳公司選擇決策.GDMM博弈過程如下.

根據(jù)重疊種子個體和二級推廣者做出不同決策時的利益得失情況，分別給出雙方的支付矩陣SSeed與NNeighbor:

(12)

(13)

其中，γk∈[0,1](k=1,2,…,8)為博弈分析的參數(shù)因子，主要取決個體間的信任程度，可以根據(jù)具體要求進行調(diào)整.

為計算方便，對Neighbor在原支付矩陣的基礎上進行了轉(zhuǎn)置.通過簡單的畫線法可以得出該博弈模型不存在純策略均衡，但可求出混合策略的納什均衡.假定重疊種子個體以概率x選擇A公司，以概率1-x選擇B公司，即重疊種子個體的混合策略為PSeed=(x,1-x)；二級推廣者以概率y選擇A公司，以概率1-y選擇B公司，即二級推廣者的混合策略為PNeighbor=(y,1-y).則重疊種子個體的預期支付函數(shù)為

(14)

對式(14)關于y求偏導，可得重疊種子個體最優(yōu)化一階條件：

解得x：

即在博弈過程中，重疊種子個體選擇公司的最佳混合策略為PSeed=(x,1-x).可以看出，重疊種子個體選擇A公司的概率x與其鄰居節(jié)點被A公司選中時獲得的收益有關，鄰居節(jié)點從A公司獲得的收益越多，重疊種子選擇A公司的概率越大；反之，則更傾向于選擇B公司.

4 實驗數(shù)據(jù)集與性能測試

4.1 實驗數(shù)據(jù)與測試環(huán)境

為驗證所提算法和策略的有效性，利用Twitter官方提供的API接口采集了2016年10月內(nèi)1周的數(shù)據(jù).經(jīng)過清洗得到有效節(jié)點6 046個、節(jié)點間關系數(shù)據(jù)14 487條.由于所采數(shù)據(jù)的用戶地理位置比較緊密(各節(jié)點距中心位置的平均距離約為72.99 km).為了檢測所提算法在不同類型測試集上的效果，又模擬了具有12 000個節(jié)點、28 320條邊的位置較為疏遠(各節(jié)點距中心位置的平均距離約為341.03 km)的數(shù)據(jù)集，具體情況如表2所示.

在實驗中，采用Java語言編程，CPU為Intel Core i5-4590 3.3 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 7.

Table 2 Experimental Data Set表2 實驗數(shù)據(jù)集

4.2 參數(shù)設置

實驗中，營銷位置l與各節(jié)點的公司選擇通過隨機指定.設用戶間影響概率計算公式n=|V|的參數(shù)α為經(jīng)驗值0.02,權值函數(shù)w(v,l)=ce-β d(v,l)中c=10，β=0.02.通常每個重疊種子個體對應多個鄰居，故在博弈分析中將鄰居得失的均值作為支付函數(shù)參數(shù)，γk∈[0,1](k=1,2,…,8)暫設為1.

4.3 實驗結(jié)果與性能分析

為體現(xiàn)社交網(wǎng)用戶之間關系緊密程度，本文用網(wǎng)絡聚類系數(shù)來評測，Cv表示節(jié)點聚類系數(shù)，CG表示網(wǎng)絡聚類系數(shù)，具體計算：

(15)

其中，|Ev|表示網(wǎng)絡用戶v的鄰居節(jié)點間的實際連接數(shù)，kv為用戶v的鄰居個數(shù).

(16)

其中，V={v1,v2,…,vn}表示網(wǎng)絡G中的所有個體集合，n=|V|為個體數(shù)目.

通過計算發(fā)現(xiàn)，與具有相同節(jié)點數(shù)和邊數(shù)的一個完全隨機化網(wǎng)絡相比，采集的Twitter數(shù)據(jù)所構(gòu)建的社交網(wǎng)有著明顯較高聚類系數(shù)，說明Twitter網(wǎng)用戶間關系比較緊密，有利于信息傳播.

為驗證GDMM策略對重疊種子在進行公司選擇時的指導效果，分別針對真實Twitter數(shù)據(jù)以及模擬數(shù)據(jù)，在DAIC與IC 這2種傳播模型下對種子集合的重疊率進行了測試(此處將Greedy與LA_Greedy算法分別作為A和B這2家公司挑選種子時所用的策略予以指定)，實驗結(jié)果分別如圖3和圖4所示，其中，橫坐標代表種子個數(shù)k，縱坐標代表種子集合的重疊率.從圖3和圖4中可以看出，盡管隨著k的增大，2家公司的種子集合的重疊率都呈變大趨勢，但相比于沒有使用納什平衡的方法，GDMM策略卻可以明顯降低種子集合的重疊率，從而更好地保證傳播效果.

Fig. 3 Overlapping rate of Twitter data based on different models圖3 Twitter數(shù)據(jù)在不同傳播模型下的種子重疊率

Fig. 4 Overlapping rate of simulated data based on different models圖4 模擬數(shù)據(jù)在不同傳播模型下的種子重疊率

Fig. 5 Influence spread of Twitter data based on DAIC model圖5 Twitter數(shù)據(jù)在DAIC模型下的影響力傳播

為驗證LA_Greedy算法的影響力傳播范圍，實驗對種子集合的影響力傳播過程進行了20 000次模擬，然后將此過程所得平均值作為種子節(jié)點最終的影響范圍，并體現(xiàn)在影響人數(shù)和影響人數(shù)權值這2個指標上.圖5和圖6為Greedy和LA_Greedy這2種算法在Twitter數(shù)據(jù)集上分別在DAIC模型和IC模型下的測試結(jié)果，其中橫坐標代表種子個數(shù)k，縱坐標代表傳播過程結(jié)束后種子集合的影響范圍和加權影響范圍.

首先，從圖5和圖6中可以看出，隨著k的增加，種子集合的影響范圍與加權影響范圍也隨之增加，但當k增至一定規(guī)模后，其增長速度開始變得緩慢.這是因為隨著具有較大影響力的節(jié)點不斷地被選入到集合后，新加入種子的邊際影響力也越來越小.

其次，從圖5和圖6中還可以看出，雖然通過LA_Greedy算法所求種子集合的最終影響人數(shù)略少于Greedy算法，但是LA_Greedy算法所影響節(jié)點的加權影響范圍卻高于Greedy算法，這說明LA_Greedy算法確實更加適用于解決地理社交網(wǎng)絡中位置敏感的影響力最大化問題，即通過LA_Greedy算法所找到的種子集合可以影響更多網(wǎng)絡中權值較大的用戶，也就是營銷位置附近的潛在顧客，解決了傳統(tǒng)IM中由于缺少位置信息所導致的傳播范圍與實際需求不符問題.

圖7和圖8則給出了Greedy和LA_Greedy這2種算法在模擬數(shù)據(jù)集上分別在DAIC模型和IC模型下的測試結(jié)果.與Twitter數(shù)據(jù)類似，橫坐標代表種子個數(shù)k，縱坐標代表傳播過程結(jié)束后種子集合的影響范圍和加權影響范圍.分別對比圖5(a)與圖7(a)、圖5(b)與圖7(b)，可以看出，用戶在地理位置比較疏遠的模擬數(shù)據(jù)集上的種子集合的影響范圍與加權影響范圍，要遠遠小于用戶地理位置比較緊密的Twitter數(shù)據(jù)集上的傳播結(jié)果，這是因為模擬數(shù)據(jù)集中各節(jié)點距中心位置的平均距離約為341.03 km，類似于日常生活中相距較遠的2個城市之間的距離，因此當給定營銷位置后，網(wǎng)絡中各用戶的權值與用戶間的影響概率的計算結(jié)果都非常小，導致種子集合的影響范圍不理想.不過，此結(jié)果也符合日常生活中人們的行為習慣，即當用戶受到線上影響而進入線下環(huán)節(jié)后，是否參與線下體驗將取決于用戶和推薦產(chǎn)品的位置特征，這是因為用戶的消費行為受到地理位置影響，存在對消費位置的偏好，此偏好由用戶的生活習慣和交通能力的因素決定，體現(xiàn)了用戶的日常生活范圍，推薦產(chǎn)品的位置越超出用戶的日常生活范圍，用戶去嘗試的概率就會越低，這也說明所提算法確實可以用于日常生活中針對某一特定范圍內(nèi)的營銷推廣活動.

Fig. 6 Influence spread of Twitter data based on IC model圖6 Twitter數(shù)據(jù)在IC模型下的影響力傳播

Fig. 7 Influence spread of simulated data based on DAIC model圖7 模擬數(shù)據(jù)在DAIC模型下的影響力傳播

Fig. 8 Influence spread of simulated data based on IC model圖8 模擬數(shù)據(jù)在IC模型的實驗結(jié)果

5 總 結(jié)

基于放射性衰變定律，首先對地理社交網(wǎng)中用戶間影響概率的計算公式進行了理論推導，并提出了一種距離敏感的DAIC傳播模型，進一步，基于該模型又提出了貪婪框架下位置敏感的影響力最大化算法LA_Greedy.實驗證明，在求解位置敏感的影響力最大化問題時，LA_Greedy算法與傳統(tǒng)Greedy算法相比，前者可以吸引更多營銷位置附近的用戶，確保了用戶的精準推薦.此外，當重疊種子根據(jù)所提的GDMM機制進行公司選擇時，種子集合的重疊率確實得以明顯下降,從而保證了有效的傳播效果.未來工作將考慮把Twitter以外更多其他社交網(wǎng)數(shù)據(jù)納入研究，并加強對部分垂直領域的數(shù)據(jù)分析處理，以體現(xiàn)本文工作可擴展性和實際應用價值.