社交網絡中多渠道影響最大化方法

李小康　張　茜　孫　昊　孫廣中

(安徽省高性能計算重點實驗室(中國科學技術大學計算機學院)　合肥　230026)

?

社交網絡中多渠道影響最大化方法

李小康張茜孫昊孫廣中

(安徽省高性能計算重點實驗室(中國科學技術大學計算機學院)合肥230026)

(國防科學技術大學高性能計算協同創新中心長沙410073)

(lxk727@mail.ustc.edu.cn)

社交網絡因為其流行性，近些年得到學術界的廣泛關注，社交網絡影響最大化是社交網絡領域中最流行的問題之一.經典的影響最大化問題是從網絡中選取k個初始用戶，作為種子用戶，讓其在網絡中傳播影響，使得最終受影響的用戶數最大化.以往的絕大部分工作針對于單個網絡的傳播，真實情況下信息是借助多個網絡傳播的.考慮到信息在多個網絡中的傳播，提出社交網絡中多渠道影響最大化問題，從多個網絡中選取k個種子用戶，讓其同時在多個網絡中傳播影響，使最終受種子用戶影響的用戶量最大化.將該問題規約為社交網絡影響最大化問題，證明其在獨立級聯模型下是NP難的.根據問題的特性，提出3種有效的近似解決方法，并在4個真實的社交網絡數據中進行實驗.實驗表明3種的方法能夠有效地解決多渠道下的影響力最大化問題.

社交網絡；影響最大化；多渠道；NP難；近似方法

近些年來，隨著Facebook和微博等社交網絡的流行，越來越多的用戶喜歡在社交網絡中分享自己的觀點和其他信息，使得網絡影響力傳播的研究成為社交網絡分析的熱點.

通常情況下，用戶在網絡中有且僅有2種狀態：激活和未激活狀態，激活表示用戶受到某觀點的影響，未激活表示未受到影響.為了更好地描述信息或者觀點在網絡中的傳播，Goldenberg等人[1]提出獨立級聯(independentcascade,IC)模型，IC模型中，用戶以一定的概率影響其鄰居結點；Granovertter[2]認為用戶有一定的堅持度，如果其鄰居的激活概率之和大于這個堅持度，則激活該用戶，他們提出線性閾值(linearthreshold,LT)模型.IC和LT雖然得到廣泛的關注，但是真實世界的影響傳播是非常復雜的，一些工作提出基于負面觀點的獨立級聯模型[3]、帶有時間限制的獨立級聯模型[4]和多實體競爭和協作的獨立級聯模型[5-6]等.

Kempe等人[7]形式化影響最大化問題，并且證明該問題是NP難的.他們提出貪心方法解決該問題，貪心方法被證明具有1-1e的最優保證.貪心方法迭代地選取最具影響增量(種子集合加入該結點帶來的影響增量)的結點，每次的選取都會計算所有結點的影響增量，這樣的策略是非常低效的.一些工作對經典的方法做改進，效率有一定提升[8-9]，但是很難擴展到很大的網絡中.一些學者提出一些啟發式的方法[10-13]，這些方法在效率上有很大提升，實驗的效果表現很好，但是缺少理論保證.最近有些學者提出一些接近線性的解決方法，而且這些方法具有最優的理論保證[14-16].

影響最大化問題最近得到廣泛的研究，考慮社交網絡中的真實場景，一些學者提出影響最大化問題的一些變型，他們提出個性化的影響最大化[17]、基于主題的(在線)影響最大化[18-20]、基于特定用戶的在線影響最大化[21-22]、基于位置的在線影響最大化[23]、基于信息覆蓋的影響最大化[24]、一定預算下的影響最大化問題[25]，Nguyen等人[26-27]和Zhan等人[28]將影響最大化問題引入到多重網絡.

上述工作中影響力的傳播絕大部分是基于單個網絡，而現實世界中個體之間的傳播網絡復雜很多，對于同一信息我們會同時借助多個不同的網絡進行傳播，如圖1所示.最典型的應用場景是校園生活，比如學校舉辦一場報告會，我們選擇一小部分比較有影響力的學生，讓其在朋友同學之間進行宣傳，目標是使來聽報告的學生數最大化.學生間宣傳途徑并非單一的，既可以采用傳統線下方式口頭宣傳，也可以借助微博、微信、人人網等多種社交網絡傳播影響.

Fig. 1　Process of information propagation.圖1　信息傳播過程

雖然Nguyen等人[26-27]提出了多重網絡影響最大化問題，但是他們問題的模型依賴性很強，只適用于線性閾值模型.我們將問題擴展到更寬泛的影響傳播模型，提出了多渠道的影響最大化問題，并形式化定義該問題.我們證明該問題是NP難的，根據該問題的特性，提出3種有效的近似解決方案.真實網絡上的實驗表明我們提出方法的有效性.本文的貢獻如下：

