地理社交網絡中基于多目標組合優化的空間感知影響力聯合最大化

金鵬飛 常雪芹 房子荃 李 淼

1(浙江大學計算機科學與技術學院 杭州 310027) 2(華為技術有限公司華為云架構業務部 廣東深圳 518129)

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

面向社交網絡“病毒式”營銷(viral marketing)，影響力最大化(influence maximization, IM)問題旨在從社交網絡中尋找并激活

k

個具有高影響力的用戶節點(影響力種子)，利用社交用戶間“口口相傳”(word of mouth, WOM)的特性，觸發影響力在用戶間的連鎖式傳播，從而使影響力傳播最大化.近年來，得益于5G與物聯網技術的發展，基于位置的廣告營銷呈現出極大的商業潛力.據權威部門預測，2021年位置營銷服務將在北美市場創造約1 375億美元的收益.對應基于位置的營銷研究，地理社交網絡中的空間感知影響力最大化問題已成為IM領域一個重要的研究分支.區別于傳統IM問題在社交網絡全圖中實現最大化傳播，空間感知IM問題考慮了用戶在物理世界中的空間屬性，使影響力在一部分位置相關的用戶群體中達到最佳的傳播效果.Li等人最早在基于位置的社交網絡中研究了位置感知影響力最大化(location-aware influence maximization, LAIM)問題，給定一個查詢范圍，LAIM問題嘗試從社交網絡中尋找

k

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

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

Fig. 1 An example of location based social advertising for multiple promotion targets圖1 基于位置的多目標營銷場景示例

圖1展示了某城市中心新開設的3家星巴克門店(

p

,

p

,

p

)

.

為方便統計，規定單一的某家門店僅能對其附近3 km范圍內(圖中興趣點圖標周圍圓形陰影區域)的用戶產生影響，同時商家發布廣告的內容篇幅最多容納2家門店信息，且營銷的費用預算為1(影響力種子個數為1).在此條件下，若選擇門店

p

,

p

作為營銷推廣目標，用戶

u

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

u

,

u

,

u

,

u

)位于推廣位置的鄰近區域，故此次營銷的實際收益為4；若選擇門店

p

,

p

作為推廣目標，并改變影響力種子為用戶

u

，則影響力傳播的總體規模為6，但由于傳播過程中所有用戶均與推廣門店位置鄰近，故該策略下商家營銷的實際收益將上升為6.

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

1) 面向真實應用，首次研究了地理社交網絡中基于多目標組合優化的空間感知影響力聯合推廣問題LA-JIP，通過發現門店推廣位置與影響力種子的最優組合搭配，以實現商家利益最大化的營銷推廣；

2) 基于反向影響力采樣技術，提出了在用戶影響力加權條件下的影響力傳播收益上下界推導方法，以有效地評估多目標組合下的營銷推廣效益；

3) 提出了滿足結果精度收斂的迭代處理算法，通過多輪的結果迭代優化，該算法能夠在一定的理論精度保障下對LA-JIP問題進行高效的近似求解；

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

1 相關工作

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

近年來隨著移動社交服務的興起，地理社交網絡中的空間感知影響力最大化問題引起了學術界的廣泛關注.Li等人最先研究了空間感知影響力最大化的問題原型，該工作借鑒了“口碑營銷”的思想，通過從全局社交網絡中尋找

k

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

R

,GISM綜合考慮區域

R

中用戶的總體激活情況以及

R

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

2 問題定義

本節首先介紹問題的相關預備知識，其次對問題進行形式化定義與難度分析，最后基于貪心策略提出一種啟發式方法作為求解問題的基準算法.表1列出了文中常用的符號及其含義.

Table 1 Symbols and Description

2.1 預備知識

對社交網絡中影響力傳播過程的分析需借助特定的傳播模型.目前學術界對影響力傳播模型的研究主要集中于：獨立級聯(independent cascade, IC)模型、線性閾值(linear threshold, LT)模型以及觸發模型，讀者可查閱文獻[30]對各模型的相關細節進行深入的了解.本文使用IC模型來對社交網絡上影響力傳播過程進行建模.

