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

于亞新 王 磊

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110169)

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

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

Fig. 1 Location-aware promotion圖1 考慮位置信息的營(yíng)銷活動(dòng)示意圖

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

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

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

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

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

綜上所述，本文主要貢獻(xiàn)有3個(gè)方面:

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

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

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

1 基于DAIC模型的IM問(wèn)題

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

Table 1 Notation of Symbols表1 符號(hào)及含義

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

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

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

(1)

等式形式:

(2)

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

(3)

整理式(3)，得：

(4)

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

(5)

整理式(5)，得：

(6)

整理式(6)，得：

(7)

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

(8)

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

puv=e-α l.

(9)

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

1.2 基于DAIC模型的影響力最大化問(wèn)題

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

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

其中，w(v,l)表示節(jié)點(diǎn)v對(duì)應(yīng)營(yíng)銷位置l的權(quán)值.

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

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

(10)

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

(11)

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

算法1.LA_Greedy算法.

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

輸出:種子集合S.

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

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

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

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

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

⑦ end for

⑧ returnS.

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

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

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

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

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

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

3 重疊種子個(gè)體的博弈決策機(jī)制GDMM

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

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

(12)

(13)

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

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

(14)

對(duì)式(14)關(guān)于y求偏導(dǎo)，可得重疊種子個(gè)體最優(yōu)化一階條件：

解得x：

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

4 實(shí)驗(yàn)數(shù)據(jù)集與性能測(cè)試

4.1 實(shí)驗(yàn)數(shù)據(jù)與測(cè)試環(huán)境

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

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

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

4.2 參數(shù)設(shè)置

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

4.3 實(shí)驗(yàn)結(jié)果與性能分析

為體現(xiàn)社交網(wǎng)用戶之間關(guān)系緊密程度，本文用網(wǎng)絡(luò)聚類系數(shù)來(lái)評(píng)測(cè)，Cv表示節(jié)點(diǎn)聚類系數(shù)，CG表示網(wǎng)絡(luò)聚類系數(shù)，具體計(jì)算：

(15)

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

(16)

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

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

為驗(yàn)證GDMM策略對(duì)重疊種子在進(jìn)行公司選擇時(shí)的指導(dǎo)效果，分別針對(duì)真實(shí)Twitter數(shù)據(jù)以及模擬數(shù)據(jù)，在DAIC與IC 這2種傳播模型下對(duì)種子集合的重疊率進(jìn)行了測(cè)試(此處將Greedy與LA_Greedy算法分別作為A和B這2家公司挑選種子時(shí)所用的策略予以指定)，實(shí)驗(yàn)結(jié)果分別如圖3和圖4所示，其中，橫坐標(biāo)代表種子個(gè)數(shù)k，縱坐標(biāo)代表種子集合的重疊率.從圖3和圖4中可以看出，盡管隨著k的增大，2家公司的種子集合的重疊率都呈變大趨勢(shì)，但相比于沒(méi)有使用納什平衡的方法，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模型下的影響力傳播

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

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

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

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

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模型的實(shí)驗(yàn)結(jié)果

5 總 結(jié)

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