1) 提出多渠道的影響最大化問題，對該問題進行數學化的描述.該問題是根據真實的場景抽象，具有一定的價值.

2) 證明多渠道的影響最大化在獨立級聯模型下是NP難問題.將該問題歸納為基本的影響最大化問題，證明其是NP難的.

3) 針對該問題，本文提出3種近似的解決方案.通過分析問題的具體特性，參照基本影響最大化的算法，我們提出3種近似的解決方法——貪心方法、基于結點度的方法和基于反向可達集的方法.實驗結果表明我們提出方法的有效性.

多渠道影響最大化問題跟多網絡相關的問題[26-28]具有一個共同點，都是針對于多個網絡，但是具有很大的不同點：1)以往的問題只是針對于改進的線性閾值模型，而我們的問題主要側重于獨立級聯模型，而且能夠適用于目前絕大部分影響傳播模型；2)以往的問題中，多網絡的結點集合是不相同的，而我們的問題是針對于特定用戶集的，多個網絡的結點集合是相同的；3)以往的問題中，結點在多個網絡上的傳播是交叉的，我們的問題側重于多渠道之間并行傳播影響，結點在多個網絡的傳播過程是不交叉的.

1　相關工作

隨著社交網絡的興起和發展，影響最大化問題得到人們的廣泛關注.影響最大化是從網絡中選取k個種子結點，讓其按照一定的傳播模型，在網絡中傳播影響，最終使受影響的個體最大化.Kempe等人[7]用數學符號形式化該問題，證明該問題在獨立級聯模型下是NP難的，并提出具有1-1e最優的貪心方法，他們還證明影響力函數具有非負、單調遞增和子模特性(sub-modular).因為影響最大化在社交網絡中的重要性，近些年來大量的工作改進該問題.我們將這些工作劃分為3類：基本方法的改進、傳播模型的改進及基本問題的改進.

1.1基本方法的改進

貪心方法每次選取最具影響力結點時，需要計算每個結點的影響增量，獨立級聯模型下為了獲取比較精確的結果，種子結合影響力的計算需要有數萬次蒙特卡羅的模擬，導致其效率非常低，很難擴展到較大的社交網絡中.在一個中等的社交網絡(大概1.5萬個結點)中，利用貪心方法選取50個種子結點，在目前大眾配置的機器上，需要花費數天的時間，低效率嚴重限制貪心方法的使用.Leskovec等人[8]利用影響力函數的子模特性，使用優先隊列存儲結點的影響增量，大幅度地減少種子結點選取過程中影響增量的計算，提出CELF方法，實驗表明CELF比起貪心方法大概有700倍的效率提升.Goyal等人[9]提出針對CELF方法的改進版本CELF++，CELF++在上次迭代計算中保存一定的計算結果，減少在下次迭代過程中的計算，實驗表明比起CELF方法，CELF++在效率上有大概2倍的提升.

盡管CELF++比起貪心方法已經有很大的提升，仍然很難擴展到很大規模的社交網絡中.Chen等人[10]提出一些啟發式的方法，比如基于度的方法、基于路徑的方法[11-12]，這些方法在效率上有很大幅度的提升，而且實驗表明他們選擇種子集帶來的影響力接近貪心方法選取達到的影響力，但是他們有一個明顯的缺點：方法達到的影響力沒有理論保證.Wang等人[13]提出了基于數據重建的方法，該方法從一個全新的角度解決問題，實驗表明他們效果幾乎逼近貪心方法的，但是仍然沒有理論的保證.

Borgs等人[14]提出一個具有理論保證的接近線性時間的方法RIS.RIS分2部分：結點反向可達集(RRS)和種子結點選擇過程，RIS的主要貢獻是舍棄用蒙特卡羅模擬計算結點的影響力，而是用結點的反向可達集模擬結點的影響力.Tang等人[15-16]證明了結點反向可達集的數量，提出2步法TIM和TIM+方法，他們還對種子結點選擇過程進行優化，提出基于邊緣的方法IMM，TIM和IMM的貢獻是在保證影響力具有理論保證的情況下，確定反向可達集的具體數量.實驗表明IMM的效率已經超過啟發式方法，比如IRIE[12].TIMTIM+和IMM方法的時間復雜度接近線性，具有一定的理論保證，而且適用于獨立級聯、線性閾值和更廣泛的模型.

1.2傳播模型的改進

獨立級聯和線性閾值是2個最廣泛的影響傳播模型.獨立級聯有2個變型：權重級聯(weightcascade,WC)和多價模型(multivalentmodel)，權重級聯模型中，每條邊的激活概率被設置為被指向結點入度的倒數；多價模型是預先設置一個傳播概率集合，從該集合中隨機選取一個值作為該條邊的傳播概率，改進的模型廣泛應用于文獻[10-13]中.