IC模型是一種概率模型.在IC模型中，社交網絡中的每個節點僅能有2種狀態：激活狀態(active)或者未激活狀態(inactive).只有處于激活狀態的節點才會對其鄰居節點產生影響.基于此，獨立級聯模型將影響力的傳播過程抽象為以下多個輪次的隨機過程：

1) 在初始時刻

t

，種子集

S

中的用戶被激活，社交網絡中其他節點為未激活狀態，影響力從

S

出發向周邊節點進行傳播；2) 在時刻

t

，上輪中被新激活的用戶

u

以概率

p

(

u

,

v

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

v

進行激活嘗試，用戶間的激活嘗試僅進行一次，且不同用戶間的激活嘗試彼此獨立(

u

對

v

的激活不受其他節點的影響)

.

若

v

被成功激活，則

v

將保持激活狀態直至傳播結束

.

令

S

表示時刻

t

新激活的用戶集；3) 在時刻

t

+1，

S

中用戶(上輪中新激活的用戶)繼續執行2)中步驟

.

上述過程重復執行，直到社交網絡中不存在可被激活的節點時，影響力傳播過程結束

.

假設傳播結束的時刻為

t

,則此時

S

=?

.

(1)

(2)

2.2 問題定義與復雜度分析

(3)

定理1.

LA-JIP問題為NP難問題.

證畢

.

定理2.

在多目標組合推廣場景中，計算種子在特定推廣對象下的影響力收益為#P難問題.證明.當式(2)中權重衰減速率參數

β

=0時，社交網絡中所有用戶權重將統一為1，此時影響力收益將轉化為傳統IM問題中的影響力規模.由于計算影響力規模為#P難問題，故計算影響力收益同樣為#P難問題

.

證畢

.

2.3 基準算法

考慮到當前有關IM問題的大多數工作傾向于使用貪婪策略來實現對問題的近似最優求解，為此本文繼承這一思想，提出一類啟發式算法對LA-JIP問題進行直觀的求解.基準算法的基本思路在于使用貪婪策略，通過一輪循環來選取指定個數的種子與位置目標的集合配對，具體流程如算法1所示.該算法根據種子與推廣位置的個數進行循環計算.在每次循環中，對不同用戶(位置)在當前

S

*,

L

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

S

*(

L

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

算法1.

基準算法(Baseline).

輸出：推廣位置集

L

*、影響力種子集

S

*

.

①

S

*←?,

L

*←?；② while |

L

*|<

m

且|

S

*|<

k

/

*選擇當前影響力收益增幅最大的用戶*

/

④ if |

S

*|<

k

then

S

*←

S

*∪{

u

}；

/

*選擇當前影響力收益增幅最大的位置*

/

⑥ if |

L

*|<

m

then

L

*←

L

*∪{

l

}；

⑦ end while

⑧ return

L

*，

S

*

.

算法1以一種較為直觀的方式對LA-JIP進行了求解，但由于LA-JIP的非子模特性，該方法無法保證其返回的結果在嚴格意義下擁有(1-1/e)的近似度.

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

定理3.

LA-JIP問題的目標函數不滿足子模特性.

證畢

.

3 多輪次迭代算法

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

3.1 反向影響力采樣技術

對影響力傳播的評估涉及期望的求解，該問題實際為#P難問題，在大規模社交網絡圖中將產生巨大的計算開銷.為了解決這一挑戰，反向影響力采樣(reverse influence sampling, RIS)是一類加速影響力評估的有效方法.RIS技術的核心在于構建一組采樣結果集，即隨機“反向可達集合”(random reverse reachable set, RR set)，并基于RR set對種子的影響力進行無偏估計(unbiased estimation).隨機反向可達集合(RR set)可通過以下步驟生成：

RR set的構建細節與優化技術可查看文獻[17-19,22].

(4)

(5)

(6)

3.2 影響力收益上下界評估方法

本節利用一類有效的概率統計方法：鞅不等式(martingale inquality)來量化影響力收益無偏估計值與影響力收益真實值之間的差異.

定義3

.

給定一組隨機變量序列

M

,

M

,…,

M

，若E[|

M

|]<+∞，E[

M

|

M

,

M

,…,

M

-1]=

M

-1，則稱該隨機變量序列為鞅

.

(7)

(8)

(9)

(10)

(11)

證明：

exp(-ln(1

/δ

))=

δ

，

證畢

.

1-

δ

,

證明:

證畢

.

3

.

2

.

1 位置集與種子集明確時影響力收益上下界評估

(12)

(13)

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

.

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

.

3

.

2

.

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

(14)

(15)

證明

.

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

則有

證畢

.

(16)

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

基于3.2節中影響力收益上下界評估方法，迭代算法的執行流程如算法2所示.

算法2.

迭代算法.

輸出：推廣目標位置集

L

*、影響力種子集

S

*

.

①

S

*←?，

L

*←?，

ratio

←0；

③ while

ratio

<1-1

/

e-

ε

④ if (Round=1)

⑥ else

⑨ end if

Greedy_MultiLoc為算法2中重要功能函數，其被算法2反復調用以實現不同輪次下對當前最優位置集的更新，其偽代碼如算法3所示

.

算法3.

Greedy_MultiLoc算法.

輸出：推廣目標位置集

L

*

.

①

L

*←?；② while |

L

*|<

m

④

L

*←

L

*∪{

l

}；

⑤ end while

⑥ return

L

*

.

接下來進行結果置信度分析

.

假設算法2中while循環的最大迭代次數為

r

.

由于每輪迭代中，影響力收益上下界評估將產生2

δ

的出錯概率，故算法在所有輪次下累計出錯的概率為2

δ

×

r

.

因此，將以1-2

δ

×

r

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

.

通常情況下，設定參數

δ

=1

/

|

V

|，由于算法2在實際執行過程中的迭代次數遠小于|

V

|，因而1-2

δ

×

r

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

/

e-

ε

)下的近似求解

