地理社交網(wǎng)絡(luò)中基于多目標(biāo)組合優(yōu)化的空間感知影響力聯(lián)合最大化

金鵬飛 常雪芹 房子荃 李 淼

1(浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310027) 2(華為技術(shù)有限公司華為云架構(gòu)業(yè)務(wù)部 廣東深圳 518129)

隨著地理定位技術(shù)與移動(dòng)社交服務(wù)的發(fā)展，融合位置信息的地理社交網(wǎng)絡(luò)(如Foursquare、Gowalla、美團(tuán)網(wǎng)、街旁網(wǎng)等)成為廣受用戶(hù)歡迎的一類(lèi)社交媒體平臺(tái).據(jù)統(tǒng)計(jì)，截至2020年，美團(tuán)平臺(tái)上的活躍商家個(gè)數(shù)以及年度交易用戶(hù)總量已分別增長(zhǎng)至680萬(wàn)和5.1億；與此同時(shí)，2020年度Foursquare通過(guò)旗下的簽到業(yè)務(wù)已在全球190個(gè)國(guó)家與地區(qū)累計(jì)收集了9 500萬(wàn)個(gè)不同類(lèi)別的興趣點(diǎn)信息.地理社交網(wǎng)絡(luò)有效地連接了用戶(hù)的線上信息與線下行為，便捷的線下服務(wù)與相對(duì)低廉的線上廣告成本，也使得更多商家將地理社交網(wǎng)絡(luò)作為一類(lèi)有效的市場(chǎng)推廣途徑.

面向社交網(wǎng)絡(luò)“病毒式”營(yíng)銷(xiāo)(viral marketing)，影響力最大化(influence maximization, IM)問(wèn)題旨在從社交網(wǎng)絡(luò)中尋找并激活

k

個(gè)具有高影響力的用戶(hù)節(jié)點(diǎn)(影響力種子)，利用社交用戶(hù)間“口口相傳”(word of mouth, WOM)的特性，觸發(fā)影響力在用戶(hù)間的連鎖式傳播，從而使影響力傳播最大化.近年來(lái)，得益于5G與物聯(lián)網(wǎng)技術(shù)的發(fā)展，基于位置的廣告營(yíng)銷(xiāo)呈現(xiàn)出極大的商業(yè)潛力.據(jù)權(quán)威部門(mén)預(yù)測(cè)，2021年位置營(yíng)銷(xiāo)服務(wù)將在北美市場(chǎng)創(chuàng)造約1 375億美元的收益.對(duì)應(yīng)基于位置的營(yíng)銷(xiāo)研究，地理社交網(wǎng)絡(luò)中的空間感知影響力最大化問(wèn)題已成為IM領(lǐng)域一個(gè)重要的研究分支.區(qū)別于傳統(tǒng)IM問(wèn)題在社交網(wǎng)絡(luò)全圖中實(shí)現(xiàn)最大化傳播，空間感知IM問(wèn)題考慮了用戶(hù)在物理世界中的空間屬性，使影響力在一部分位置相關(guān)的用戶(hù)群體中達(dá)到最佳的傳播效果.Li等人最早在基于位置的社交網(wǎng)絡(luò)中研究了位置感知影響力最大化(location-aware influence maximization, LAIM)問(wèn)題，給定一個(gè)查詢(xún)范圍，LAIM問(wèn)題嘗試從社交網(wǎng)絡(luò)中尋找

k

個(gè)種子節(jié)點(diǎn)，使影響力在查詢(xún)范圍內(nèi)的用戶(hù)中達(dá)到最大傳播規(guī)模.然而，在LAIM問(wèn)題中，用戶(hù)如何設(shè)定合理的查詢(xún)范圍是一個(gè)潛在的難題.具體而言，假如用戶(hù)設(shè)定的查詢(xún)范圍過(guò)小，大量空間鄰近用戶(hù)將因在查詢(xún)范圍之外而無(wú)法成為營(yíng)銷(xiāo)推廣對(duì)象；若查詢(xún)范圍設(shè)定過(guò)大，則相當(dāng)一部分被激活的用戶(hù)將處于查詢(xún)范圍的邊緣區(qū)域，受空間移動(dòng)的限制，這部分用戶(hù)無(wú)法真正成為線下活躍用戶(hù).為解決此問(wèn)題，Wang等人提出距離感知影響力最大化(distance-aware influence maximization, DAIM)問(wèn)題，認(rèn)為距離查詢(xún)位置更近的用戶(hù)將更有可能被營(yíng)銷(xiāo)活動(dòng)所吸引，因而具有更高的推廣價(jià)值.基于此，DAIM對(duì)各用戶(hù)分配了不同的價(jià)值權(quán)重，以指導(dǎo)空間距離加權(quán)下的影響力種子選擇.

值得注意的是，當(dāng)前有關(guān)空間感知IM問(wèn)題的研究，都只將固定位置處的單一空間對(duì)象作為推廣目標(biāo).這一設(shè)定僅能在有限的空間范圍內(nèi)吸引較少的客戶(hù)，故不利于商家最大化地拓展其市場(chǎng)潛力.為實(shí)現(xiàn)利益最大化，商家需要有多個(gè)營(yíng)銷(xiāo)目標(biāo)，如連鎖店公司對(duì)旗下的多家門(mén)店進(jìn)行聯(lián)合推廣.考慮到大型連鎖公司旗下龐大的門(mén)店規(guī)模(如星巴克在中國(guó)大陸的門(mén)店規(guī)?？傆?jì)約為5 000家，2020年新增門(mén)店259家)，受廣告篇幅與費(fèi)用的限制，商家將無(wú)法在單條廣告中窮盡所有門(mén)店信息.如何從所有門(mén)店中優(yōu)先推選出一部分最具潛力的門(mén)店作為線上推廣主體，并搭配有效的社交營(yíng)銷(xiāo)策略以實(shí)現(xiàn)商家利益的最大化是本文研究的重點(diǎn).圖1進(jìn)一步展示本文的研究動(dòng)機(jī).