一些學者考慮到影響傳播過程中的具體細節，對基本模型做了擴展.1)考慮到影響傳播過程中負面觀點的出現，提出負面獨立級聯(independentcascadenegative,IC-N)模型[3].IC-N中結點有3個狀態：正面激活、未激活和負面激活.而且引入參數質量因子q，如果結點被負面結點激活，則保持負面激活狀態，如果被正面結點激活，則該結點以概率q保持正面激活狀態，以1-q概率變成負面激活狀態；2)考慮到影響的傳播存在競爭關系，提出競爭線性閾值模型(competitivelinearthreshold,CLT)[5].CLT中每條邊有2個激活概率，分別表示正面激活概率和負面激活概率；3)考慮到結點之間的影響具有時限性，提出時限性獨立級聯模型(independentcascademodelwithmeetingevents,IC-M)[4].IC-M中，每個結點激活其鄰居結點之前，以一定的概率檢測該條邊鏈接是否過期，如果未過期，則執行激活過程，否則認為其結點不能激活該鄰居結點；4)考慮到多個實體在網絡中傳播影響時，會存在競爭或者互補的關系，提出比較性獨立級聯模型(comparativeindependentcascademodel,Com-IC)[6].Com-IC包括2個主要元素：邊階的信息傳播(edge-levelinfor-mationpropagation)和頂點階自動化(node-levelautomation)，這2個元素使最終的采納決策(影響)依賴于全局采納概率(globaladoptionprobability).

1.3基本問題的改進

基本的影響最大化問題是從網絡中選取k個結點，使受影響的用戶最大化，一些學者考慮到現實網絡的具體情況，提出影響最大化的各種變型.Guo等人[17]提出個性化的影響最大化，對于給定的結點，求對該結點最具影響力的k個結點；一些工作考慮到用戶興趣，提出基于主題興趣的在線影響最大化問題[18-20]，對于給定的用戶行為對興趣的影響，求種子結合，使得影響的用戶量最大化，該問題的貢獻是對于給定的用戶行為對興趣的影響，求得用戶間的影響概率；另外一些工作優化特定結點集合影響力，提出基于特定用戶的影響最大化問題[21-23]，給定特定的用戶集，求種子集，使這些用戶的影響最大化；Wang等人[24]將激活結點的鄰居看作信息結點，提出信息影響最大化問題，考慮到選取種子結點是有代價的，Goyal等人[25]提出了一定預算下的影響最大化問題，對于給定的預算，該問題是從網絡中選取少部分結點，使得其在網絡中影響的結點數最大化.Nguyen等人[26-27]考慮到影響在多個網絡中的傳播，提出了改進的線性閾值模型下的多重網絡影響最大化問題，Zhan等人[28]提出了多重網絡影響最大化的改進版本——異構網絡影響最大化問題.

2　先驗知識

社交網絡可以用圖的模型G=(V,E)來抽象，V是圖中的結點集合，表示社交網絡中的用戶集合；E表示圖中邊的集合，代表網絡中用戶之間的關系.本節主要介紹社交網絡影響最大化的形式化定義及獨立級聯模型的傳播過程.

2.1影響最大化

對于給定的圖G=(V,E)和整數k，影響最大化是從圖中選取一個大小為k的結點集合S，作為種子集合，讓其在網絡中傳播影響，使得最終的影響力|R(S)|最大，其中R(S)是被種子集合S影響的結點集合，影響最大化問題形式化描述為

(1)

其中，|S|=k,S?V.

Kempe等人[7]證明影響最大化是NP難的.

2.2獨立級聯模型

獨立級聯是一種被研究者廣泛關注的影響傳播模型，該模型中參數pv,w是結點v對其鄰居結點w的激活概率，無論是否激活w，v只有一次激活w的機會，而且該過程是獨立的，即對w的激活不會受其他結點影響，新激活的結點又會以一定的概率pv,w激活其未激活的鄰居結點，直到沒有新激活的結點，激活過程結束.激活的結點只有一次機會去激活其鄰居結點.一個激活結點激活鄰居結點的具體過程如下：

1) 激活的結點放入激活隊列中；

2) 激活隊列隊首出隊，以一定的概率激活其鄰居結點；若激活，則將鄰居結點入隊；

3) 重復過程2)，直到激活隊列為空.

3　問題定義

本節我們對多渠道影響最大化問題給出一個形式化的定義，并證明該問題是NP難的.

對于給定的z個網絡G1,G2,…,Gz，Gi=(V,Ei)和整數k，多渠道影響最大化是從z個網絡中選取k個結點，作為種子集合，讓其分別在z個網絡中傳播影響，使得z個網絡中影響集合并集的元素數最多.多渠道影響最大化可以形式化為