.

4 實驗評估

4.1 數據集與測試環境

為驗證本文研究內容及所提技術方法的有效性，本節使用2組真實的地理社交網絡數據集：Brightkite和Gowalla進行實驗評估.數據集可通過Stanford大學的SNAP項目在線獲取.在Brightkite和Gowalla中，分別有11.4%和45.6%的用戶無位置坐標，對于這部分用戶，根據其朋友位置坐標的均值對其進行位置分配.處理后的數據集信息如表2所示:

Table 2 Statistics of the Datasets

實驗測試的算法均使用C++語言編寫，并在g++13編譯器下編譯優化.所有實驗在配備有Intel i-7 2.9 GHz主頻CPU，64 GB內存的PC機上運行，安裝的操作系統為Ubuntu 14.04.

4.2 實驗設定

1) 傳播概率設定.參考當前IM研究領域中廣泛使用的方法，本文采用加權級聯(weighted cascade)模型對社交網絡圖邊上影響力傳播概率進行分配：

p

(

u

,

v

)=1

/

|

N

(

v

)|，其中|

N

(

v

)|表示用戶

v

在社交網絡中的入度

.

3) 影響力收益值評估.為客觀評估不同算法所求結果的質量，實驗對種子影響力傳播過程進行10 000次蒙特卡羅(Monte Carlo, MC)模擬，并將此過程中被激活用戶權重和的均值作為種子影響力收益.

4) 參數設定.為評估不同參數設置對算法的影響，我們在不同參數設定下對算法性能進行評估.各參數設定值的范圍如表3所示，每行中黑體數字表示各參數的默認設定值.在評估參數性能時，我們僅改變其中某個參數的值，而固定其余參數為默認設定值.

Table 3 Parameter Settings

4.3 有效性評估

為了驗證本文研究內容在空間感知影響力聯合推廣中的有效性，本節將LA-JIP策略下產生的影響力收益情況與下述策略進行對比：

3) Baseline策略.本文所提算法1(基準算法)，即解決問題的啟發式算法；

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

Fig. 3 The distribution of the users located in Dallas圖3 達拉斯市區范圍內用戶分布情況

Fig. 4 The performance comparison of influence promotion for bars by different strategies圖4 酒吧類興趣點集合下不同策略的影響力 推廣效果對比

Fig. 5 The performance comparison of influence promotion for markets by different strategies圖5 商場類興趣點集合下不同策略的影響力 推廣效果對比

設置

m

=2，

k

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

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

4.4 算法性能評估

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

4.4.1 種子個數對性能的影響