Fig. 1 An example of location based social advertising for multiple promotion targets圖1 基于位置的多目標(biāo)營(yíng)銷(xiāo)場(chǎng)景示例

圖1展示了某城市中心新開(kāi)設(shè)的3家星巴克門(mén)店(

p

,

p

,

p

)

.

為方便統(tǒng)計(jì)，規(guī)定單一的某家門(mén)店僅能對(duì)其附近3 km范圍內(nèi)(圖中興趣點(diǎn)圖標(biāo)周?chē)鷪A形陰影區(qū)域)的用戶(hù)產(chǎn)生影響，同時(shí)商家發(fā)布廣告的內(nèi)容篇幅最多容納2家門(mén)店信息，且營(yíng)銷(xiāo)的費(fèi)用預(yù)算為1(影響力種子個(gè)數(shù)為1).在此條件下，若選擇門(mén)店

p

,

p

作為營(yíng)銷(xiāo)推廣目標(biāo)，用戶(hù)

u

作為發(fā)起線上影響力傳播的種子，則影響力傳播過(guò)程將激活7名用戶(hù)，其中4名(

u

,

u

,

u

,

u

)位于推廣位置的鄰近區(qū)域，故此次營(yíng)銷(xiāo)的實(shí)際收益為4；若選擇門(mén)店

p

,

p

作為推廣目標(biāo)，并改變影響力種子為用戶(hù)

u

，則影響力傳播的總體規(guī)模為6，但由于傳播過(guò)程中所有用戶(hù)均與推廣門(mén)店位置鄰近，故該策略下商家營(yíng)銷(xiāo)的實(shí)際收益將上升為6.

在圖1示例中，本質(zhì)是求解一組推廣目標(biāo)與影響力種子集合的最優(yōu)搭配，從而使商家在基于位置的營(yíng)銷(xiāo)中獲得最大化的收益.本文將該問(wèn)題稱(chēng)為基于多目標(biāo)組合優(yōu)化的空間感知影響力聯(lián)合推廣(location-aware joint influence promotion, LA-JIP)問(wèn)題.相比于傳統(tǒng)IM問(wèn)題以及空間感知的IM問(wèn)題變種，LA-JIP問(wèn)題的求解有著更多的挑戰(zhàn)：1)在不同位置組合下，用戶(hù)權(quán)重的衡量將更為復(fù)雜，且評(píng)估影響力傳播過(guò)程中所獲得的收益本身是一個(gè)#P難題，如何對(duì)影響力傳播收益進(jìn)行高效而準(zhǔn)確的評(píng)估是解決LA-JIP問(wèn)題的關(guān)鍵；2)LA-JIP問(wèn)題涉及對(duì)推廣目標(biāo)的位置與影響力種子的聯(lián)合選取，該問(wèn)題本身為一個(gè)NP難問(wèn)題，且目標(biāo)函數(shù)不滿(mǎn)足子模特性，故傳統(tǒng)的貪心策略將無(wú)法直接對(duì)該問(wèn)題實(shí)現(xiàn)理論精度保障下的求解；3)LA-JIP是一個(gè)多目標(biāo)組合優(yōu)化問(wèn)題，由于不同優(yōu)化目標(biāo)間彼此關(guān)聯(lián)性強(qiáng)，故難以針對(duì)某一目標(biāo)設(shè)計(jì)有效的剪枝方式以加速問(wèn)題的精確求解.綜上所述，本文工作的主要貢獻(xiàn)有4個(gè)方面：

1) 面向真實(shí)應(yīng)用，首次研究了地理社交網(wǎng)絡(luò)中基于多目標(biāo)組合優(yōu)化的空間感知影響力聯(lián)合推廣問(wèn)題LA-JIP，通過(guò)發(fā)現(xiàn)門(mén)店推廣位置與影響力種子的最優(yōu)組合搭配，以實(shí)現(xiàn)商家利益最大化的營(yíng)銷(xiāo)推廣；

2) 基于反向影響力采樣技術(shù)，提出了在用戶(hù)影響力加權(quán)條件下的影響力傳播收益上下界推導(dǎo)方法，以有效地評(píng)估多目標(biāo)組合下的營(yíng)銷(xiāo)推廣效益；

3) 提出了滿(mǎn)足結(jié)果精度收斂的迭代處理算法，通過(guò)多輪的結(jié)果迭代優(yōu)化，該算法能夠在一定的理論精度保障下對(duì)LA-JIP問(wèn)題進(jìn)行高效的近似求解；

4) 在多個(gè)真實(shí)數(shù)據(jù)集上對(duì)所提問(wèn)題及技術(shù)方法的有效性進(jìn)行了驗(yàn)證.實(shí)驗(yàn)結(jié)果表明相比傳統(tǒng)IM或DAIM問(wèn)題，LA-JIP能夠有效地提升空間感知影響力推廣收益；此外，所提出的迭代處理算法相比傳統(tǒng)貪心策略下的基準(zhǔn)算法，結(jié)果質(zhì)量提高10%～50%、算法運(yùn)行效率快1～2個(gè)數(shù)量級(jí).