(2)

其中，Ri(S)是種子集S在網絡Gi中傳播影響時影響的結點集合，|S|=k,S?V.

我們的問題針對特定目標的用戶，所以不同網絡Gi的結點集合是相同的.

定理1. 對于多個社交網絡，在獨立級聯模型下，多渠道影響最大化是NP難問題.

證明. 當網絡個數z=1時，多渠道影響最大化問題就轉換為經典的影響最大化問題，所以影響最大化問題是多重影響最大化問題的一個特例，Kempe等人[7]證明經典的影響最大化問題是NP難的，因此多重影響最大化在獨立級聯模型下是NP難問題.

證畢.

4　解決方案

由第3節可知，多渠道影響最大化是NP難的，不存在多項式時間內的最優解.目前的算法存在一個明顯的不足——不適用于多渠道下影響力的計算.多渠道影響最大化下，初始用戶的影響力計算需要將初始用戶在不同網絡上的影響集合求并集.根據該問題的特性，我們提出了3種近似的解決方案：貪心方法、基于結點度的方法和基于合成圖的方法.

4.1貪心方法

算法1. 貪心方法.

輸入：G1,G2,…,Gz，k；

輸出：S.

S=?；

While|S|

S=S∪{v}；

EndWhile

OutputS.

貪心方法每次選取最具影響力結點時，需要計算每個結點的影響增量.獨立級聯模型下，為了獲取比較精確的結果，種子結合影響力的計算需要有數萬次蒙特卡羅的模擬，使其效率非常低下，很難擴展到數千個結點數百萬條邊的網絡中.為了滿足效率的需求，我們提出一個高效的啟發式方法：基于結點度的方法.

4.2基于結點度的方法

一個結點的出度越大，說明它能夠影響的鄰居越多，一定程度上反映它具有較大的影響力.基于結點度的方法首先計算所有結點在z個網絡的出度之和，每次選擇具有出度最大的結點，如果一個結點被選作種子結點，其入邊鄰居就不能再影響它，則其入邊鄰居的影響力就會減弱，這里我們簡單地減1處理，重復上述選擇過程直至選出k個種子結點，具體的過程如算法2.由算法2知，基于結點度的方法的時間復雜度為O(k(n+zd)+nz)，其中d是結點的平均度數.比起貪心方法，算法2在效率上有大幅度地提升，能夠擴展到更大的網絡中.

算法2. 基于結點度的方法.

輸入：G1,G2,…,Gz，k；

輸出：S.

S=?；

Foreachv∈V

EndFor

While|S|

S=S∪{v}；

Fori=1,2,…,zdo

Foreachw∈innodei(v)

degree(w)-=1；

EndFor

EndFor

EndWhile

OutputS.

在一些影響傳播模型下，基于結點度的方法是一種簡單有效的方法，但是它有一個基本的假設：結點的出度能夠反映結點在網絡中的影響力，在經典的獨立級聯模型下，任意2個結點間的激活概率是相等的，結點的一度(與結點直接相連) 影響力基本可以近似結點的真實影響力，因為結點的二度三度影響力是指數下降的，與一度影響力相比基本可以忽略不計.但是如果結點間的激活概率不相等時，比如權重級聯模型(WC)，該方法的假設就不再合理，因此基于結點度的方法的適用范圍有限.提出一種用于解決多渠道影響最大化問題、效率高、表現好、能適用于多種影響傳播模型的方法是非常有必要的.

4.3基于反向可達集的方法

多渠道影響最大化問題計算種子集合S的影響力時，首先計算S在不同網絡Gi的影響集合Ri(S)，然后對不同的影響集合求并集，得到S在多渠道上的影響力|R(S)|.由于多渠道影響最大化問題影響力的計算需要同時計算不同網絡的影響集合，目前流行的方法，比如TIM+[15]和IMM[16]，不能直接解決多渠道的影響最大化.

種子集合S的影響力計算過程中，需要同時計算在不同網絡中的影響集合，如果一條邊(u,v)在z個網絡都出現，u對v的激活過程簡單認為在一個網絡中進行z次，我們將z個網絡Gi轉換成一個網絡G.在G中，結點u對結點v的激活概率pu,v如式(3):

(3)

得到網絡G后，我們借鑒最新的線性方法[14-16]，提出基于反向可達集的方法.基于反向可達集的方法分2步：1)有放回地從結點集合V中隨機選擇一些結點，在轉置圖上，進行廣度優先搜索(BFS)或者深度優先搜索(DFS)去激活其鄰居結點，所有激活的結點組成一個反向可達集(reversereachableset)，RR是反向可達集的結合，大小為θ；2)使用最大覆蓋方法[29]選擇種子集合，首先，選擇反向可達集最大覆蓋結點加入種子集合S，然后刪除包含該結點的反向可達集，重復此過程，直至選取k個種子結點，具體過程如算法3.算法3反向可達集數量θ是受參數ε控制的.