本文在Brightkite和Gowalla兩組數據集下測試不同的種子個數(5,10,15,20,25)對BA與IT算法性能的影響，結果如圖6所示.從圖6結果可知，IT算法能夠在BA算法基礎上進一步提升10%～50%的影響力傳播收益，且運行效率有1～2個數量級的提升.這驗證了本文第3節中所提方法的有效性.此外，隨著種子個數的增多，所有算法的響應時間及影響力傳播收益均呈現增長趨勢.這是因為較多的種子能觸發更大的影響力傳播范圍，從而提高了影響力在用戶中傳播所能獲得的收益；這同時也增加了算法在評估種子影響力過程中的開銷.值得注意的是，所有算法在Gowalla數據集下均獲得了比Brightkite數據集下更高的影響力收益.這是因為Gowalla相比Brightkite擁有更大的社交網絡以及更為稠密的用戶空間分布，因而Gowalla數據集下產生的種子能夠激活更多高權重的用戶，從而利于影響力在傳播過程中積累到更多收益.這一對比結果體現了迭代算法在大規模社交圖下實現空間感知影響力推廣的性能優勢.

Fig. 6 The effect of varying k on performance圖6 種子個數k變化對算法性能的影響

4.4.2 推廣目標位置個數對性能的影響

Fig. 7 The effect of varying m on performance圖7 推廣目標位置個數m變化對算法性能的影響

圖7展示了推廣目標位置個數對算法性能的影響.在不同的位置個數設定下，迭代算法的性能均明顯優于基準算法，且在更大規模的Gowalla數據集上迭代算法較基準算法的性能優勢更為明顯.隨著推廣目標位置個數的增多，各算法取得的影響力收益均呈現增長趨勢.這是因為推廣位置的增加將使更多用戶因鄰近空間對象而擁有更大的推廣權重，因而影響力傳播過程將獲得更大的收益.值得注意的是，當推廣位置較多時(|

L

|≥4)，基準算法與迭代算法間性能分化趨勢更為明顯，這進一步體現了迭代算法在多目標組合優化處理中的優勢.

4.4.3 侯選位置集合大小對性能的影響

圖8展示了候選位置集合大小的變化對算法性能的影響.在不同規模的候選位置集合下，迭代算法的性能均明顯優于基準算法.此外，隨著候選位置集合的增大，各算法所得結果的影響力收益呈現先增加后逐漸趨于穩定的趨勢.這是因為當候選位置集合規模較小時，加入更多的位置可使算法構建出與影響力空間分布更為擬合的推廣目標位置分布.然而，當候選位置集增加至一定規模后，集合中的大量位置之間將存在較多的影響力重疊，從而使得影響力傳播收益的增幅呈現減緩趨勢.

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

4.5 對ε參數設定的評估

Fig. 9 Evaluate parameter ε in Brightkite dataset圖9 Brightkite數據集下評估參數ε

Fig. 10 Evaluate parameter ε in Gowalla dataset圖10 Gowalla數據集下評估參數ε

本節進一步探索迭代算法中對精度誤差參數

ε

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

ε

的運行結果(影響力收益、響應時間、RR set采樣規模).從圖9中結果可知，當

ε

值較小時(

ε

<0.20)，進一步減小ε對算法返回的結果精度提升效果并不明顯；相反，還將導致算法的響應時間急劇增長，并在處理過程中耗費大量的內存開銷(大量RR set被采樣產生并作為中間結果常駐內存).當精度誤差參數設定較大時(

ε

≥0.20)，算法時間空間上的開銷都明顯降低，但結果精度損失卻下降明顯.權衡算法的求解效率與返回結果的質量，本文將

ε

=0.20作為迭代算法的默認精度誤差參數.

5 總 結

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

k

近鄰排序等)來設計更為合理的用戶權重度量函數，以使LA-JIP問題適應更多復雜的應用場景.此外進一步優化提升本文提出的近似算法的理論精度也是未來努力的方向之一.

作者貢獻聲明

：金鵬飛負責提出問題研究的動機與思路、算法設計方案、實驗方案并撰寫論文；常雪芹負責算法方案實現、實驗測試、結果評估并協助撰寫論文；房子荃與李淼提出指導意見并修改完善論文.