1 相關(guān)工作

影響力最大化問(wèn)題最早可追溯至對(duì)“病毒式營(yíng)銷(xiāo)”和“口碑效應(yīng)”的研究.Domingo和Richardson首次將影響力最大化分析引入社交領(lǐng)域，并指出了該問(wèn)題在輿情預(yù)警與市場(chǎng)營(yíng)銷(xiāo)中的重要性.隨后，Kempe等人首次從算法角度將影響力最大化定義為一個(gè)組合優(yōu)化問(wèn)題，在獨(dú)立級(jí)聯(lián)(independent cascade, IC)模型與線性閾值(linear threshold, LT)模型下證明了該問(wèn)題的NP難復(fù)雜性，并基于問(wèn)題的子模特性在貪心策略下提出了精度為(1-1/e)的近似算法，但該算法需涉及大量耗時(shí)的蒙特卡羅模擬來(lái)對(duì)節(jié)點(diǎn)影響力進(jìn)行評(píng)估，因而算法時(shí)間復(fù)雜度極高，不適用于大規(guī)模社交網(wǎng)絡(luò).此后，一些研究者提出了啟發(fā)式方法以識(shí)別高影響力的用戶(hù)節(jié)點(diǎn)，這類(lèi)方法盡管在效率上有較大提升，但其求得結(jié)果的精度缺乏理論保證.后續(xù)大量研究工作致力于提出滿(mǎn)足理論精度保證的高效近似算法，以支持大規(guī)模社交網(wǎng)絡(luò)圖下的IM問(wèn)題求解.針對(duì)這一目標(biāo)，大量高效的影響力采樣策略被提出.其中基于反向影響力采樣技術(shù)的算法被證明不僅具有理論精度保障，而且滿(mǎn)足漸線性的時(shí)間復(fù)雜度，因而成為當(dāng)下最為有效的一類(lèi)IM問(wèn)題處理方法.這類(lèi)算法的核心是采樣足夠規(guī)模的隨機(jī)反向影響力可達(dá)集，從而對(duì)高影響力節(jié)點(diǎn)展開(kāi)有效的分析與選擇.后續(xù)基于該方向的一系列拓展工作，集中解決了如何在不改變結(jié)果精度的前提下盡可能地減少隨機(jī)反向可達(dá)集的采樣規(guī)模，以最大化地提升算法的處理效率.

近年來(lái)隨著移動(dòng)社交服務(wù)的興起，地理社交網(wǎng)絡(luò)中的空間感知影響力最大化問(wèn)題引起了學(xué)術(shù)界的廣泛關(guān)注.Li等人最先研究了空間感知影響力最大化的問(wèn)題原型，該工作借鑒了“口碑營(yíng)銷(xiāo)”的思想，通過(guò)從全局社交網(wǎng)絡(luò)中尋找

k

個(gè)種子節(jié)點(diǎn)，以觸發(fā)影響力在給定空間查詢(xún)范圍內(nèi)的最優(yōu)傳播效果.進(jìn)一步地，Wang等人在文獻(xiàn)[9]中提出了距離感知的影響力最大化(distance-aware influence maximization, DAIM)問(wèn)題，給定一個(gè)地理位置坐標(biāo)，DAIM根據(jù)用戶(hù)與查詢(xún)位置間距離的遠(yuǎn)近，對(duì)不同位置處的用戶(hù)推廣效益進(jìn)行加權(quán)處理，最終使所選種子的影響力能夠在鄰近用戶(hù)群體中產(chǎn)生最優(yōu)的推廣效果.類(lèi)似DAIM，文獻(xiàn)[23]綜合考慮了社交影響力傳播過(guò)程中的時(shí)間有效性，研究了目標(biāo)用戶(hù)影響力最大化問(wèn)題，該工作基于反向影響力采樣的思想提出了基于加權(quán)反向可達(dá)采樣樹(shù)的近似算法，實(shí)現(xiàn)了理論精度保障下的問(wèn)題求解.受LAIM啟發(fā)，文獻(xiàn)[24]研究了地理社交影響力最大化拓展(geo-social influence spanning maximization, GISM)問(wèn)題,給定查詢(xún)區(qū)域

R

,GISM綜合考慮區(qū)域

R

中用戶(hù)的總體激活情況以及

R

中各個(gè)子區(qū)域內(nèi)部用戶(hù)的激活比率，使影響力能夠在盡可能多的子區(qū)域間有更均衡的傳播效果，GISM在區(qū)域性的政客競(jìng)選中有著重要的應(yīng)用價(jià)值.此外，Zhong等人面向DAIM問(wèn)題探討了高效的錨點(diǎn)采樣技術(shù).Wang等人在社交媒體數(shù)據(jù)流上對(duì)LAIM問(wèn)題展開(kāi)了探索.Shi等人在文獻(xiàn)[27]中通過(guò)對(duì)地理社交網(wǎng)絡(luò)中興趣點(diǎn)簽到數(shù)據(jù)的分析，探索了地理位置驅(qū)動(dòng)下影響力最大化問(wèn)題.于亞新等人在考慮競(jìng)爭(zhēng)的地理社交網(wǎng)絡(luò)中研究了避免種子重疊的多方影響力博弈問(wèn)題.面向多標(biāo)準(zhǔn)決策優(yōu)化，Wang等人探討了不同種子選取策略下的Pareto結(jié)果集高效求解方法，通過(guò)權(quán)衡營(yíng)銷(xiāo)過(guò)程中的代價(jià)與收益，為商家提供全面的營(yíng)銷(xiāo)決策支持.值得注意的是，上述的所有工作僅局限于通過(guò)改變影響力種子的選取策略來(lái)實(shí)現(xiàn)空間感知的影響力推廣，而忽略了推廣目標(biāo)本身在空間屬性方面所具有的優(yōu)化潛能，這也是本文研究工作與現(xiàn)有工作的最大不同之處.