算法3. 基于反向可達集的方法.

輸入：G1,G2,…,Gz，k；

輸出：S.

S=?;RR=?；

Fori=1,2,…,θdo

從G中隨機選擇結點u；

計算u的反向集合RRi；

RR=RR∪RRi；

EndFor

Fori=1,2,…,kdo

選擇對RR具有最大覆蓋的結點u；

S=S∪{u}；

從RR中刪除包含結點u的集合；

EndFor

OutputS.

基于反向可達集的方法主要有2個過程：合成圖G的生成和從G中選取種子集.如果圖中邊的影響概率是以散列表的形式存儲，則合成圖過程的時間復雜度為O(m),從G中選取種子集合過程可以在一個接近現實時間內完成.因此比起貪心的方法，基于反向可達集的方法效率是非常高的.

5　實　　驗

本節主要介紹實驗的基本設置及實驗結果與分析.

5.1實驗設置

我們使用4個真實的數據集：Gnu網絡、Wiki-Vote網絡、Hept網絡和Phy網絡，這些數據廣泛應用于很多工作中[9-16].Gnu是Gnutella文件貢獻網絡，Wiki-Vote是維基百科的投票網絡，這2個數據可以從Stanford大學的SNAP項目[30]下載；GrQc和HepTh是文章合作網絡，分別來自廣義相對論量子宇宙和高能源物理，可以從Stanford大學的SNAP項目下載[30]，數據的詳細信息如表1所示.為了模擬信息在多渠道的傳播，我們將網絡數量z設置為2，網絡G2和網絡G1是在原始網絡中隨機刪除20%的邊.

Table1　Details of Network on Experiments表1　實驗網絡的詳細信息

本次實驗是基于IC模型和WC模型的.IC模型下結點間的影響概率p=0.01；WC模型下，結點u對其鄰居結點v的影響力設為結點v的入度的倒數1indegree(v)，其中indegree(v)是結點v的入度.為了得到較為準確的影響力，實驗中所有影響力的計算，我們使用蒙特卡羅模擬，模擬次數r=20 000，基于反向可達集的方法中的ε=0.1.實驗中我們共使用4種方法.

1) 在4.1節提出的貪心方法.

2) 在4.2節提出的基于結點度的方法.

3) 在4.3節提出的基于反向可達集的方法.

4) 隨機的方法，從結點集合中隨機選取k個種子結點，該方法曾作為對比方法敘述于文獻[7,10]中.

實驗程序是用C++實現的，運行于Linux服務器上。服務器的CPU配置為Intel?CoreTMi5-4460CPU@ 3.20GHz，內存為8GB.

5.2實驗結果與分析

1) 影響力比較.

我們在4個真實的數據集上實驗測試種子數量從1～50，將4種方法選取的種子結點在多渠道上傳播影響，用蒙特卡羅模擬其影響力，具體的結果如圖2、圖3所示，圖2和圖3分別是在IC模型和WC模型下的結果，其中hgreedy，hdegree，himm分別表示我們提出的用于解決多渠道影響最大化的貪心方法、基于結點度的方法和基于反向可達集的方法，random表示隨機的方法，分圖(a)～(d)分別表示在Gnu，Wiki-Vote，GrQc，HepTh網絡的影響力.

Fig. 2　Influence spread of different methods on 4 real datasets under IC model.圖2　IC模型不同的方法在4個真實數據上得到的影響力

Fig. 3　Influence spread of different methods on 4 real datasets under WC model.圖3　WC模型不同的方法在4個真實數據上得到的影響力

由圖2和圖3可知，隨機的方法效果最差，主要是因為它選擇種子結點只是隨機地選擇k個種子結點，并不依賴于網絡的拓撲和結點間的影響力.當種子個數比較少時，貪心方法、基于結點度的方法和基于反向可達集的方法表現相當，因為他們都是基于一定的貪心策略選擇，這些策略一定程度上能夠反映結點的影響力.

由圖2可知，基于反向可達集的方法和基于結點度的方法的表現明顯高于貪心方法.基于反向可達集的方法是用結點覆蓋反向可達集的數量來預估其影響力，每選擇一個最大覆蓋的結點會刪除其覆蓋的反向可達集.基于結點度的方法優先選擇度大的結點，IC模型下，每條邊的激活概率相同，結點的出度基本反映其影響力，而且這2種方法每次的種子結點選擇會降低其鄰居結點影響力，使得最終的種子結點能夠覆蓋網絡中的較大區域.多渠道下影響力函數并不滿足子模特性，貪心地選擇種子結點很容易得到局部最優解.

由圖3可知，WC模型下基于反向可達集的方法仍然表現很好，主要是該方法不依賴于邊的影響概率，適用于絕大部分傳播模型.而基于結點度的方法在不同數據網絡上的表現差異很大，WC模型下每條邊的激活概率不等，結點的出度并不能對應結點的影響力，仍然依靠出度去選種子結點，選出的種子集合不一定能夠帶來很大的影響力.

2) 效率比較.

為了比較各種方法的效率，我們測試4種方法在HepTh網絡上選取50個種子集合所用的時間，我們在IC和WC模型下分別測試，具體的結果如表2所示.由表2可知，隨機方法和基于結點度的方法效率是非常高的，前者僅依賴于網絡中結點的數量和種子的數量，后者還依賴結點的度，這些量一般是給定的或者是很容易計算.貪心方法在選擇種子結點時，需要模擬每個結點加入種子集合后的影響力，而每次模擬需要有數萬次的蒙特卡羅的模擬，所以貪心方法效率非常低，基于反向可達集的方法用結點覆蓋反向可達集的數量近似模擬結點的影響力，替代蒙特卡羅的模擬，而且每個結點的近似影響力只需要計算一次，因此其效率非常高.

Table 2　Running Time Comparison of Different Methods表2　不同方法運行時間對比

3) 網絡個數討論.

Fig. 4　Influence spread comparison under different number of networks.圖4　不同網絡個數下影響力對比

圖4展示了在Wiki-Vote網絡上，針對多渠道下影響最大化問題中不同網絡個數，選取50個種子結點在對應網絡個數上的影響力，我們分別測試在2種傳播模型：IC模型和WC模型，其中HIM1，HIM2，HIM3分別表示在網絡G1、2個網絡(G1和G2)和3個網絡(G1，G2，G3)上，使用基于反向可達集的方法選取的種子集合在各自不同的網絡上產生的影響力.網絡G3的獲取方式是與網絡G1和G2是一樣的，從原始網絡中隨機刪除20%的邊，實驗中我們最多模擬3個網絡，因為現實世界中，主流的社交網絡個數比較少.由圖4可知，隨著網絡個數的增加，選取同樣大小的種子集合，產生的影響力越大，而且影響的增量會有一定的下降，2個網絡與1個網絡相比，IC模型和WC模型下影響力分別有66.75%和59.24%的提升，3個網絡與2個網絡相比，IC模型和WC模型下影響力分別有28.14%和21.87%的提升.直觀地理解，信息在多個網絡中傳播影響會比在單個網絡中產生的影響大，從側面說明我們提出問題的合理性.

4) 采樣比例討論與單網絡方法對比.

本次實驗有2個目標：①比較不同邊采樣下的影響力；②比較我們提出的方法與對應的單網絡方法產生的影響力.我們在Gnu網絡上的WC模型下，從原始網絡中隨機刪除20%，30%，50%的邊生成相應的網絡，使用基于結點度的方法與其對應的單網絡影響最大化方法選取50個種子結點，然后計算其影響力.具體結果如圖5所示，其中WC2，WC3，WC5分別表示網絡是從原始網絡中隨機刪除20%，30%，50%的邊，hdegree，degree分別表示我們提出的基于結點度的方法與其對應的單網絡的方法(用基于結點度的方法從其中一個網絡中選取種子集合).

Fig. 5　Edge sample ratio discuss and comparison with method for single network.圖5　邊采樣比例討論與單網絡方法對比

由圖5可知，隨著網絡中邊數量的增加，同一種方法選取相同的數量的種子結點，在相應的網絡中產生的影響力隨之增加，因為網絡中邊數量越多，種子結點能激活的鄰居結點越多，最終受影響的結點數量越多，則產生的影響力越大.不同比例的邊采樣的情況下，基于結點度的方法選取的種子集合產生的影響力比其對應的單網絡方法選取的種子集合產生的影響力大，因為單網絡的方法是從其中一個網絡中選取種子結點，相當于選取種子結合時只依靠部分信息，選取的種子結點難免產生較差的影響力.

6　結束語

考慮到信息或者觀點的傳播會借助多個網絡，本文提出多渠道影響最大化問題，用數學的方法形式化該問題；通過將多渠道影響最大化問題歸納為基本的影響最大化問題，我們證明多渠道影響最大化是NP難問題；針對該問題的基本特性，我們提出3種近似的解決方法：貪心方法、基于結點度的方法和基于反向可達集的方法；真實網絡上的實驗結果表明我們提出方法的有效性.

本文提出了多渠道影響的影響最大化問題，接下來的工作會側重3個方面：1)深入理解問題的性質，找到效率更高的計算影響力的方法；2)尋找用于解決多渠道影響最大化問題效率更高、效果更好的方法；3)針對種子結點在多個網絡傳播影響的獨立性，使用并行的策略優化影響力的計算.