2 問(wèn)題定義

本節(jié)首先介紹問(wèn)題的相關(guān)預(yù)備知識(shí)，其次對(duì)問(wèn)題進(jìn)行形式化定義與難度分析，最后基于貪心策略提出一種啟發(fā)式方法作為求解問(wèn)題的基準(zhǔn)算法.表1列出了文中常用的符號(hào)及其含義.

Table 1 Symbols and Description

2.1 預(yù)備知識(shí)

對(duì)社交網(wǎng)絡(luò)中影響力傳播過(guò)程的分析需借助特定的傳播模型.目前學(xué)術(shù)界對(duì)影響力傳播模型的研究主要集中于：獨(dú)立級(jí)聯(lián)(independent cascade, IC)模型、線性閾值(linear threshold, LT)模型以及觸發(fā)模型，讀者可查閱文獻(xiàn)[30]對(duì)各模型的相關(guān)細(xì)節(jié)進(jìn)行深入的了解.本文使用IC模型來(lái)對(duì)社交網(wǎng)絡(luò)上影響力傳播過(guò)程進(jìn)行建模.

IC模型是一種概率模型.在IC模型中，社交網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)僅能有2種狀態(tài)：激活狀態(tài)(active)或者未激活狀態(tài)(inactive).只有處于激活狀態(tài)的節(jié)點(diǎn)才會(huì)對(duì)其鄰居節(jié)點(diǎn)產(chǎn)生影響.基于此，獨(dú)立級(jí)聯(lián)模型將影響力的傳播過(guò)程抽象為以下多個(gè)輪次的隨機(jī)過(guò)程：

1) 在初始時(shí)刻

t

，種子集

S

中的用戶(hù)被激活，社交網(wǎng)絡(luò)中其他節(jié)點(diǎn)為未激活狀態(tài)，影響力從

S

出發(fā)向周邊節(jié)點(diǎn)進(jìn)行傳播；2) 在時(shí)刻

t

，上輪中被新激活的用戶(hù)

u

以概率

p

(

u

,

v

)對(duì)所有未激活的出邊鄰居

v

進(jìn)行激活嘗試，用戶(hù)間的激活嘗試僅進(jìn)行一次，且不同用戶(hù)間的激活嘗試彼此獨(dú)立(

u

對(duì)

v

的激活不受其他節(jié)點(diǎn)的影響)

.

若

v

被成功激活，則

v

將保持激活狀態(tài)直至傳播結(jié)束

.

令

S

表示時(shí)刻

t

新激活的用戶(hù)集；3) 在時(shí)刻

t

+1，

S

中用戶(hù)(上輪中新激活的用戶(hù))繼續(xù)執(zhí)行2)中步驟

.

上述過(guò)程重復(fù)執(zhí)行，直到社交網(wǎng)絡(luò)中不存在可被激活的節(jié)點(diǎn)時(shí)，影響力傳播過(guò)程結(jié)束

.

假設(shè)傳播結(jié)束的時(shí)刻為

t

,則此時(shí)

S

=?

.

(1)

(2)

2.2 問(wèn)題定義與復(fù)雜度分析

(3)

定理1.

LA-JIP問(wèn)題為NP難問(wèn)題.

證畢

.

定理2.

在多目標(biāo)組合推廣場(chǎng)景中，計(jì)算種子在特定推廣對(duì)象下的影響力收益為#P難問(wèn)題.證明.當(dāng)式(2)中權(quán)重衰減速率參數(shù)

β

=0時(shí)，社交網(wǎng)絡(luò)中所有用戶(hù)權(quán)重將統(tǒng)一為1，此時(shí)影響力收益將轉(zhuǎn)化為傳統(tǒng)IM問(wèn)題中的影響力規(guī)模.由于計(jì)算影響力規(guī)模為#P難問(wèn)題，故計(jì)算影響力收益同樣為#P難問(wèn)題

.

證畢

.

2.3 基準(zhǔn)算法

考慮到當(dāng)前有關(guān)IM問(wèn)題的大多數(shù)工作傾向于使用貪婪策略來(lái)實(shí)現(xiàn)對(duì)問(wèn)題的近似最優(yōu)求解，為此本文繼承這一思想，提出一類(lèi)啟發(fā)式算法對(duì)LA-JIP問(wèn)題進(jìn)行直觀的求解.基準(zhǔn)算法的基本思路在于使用貪婪策略，通過(guò)一輪循環(huán)來(lái)選取指定個(gè)數(shù)的種子與位置目標(biāo)的集合配對(duì)，具體流程如算法1所示.該算法根據(jù)種子與推廣位置的個(gè)數(shù)進(jìn)行循環(huán)計(jì)算.在每次循環(huán)中，對(duì)不同用戶(hù)(位置)在當(dāng)前

S

*,

L