[1]GoldenbergJ,LibaiB,MullerE.Talkofthenetwork:Acomplexsystemslookattheunderlyingprocessofword-of-mouth[J].MarketingLetters, 2001, 12(3): 211-223

[2]GranovetterM.Thresholdmodelsofcollectivebehavior[J].AmericanJournalofSociology, 1978, 83(6): 1420-1443

[3]ChenW,CollinsA,CummingsR,etal.Influencemaximizationinsocialnetworkswhennegativeopinionsmayemergeandpropagate[C] //Procofthe11thSIAMIntConfonDataMining(ICDM).Philadelphia,PA:SIAM, 2011: 379-390

[4]ChenW,LuW,ZhangN.Time-criticalinfluencemaximizationinsocialnetworkswithtime-delayeddiffusionprocess[C] //Procofthe26thConfonArtificialIntelligence.PaloAlto,CA:AAAI, 2012

[5]HeX,SongG,ChenW,etal.Influenceblockingmaximizationinsocialnetworksunderthecompetitivelinearthresholdmodel[C] //Procofthe12thSIAMIntConfonDataMining.Philadelphia,PA:SIAM, 2012: 463-474

[6]LuW,ChenW,LakshmananLVS.Fromcompetitiontocomplementarity:Comparativeinfluencediffusionandmaximization[J].VLDBEndowment, 2015, 9(2): 60-71

[7]KempeD,KleinbergJ,Tardosé.Maximizingthespreadofinfluencethroughasocialnetwork[C] //Procofthe9thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2003: 137-146

[8]LeskovecJ,KrauseA,GuestrinC,etal.Cost-effectiveoutbreakdetectioninnetworks[C] //Procofthe13thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2007: 420-429

[9]GoyalA,LuW,LakshmananLVS.CELF++:Optimizingthegreedyalgorithmforinfluencemaximizationinsocialnetworks[C] //Procofthe20thIntConfCompaniononWorldWideWeb.NewYork:ACM, 2011: 47-48

[10]ChenW,WangY,YangS.Efficientinfluencemaximizationinsocialnetworks[C] //Procofthe15thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2009: 199-208

[11]ChenW,WangC,WangY.Scalableinfluencemaximizationforprevalentviralmarketinginlarge-scalesocialnetworks[C] //Procofthe16thACMSIGKDDIntConfonKnowledgeDiscoveryandDataMining.NewYork:ACM, 2010: 1029-1038

[12]JungK,HeoW,ChenW.IRIE:Scalableandrobustinfluencemaximizationinsocialnetworks[C] //Procofthe12thIEEEIntConfDataMining(ICDM).Piscataway,NJ:IEEE, 2012: 918-923

[13]WangZ,WangH,LiuQ,etal.Influentialnodesselection:Adatareconstructionperspective[C] //Procofthe37thIntACMSIGIRConfonResearch&DevelopmentinInformationRetrieval.NewYork:ACM, 2014: 879-882

[14]BorgsC,BrautbarM,ChayesJ,etal.Maximizingsocialinfluenceinnearlyoptimaltime[C] //Procofthe25thAnnualACM-SIAMSymponDiscreteAlgorithms.Philadelphia,PA:SIAM, 2014: 946-957

[15]TangY,XiaoX,ShiY.Influencemaximization:Near-optimaltimecomplexitymeetspracticalefficiency[C] //Procofthe7thACMSIGMODIntConfonManagementofData.NewYork:ACM, 2014: 75-86

[16]TangY,ShiY,XiaoX.Influencemaximizationinnear-lineartime:Amartingaleapproach[C] //Procofthe8thACMSIGMODIntConfonManagementofData.NewYork:ACM, 2015: 1539-1554

[17]GuoJ,ZhangP,ZhouC,etal.Personalizedinfluencemaximizationonsocialnetworks[C] //Procofthe22ndACMIntConfonInformation&KnowledgeManagement.NewYork:ACM, 2013: 199-208

[18]Aslay?,BarbieriN,BonchiF,etal.Onlinetopic-awareinfluencemaximizationqueries[C//OL]. 2016[2016-03-10].http://www.francescobonchi.com//inflex.pdf

[19]ChenS,FanJ,LiG,etal.Onlinetopic-awareinfluencemaximization[J].VLDBEndowment, 2015, 8(6): 666-677

[20]LiY,ZhangD,TanKL.Real-timetargetedinfluencemaximizationforonlineadvertisements[J].VLDBEndowment, 2015, 8(10): 1070-1081

[21]LiFH,LiCT,ShanMK.Labeledinfluencemaximizationinsocialnetworksfortargetmarketing[C] //Procofthe3rdPrivacy,Security,RiskandTrust(PASSAT)andProcofthe3rdIntConfonSocialComputing(SocialCom).Piscataway,NJ:IEEE, 2011: 560-563

[22]LeeJR,ChungCW.Aqueryapproachforinfluencemaximizationonspecificusersinsocialnetworks[J].IEEETransonKnowledgeandDataEngineering, 2015, 27(2): 340-353

[23]LiG,ChenS,FengJ,etal.Efficientlocation-awareinfluencemaximization[C] //Procofthe7thACMSIGMODIntConfonManagementofData.NewYork:ACM, 2014: 87-98

[24]WangZ,ChenE,LiuQ,etal.Maximizingthecoverageofinformationpropagationinsocialnetworks[C] //Procofthe24thIntConfonArtificialIntelligence.PaloAlto,CA:AAAI, 2015: 2104-2110

[25]GoyalA,BonchiF,LakshmananLVS,etal.Onminimizingbudgetandtimeininfluencepropagationoversocialnetworks[J].SocialNetworkAnalysisandMining, 2013, 3(2): 179-192

[26]NguyenDT,DasS,ThaiMT.Influencemaximizationinmultipleonlinesocialnetworks[C] //Procofthe32ndtheGlobalCommunicationsConf(GLOBECOM).Piscataway,NJ:IEEE, 2013: 3060-3065

[27]NguyenDT,ZhangH,DasS,etal.Leastcostinfluenceinmultiplexsocialnetworks:Modelrepresentationandanalysis[C] //Procofthe13thIntConfonDataMining.Piscataway,NJ:IEEE, 2013: 567-576

[28]ZhanQ,ZhangJ,WangS,etal.Influencemaximizationacrosspartiallyalignedheterogenoussocialnetworks[C] //ProcofPacific-AsiaConfonKnowledgeDiscoveryandDataMining.Berlin:Springer, 2015: 58-69

[29]VaziraniVV.ApproximationAlgorithms[M].Berlin:SpringerScience&BusinessMedia, 2013

[30]LeskovecJ,KrevlA.SNAP[EB//OL]. 2016[2016-03-10].http://snap.stanford.edu//data

LiXiaokang,bornin1990.MasterfromtheUniversityofScienceandTechnologyofChina.Hismainresearchinterestsincludesocialnetwork,bigdataprocessingandprivacypreserving.

ZhangXi,bornin1993.MastercandidateintheUniversityofScienceandTechnologyofChina.Hermainresearchinterestsincludedatamining.

SunHao,bornin1994.MastercandidateintheUniversityofScienceandTechnologyofChina.Hismainresearchinterestsincludebigdataanalysis.

SunGuangzhong,bornin1978.PhD,associateprofessorintheUniversityofScienceandTechnologyofChina.Hismainresearchinterestincludehighper-formancecomputing,algorithmoptimiza-tionandbigdataanalysis.

InfluenceMaximizationAcrossMulti-ChannelsinSocialNetwork

LiXiaokang,ZhangXi,SunHao,andSunGuangzhong

(Anhui Province Key Laboratory of High Performance Computing (School of Computer Science, University of Science and Technology of China), Hefei 230026) (Collaborative Innovation Center of High Performance Computing, National University of Defense Technology, Changsha 410073)

Socialnetworkshavewidelyattractedtheinterestsofresearchersinrecentyearsbecauseoftheirpopularity.Influencemaximizationinsocialnetworkisoneofthemostpopularproblemsofsocialnetworkfields.Influencemaximizationinsocialnetworkisaproblemtopickupkseedusersfromasocialnetwork,targetthemasseedusersandpropagateinfluenceviathenetwork,withthegoalofmaximizingthenumberofusersinfluencedbyseednodes.Themajorityofpreviousworkisbasedonasinglechannel.However,inrealworld,informationispropagatedviamultiplechannels.Thispapertakesinformationspreadinmultiplenetworksintoconsideration,proposesandformulatesinfluencemaximizationproblemacrossmulti-channelsinsocialnetwork.Theproblembecomestopickupkseedusersfrommultiplenetworksandsimultaneouslypropagateinfluenceacrossmultiplenetworks,maximizingthenumberofinfluencedusersbyseedset.WeprovetheproblemisNP-hardunderindependentcascademodelthroughreducingitintoinfluencemaximizationinsocialnetwork.Accordingtothepropertyoftheproblem,weputforwardthreeefficientandeffectiveapproximationmethodsforit.Experimentsshowourproposedmethodsareeffectiveonfourrealsocialnetworks.

socialnetwork;influencemaximization;multi-channels;NP-hard;approximationmethods

2016-03-21；

2016-06-03

國家自然科學基金項目(61303047)

孫廣中(gzsun@ustc.edu.cn)

TP391

ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61303047).