*組合下的影響力收益增幅進(jìn)行計(jì)算(行③⑤)，并選取當(dāng)前擁有最大影響力收益增幅的用戶(hù)(位置)加入集合

S

*(

L

*)中(行④⑥).由于LA-JIP問(wèn)題需要對(duì)2組集合的搭配進(jìn)行優(yōu)化，且集合內(nèi)部與集合間元素都存在相關(guān)性，故算法1循環(huán)內(nèi)部需交替地執(zhí)行當(dāng)前最優(yōu)種子與位置的選取，以實(shí)現(xiàn)對(duì)2組集合元素的同步優(yōu)化.值得注意的是，由于首次循環(huán)中算法考察當(dāng)前最優(yōu)的位置需借助已有種子的影響力傳播情況，因此我們規(guī)定種子的選擇步驟應(yīng)優(yōu)先于位置的選擇.

算法1.

基準(zhǔn)算法(Baseline).

輸出：推廣位置集

L

*、影響力種子集

S

*

.

①

S

*←?,

L

*←?；② while |

L

*|<

m

且|

S

*|<

k

/

*選擇當(dāng)前影響力收益增幅最大的用戶(hù)*

/

④ if |

S

*|<

k

then

S

*←

S

*∪{

u

}；

/

*選擇當(dāng)前影響力收益增幅最大的位置*

/

⑥ if |

L

*|<

m

then

L

*←

L

*∪{

l

}；

⑦ end while

⑧ return

L

*，

S

*

.

算法1以一種較為直觀的方式對(duì)LA-JIP進(jìn)行了求解，但由于LA-JIP的非子模特性，該方法無(wú)法保證其返回的結(jié)果在嚴(yán)格意義下?lián)碛?1-1/e)的近似度.

Fig. 2 The example of non-submodularity in LA-JIP圖2 LA-JIP問(wèn)題非子模特性證明示例

定理3.

LA-JIP問(wèn)題的目標(biāo)函數(shù)不滿(mǎn)足子模特性.

證畢

.

3 多輪次迭代算法

由于基準(zhǔn)算法無(wú)法提供明確的理論精度保證，故本節(jié)提出一套基于迭代的處理框架以支持精度收斂的LA-JIP問(wèn)題求解.首先介紹反向影響力采樣技術(shù)及影響力無(wú)偏估計(jì)策略的原理；其次基于鞅不等式(martingale inquality)設(shè)計(jì)針對(duì)影響力傳播收益的上下界評(píng)估方法；最后基于上述技術(shù)對(duì)迭代算法的運(yùn)行流程展開(kāi)介紹，并給出結(jié)果置信度分析.

3.1 反向影響力采樣技術(shù)

對(duì)影響力傳播的評(píng)估涉及期望的求解，該問(wèn)題實(shí)際為#P難問(wèn)題，在大規(guī)模社交網(wǎng)絡(luò)圖中將產(chǎn)生巨大的計(jì)算開(kāi)銷(xiāo).為了解決這一挑戰(zhàn)，反向影響力采樣(reverse influence sampling, RIS)是一類(lèi)加速影響力評(píng)估的有效方法.RIS技術(shù)的核心在于構(gòu)建一組采樣結(jié)果集，即隨機(jī)“反向可達(dá)集合”(random reverse reachable set, RR set)，并基于RR set對(duì)種子的影響力進(jìn)行無(wú)偏估計(jì)(unbiased estimation).隨機(jī)反向可達(dá)集合(RR set)可通過(guò)以下步驟生成：

RR set的構(gòu)建細(xì)節(jié)與優(yōu)化技術(shù)可查看文獻(xiàn)[17-19,22].

(4)

(5)

(6)

3.2 影響力收益上下界評(píng)估方法

本節(jié)利用一類(lèi)有效的概率統(tǒng)計(jì)方法：鞅不等式(martingale inquality)來(lái)量化影響力收益無(wú)偏估計(jì)值與影響力收益真實(shí)值之間的差異.

定義3

.

給定一組隨機(jī)變量序列

M

,

M

,…,

M

，若E[|

M

|]<+∞，E[

M

|

M

,

M

,…,

M

-1]=

M

-1，則稱(chēng)該隨機(jī)變量序列為鞅

.

(7)

(8)

(9)

(10)

(11)

證明：

exp(-ln(1

/δ

))=

δ

，

證畢

.

1-

δ

,

證明:

證畢

.

3

.

2

.

1 位置集與種子集明確時(shí)影響力收益上下界評(píng)估

(12)

(13)

式(12)和(13)在推廣位置與影響力種子組合內(nèi)容已知的情況下對(duì)影響力收益上下界進(jìn)行評(píng)估

.

以下將在位置集與種子集組合不確定的情況下，推導(dǎo)出所有潛在組合可獲得的最大影響力收益上界

.

3

.

2

.

2 潛在位置與種子組合下的影響力收益上界推導(dǎo)

(14)

(15)

證明

.

根據(jù)影響力收益的定義(定義2)，有

則有

證畢

.

(16)

3.3 LA-JIP多輪迭代處理算法

基于3.2節(jié)中影響力收益上下界評(píng)估方法，迭代算法的執(zhí)行流程如算法2所示.

算法2.

迭代算法.

輸出：推廣目標(biāo)位置集

L

*、影響力種子集

S

*

.

①

S

*←?，

L

*←?，

ratio

←0；

③ while

ratio

<1-1

/

e-

ε

④ if (Round=1)

⑥ else

⑨ end if

Greedy_MultiLoc為算法2中重要功能函數(shù)，其被算法2反復(fù)調(diào)用以實(shí)現(xiàn)不同輪次下對(duì)當(dāng)前最優(yōu)位置集的更新，其偽代碼如算法3所示

.

算法3.

Greedy_MultiLoc算法.

輸出：推廣目標(biāo)位置集

L

*

.

①

L

*←?；② while |

L

*|<

m

④

L

*←

L

*∪{

l

}；

⑤ end while

⑥ return

L

*

.

接下來(lái)進(jìn)行結(jié)果置信度分析

.

假設(shè)算法2中while循環(huán)的最大迭代次數(shù)為

r

.

由于每輪迭代中，影響力收益上下界評(píng)估將產(chǎn)生2

δ

的出錯(cuò)概率，故算法在所有輪次下累計(jì)出錯(cuò)的概率為2

δ

×

r

.

因此，將以1-2

δ

×

r

的置信概率獲得指定精度下的近似結(jié)果

.

通常情況下，設(shè)定參數(shù)

δ

=1

/

|

V

|，由于算法2在實(shí)際執(zhí)行過(guò)程中的迭代次數(shù)遠(yuǎn)小于|

V

|，因而1-2

δ

×

r

≈1，即算法能夠以較高的置信度獲得(1-1

/

e-

ε

)下的近似求解

.

4 實(shí)驗(yàn)評(píng)估

4.1 數(shù)據(jù)集與測(cè)試環(huán)境

為驗(yàn)證本文研究?jī)?nèi)容及所提技術(shù)方法的有效性，本節(jié)使用2組真實(shí)的地理社交網(wǎng)絡(luò)數(shù)據(jù)集：Brightkite和Gowalla進(jìn)行實(shí)驗(yàn)評(píng)估.數(shù)據(jù)集可通過(guò)Stanford大學(xué)的SNAP項(xiàng)目在線獲取.在Brightkite和Gowalla中，分別有11.4%和45.6%的用戶(hù)無(wú)位置坐標(biāo)，對(duì)于這部分用戶(hù)，根據(jù)其朋友位置坐標(biāo)的均值對(duì)其進(jìn)行位置分配.處理后的數(shù)據(jù)集信息如表2所示:

Table 2 Statistics of the Datasets

實(shí)驗(yàn)測(cè)試的算法均使用C++語(yǔ)言編寫(xiě)，并在g++13編譯器下編譯優(yōu)化.所有實(shí)驗(yàn)在配備有Intel i-7 2.9 GHz主頻CPU，64 GB內(nèi)存的PC機(jī)上運(yùn)行，安裝的操作系統(tǒng)為Ubuntu 14.04.

4.2 實(shí)驗(yàn)設(shè)定

1) 傳播概率設(shè)定.參考當(dāng)前IM研究領(lǐng)域中廣泛使用的方法，本文采用加權(quán)級(jí)聯(lián)(weighted cascade)模型對(duì)社交網(wǎng)絡(luò)圖邊上影響力傳播概率進(jìn)行分配：

p

(

u

,

v

)=1

/

|

N

(

v

)|，其中|

N

(

v

)|表示用戶(hù)

v

在社交網(wǎng)絡(luò)中的入度

.

3) 影響力收益值評(píng)估.為客觀評(píng)估不同算法所求結(jié)果的質(zhì)量，實(shí)驗(yàn)對(duì)種子影響力傳播過(guò)程進(jìn)行10 000次蒙特卡羅(Monte Carlo, MC)模擬，并將此過(guò)程中被激活用戶(hù)權(quán)重和的均值作為種子影響力收益.

4) 參數(shù)設(shè)定.為評(píng)估不同參數(shù)設(shè)置對(duì)算法的影響，我們?cè)诓煌瑓?shù)設(shè)定下對(duì)算法性能進(jìn)行評(píng)估.各參數(shù)設(shè)定值的范圍如表3所示，每行中黑體數(shù)字表示各參數(shù)的默認(rèn)設(shè)定值.在評(píng)估參數(shù)性能時(shí)，我們僅改變其中某個(gè)參數(shù)的值，而固定其余參數(shù)為默認(rèn)設(shè)定值.

Table 3 Parameter Settings

4.3 有效性評(píng)估

為了驗(yàn)證本文研究?jī)?nèi)容在空間感知影響力聯(lián)合推廣中的有效性，本節(jié)將LA-JIP策略下產(chǎn)生的影響力收益情況與下述策略進(jìn)行對(duì)比：

3) Baseline策略.本文所提算法1(基準(zhǔn)算法)，即解決問(wèn)題的啟發(fā)式算法；

4) LA-JIP策略.本文所提算法2(多輪迭代處理算法)，即求得的結(jié)果有理論精度保障的近似算法.

Fig. 3 The distribution of the users located in Dallas圖3 達(dá)拉斯市區(qū)范圍內(nèi)用戶(hù)分布情況

Fig. 4 The performance comparison of influence promotion for bars by different strategies圖4 酒吧類(lèi)興趣點(diǎn)集合下不同策略的影響力 推廣效果對(duì)比

Fig. 5 The performance comparison of influence promotion for markets by different strategies圖5 商場(chǎng)類(lèi)興趣點(diǎn)集合下不同策略的影響力 推廣效果對(duì)比

設(shè)置

m

=2，

k

=10，測(cè)試上述推廣策略的執(zhí)行效果.對(duì)不同策略返回的結(jié)果(推廣位置集+種子集)執(zhí)行蒙特卡洛模擬評(píng)估其影響力傳播情況，使用百度地圖API對(duì)傳播中激活用戶(hù)的位置進(jìn)行可視化展示.由于各類(lèi)興趣點(diǎn)組下策略間的性能差異大體相同，本節(jié)僅對(duì)酒吧、商場(chǎng)這2類(lèi)興趣點(diǎn)集合下的結(jié)果進(jìn)行展示(圖4與圖5).由圖中結(jié)果可知，IM+DBSCAN策略在空間感知影響力推廣中的效果最差，該策略激活用戶(hù)的空間分布十分離散且與推廣位置間無(wú)明顯鄰近關(guān)系；DAIM策略由于考慮了用戶(hù)權(quán)重，故影響力傳播相對(duì)推廣位置有明顯的空間聚合趨勢(shì).然而，由于該策略忽略了對(duì)推廣位置的優(yōu)化，推廣位置個(gè)體間仍存在較多的影響力重疊，整體推廣效果依舊不佳；Baseline策略由于在貪婪策略中對(duì)種子集與位置集進(jìn)行了同步優(yōu)化，故相比僅分開(kāi)優(yōu)化2組集合的IM+DBSCAN策略，影響力推廣效果有明顯的提升.

但由于Baseline策略無(wú)理論精度保障，因此優(yōu)化性能并不穩(wěn)定，在某些輸入情況下Baseline策略的效果將劣于DAIM策略.作為對(duì)比，LA-JIP策略在各類(lèi)興趣點(diǎn)集合下始終中展現(xiàn)了全局最優(yōu)的特點(diǎn)，且相比Baseline策略，LA-JIP策略整體性能更加穩(wěn)定，產(chǎn)生的影響力分布情況相對(duì)推廣目標(biāo)的位置分布也更具空間聚合性.此外，由于LA-JIP策略進(jìn)一步優(yōu)化了推廣位置的空間布局，因此LA-JIP相比DAIM減少了更多內(nèi)部的影響力重疊，故在多目標(biāo)組合下有更優(yōu)影響力全局推廣效果.

4.4 算法性能評(píng)估

本節(jié)在Brightkite和Gowalla兩組數(shù)據(jù)集上，對(duì)基準(zhǔn)算法(baseline, BA)、迭代算法(iterative, IT)的處理性能進(jìn)行全面評(píng)估.實(shí)驗(yàn)比較了算法在不同種子個(gè)數(shù)、推廣目標(biāo)位置個(gè)數(shù)、侯選位置集合大小下的性能變化趨勢(shì).本文以算法的響應(yīng)時(shí)間和所求結(jié)果的影響力傳播收益作為衡量算法性能的2項(xiàng)指標(biāo).本文對(duì)每組實(shí)驗(yàn)重復(fù)5次測(cè)試，并取平均值作為最終結(jié)果.

4.4.1 種子個(gè)數(shù)對(duì)性能的影響

本文在Brightkite和Gowalla兩組數(shù)據(jù)集下測(cè)試不同的種子個(gè)數(shù)(5,10,15,20,25)對(duì)BA與IT算法性能的影響，結(jié)果如圖6所示.從圖6結(jié)果可知，IT算法能夠在BA算法基礎(chǔ)上進(jìn)一步提升10%～50%的影響力傳播收益，且運(yùn)行效率有1～2個(gè)數(shù)量級(jí)的提升.這驗(yàn)證了本文第3節(jié)中所提方法的有效性.此外，隨著種子個(gè)數(shù)的增多，所有算法的響應(yīng)時(shí)間及影響力傳播收益均呈現(xiàn)增長(zhǎng)趨勢(shì).這是因?yàn)檩^多的種子能觸發(fā)更大的影響力傳播范圍，從而提高了影響力在用戶(hù)中傳播所能獲得的收益；這同時(shí)也增加了算法在評(píng)估種子影響力過(guò)程中的開(kāi)銷(xiāo).值得注意的是，所有算法在Gowalla數(shù)據(jù)集下均獲得了比Brightkite數(shù)據(jù)集下更高的影響力收益.這是因?yàn)镚owalla相比Brightkite擁有更大的社交網(wǎng)絡(luò)以及更為稠密的用戶(hù)空間分布，因而Gowalla數(shù)據(jù)集下產(chǎn)生的種子能夠激活更多高權(quán)重的用戶(hù)，從而利于影響力在傳播過(guò)程中積累到更多收益.這一對(duì)比結(jié)果體現(xiàn)了迭代算法在大規(guī)模社交圖下實(shí)現(xiàn)空間感知影響力推廣的性能優(yōu)勢(shì).

Fig. 6 The effect of varying k on performance圖6 種子個(gè)數(shù)k變化對(duì)算法性能的影響

4.4.2 推廣目標(biāo)位置個(gè)數(shù)對(duì)性能的影響

Fig. 7 The effect of varying m on performance圖7 推廣目標(biāo)位置個(gè)數(shù)m變化對(duì)算法性能的影響

圖7展示了推廣目標(biāo)位置個(gè)數(shù)對(duì)算法性能的影響.在不同的位置個(gè)數(shù)設(shè)定下，迭代算法的性能均明顯優(yōu)于基準(zhǔn)算法，且在更大規(guī)模的Gowalla數(shù)據(jù)集上迭代算法較基準(zhǔn)算法的性能優(yōu)勢(shì)更為明顯.隨著推廣目標(biāo)位置個(gè)數(shù)的增多，各算法取得的影響力收益均呈現(xiàn)增長(zhǎng)趨勢(shì).這是因?yàn)橥茝V位置的增加將使更多用戶(hù)因鄰近空間對(duì)象而擁有更大的推廣權(quán)重，因而影響力傳播過(guò)程將獲得更大的收益.值得注意的是，當(dāng)推廣位置較多時(shí)(|

L

|≥4)，基準(zhǔn)算法與迭代算法間性能分化趨勢(shì)更為明顯，這進(jìn)一步體現(xiàn)了迭代算法在多目標(biāo)組合優(yōu)化處理中的優(yōu)勢(shì).

4.4.3 侯選位置集合大小對(duì)性能的影響

圖8展示了候選位置集合大小的變化對(duì)算法性能的影響.在不同規(guī)模的候選位置集合下，迭代算法的性能均明顯優(yōu)于基準(zhǔn)算法.此外，隨著候選位置集合的增大，各算法所得結(jié)果的影響力收益呈現(xiàn)先增加后逐漸趨于穩(wěn)定的趨勢(shì).這是因?yàn)楫?dāng)候選位置集合規(guī)模較小時(shí)，加入更多的位置可使算法構(gòu)建出與影響力空間分布更為擬合的推廣目標(biāo)位置分布.然而，當(dāng)候選位置集增加至一定規(guī)模后，集合中的大量位置之間將存在較多的影響力重疊，從而使得影響力傳播收益的增幅呈現(xiàn)減緩趨勢(shì).

Fig. 8 The effect of varying on performance圖8 候選位置集合大小變化對(duì)算法性能的影響

4.5 對(duì)ε參數(shù)設(shè)定的評(píng)估

Fig. 9 Evaluate parameter ε in Brightkite dataset圖9 Brightkite數(shù)據(jù)集下評(píng)估參數(shù)ε

Fig. 10 Evaluate parameter ε in Gowalla dataset圖10 Gowalla數(shù)據(jù)集下評(píng)估參數(shù)ε

本節(jié)進(jìn)一步探索迭代算法中對(duì)精度誤差參數(shù)

ε

的合理設(shè)定.圖9～10展示了迭代算法在Brightkite數(shù)據(jù)集以及Gowalla數(shù)據(jù)集下基于不同精度誤差參數(shù)

ε

的運(yùn)行結(jié)果(影響力收益、響應(yīng)時(shí)間、RR set采樣規(guī)模).從圖9中結(jié)果可知，當(dāng)

ε

值較小時(shí)(

ε

<0.20)，進(jìn)一步減小ε對(duì)算法返回的結(jié)果精度提升效果并不明顯；相反，還將導(dǎo)致算法的響應(yīng)時(shí)間急劇增長(zhǎng)，并在處理過(guò)程中耗費(fèi)大量的內(nèi)存開(kāi)銷(xiāo)(大量RR set被采樣產(chǎn)生并作為中間結(jié)果常駐內(nèi)存).當(dāng)精度誤差參數(shù)設(shè)定較大時(shí)(

ε

≥0.20)，算法時(shí)間空間上的開(kāi)銷(xiāo)都明顯降低，但結(jié)果精度損失卻下降明顯.權(quán)衡算法的求解效率與返回結(jié)果的質(zhì)量，本文將

ε

=0.20作為迭代算法的默認(rèn)精度誤差參數(shù).

5 總 結(jié)

本文研究了地理社交網(wǎng)絡(luò)中基于多目標(biāo)組合優(yōu)化的空間感知影響力聯(lián)合推廣問(wèn)題(LA-JIP).該問(wèn)題考慮了影響力在位置相關(guān)用戶(hù)中的推廣差異，通過(guò)構(gòu)建推廣目標(biāo)位置與影響力種子間的最優(yōu)搭配，實(shí)現(xiàn)全局利益最大化的商家營(yíng)銷(xiāo)推廣.為了有效地解決LA-JIP問(wèn)題，本文拓展了現(xiàn)有的反向影響力采樣技術(shù)，提出了有理論保障的影響力收益上下界評(píng)估方法，并基于此通過(guò)多輪迭代對(duì)問(wèn)題進(jìn)行了高效的近似求解.最終，在真實(shí)的數(shù)據(jù)集下實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出的技術(shù)能有效地提升多目標(biāo)組合下空間感知影響力推廣.在未來(lái)工作中，我們將考慮引入更多的地理空間因素(如營(yíng)銷(xiāo)點(diǎn)的空間分布密集、營(yíng)銷(xiāo)位置相對(duì)各用戶(hù)的

k

近鄰排序等)來(lái)設(shè)計(jì)更為合理的用戶(hù)權(quán)重度量函數(shù)，以使LA-JIP問(wèn)題適應(yīng)更多復(fù)雜的應(yīng)用場(chǎng)景.此外進(jìn)一步優(yōu)化提升本文提出的近似算法的理論精度也是未來(lái)努力的方向之一.

作者貢獻(xiàn)聲明

：金鵬飛負(fù)責(zé)提出問(wèn)題研究的動(dòng)機(jī)與思路、算法設(shè)計(jì)方案、實(shí)驗(yàn)方案并撰寫(xiě)論文；常雪芹負(fù)責(zé)算法方案實(shí)現(xiàn)、實(shí)驗(yàn)測(cè)試、結(jié)果評(píng)估并協(xié)助撰寫(xiě)論文；房子荃與李淼提出指導(dǎo)意見(jiàn)并修改完善論文.