基于k-核過濾的社交網(wǎng)絡影響最大化算法

李閱志，祝園園，鐘　鳴

(1.軟件工程國家重點實驗室(武漢大學)，武漢 430072;　2.武漢大學 計算機學院，武漢 430072)(*通信作者電子郵箱yyzhu@whu.edu.cn)

0　引言

隨著Facebook和微信微博等社交網(wǎng)絡的流行，越來越多的用戶喜歡在社交網(wǎng)絡中分享自己的觀點和其他信息，使得網(wǎng)絡影響力傳播的研究成為社交網(wǎng)絡分析的熱點[1]。 影響力最大化問題作為病毒式營銷和廣告投放等社交網(wǎng)絡推薦研究領域的一個重要問題，引起了廣泛的關注和研究熱情。

影響最大化問題最早由Domingos等[2]定義為如何尋找t個初始節(jié)點，使得信息的最終傳播范圍最廣。 Kempe等[3]將影響最大化定義為一個離散優(yōu)化問題，證實了這個問題在獨立級聯(lián)模型下是NP難問題，提出了對后續(xù)研究影響極大的兩種傳播模型：獨立級聯(lián)(Independent Cascade，IC)模型和線性閾值(Linear Threshhold，LT)模型，并基于子模性質(sub-modularity)提出了一個基本的貪心算法Greedy。 為了降低Greedy算法的時間復雜度，后來的研究者又提出了若干改進算法，如CELF(Cost-Effective Lazy Forward)算法[4]、DegreeDiscount算法[5]、核覆蓋算法(Core Covering Algorithm, CCA)[6]、PMIA(Prefix excluding Maximum Influence Arborescence)算法[7]、IRIE(Influence Rank Influence Estimation)算法[8]等。 其中PMIA算法和IRIE算法被認為是現(xiàn)有影響力最大化算法中影響范圍和時間效率排名靠前的算法。這些算法基本都使用了子模性質，雖然時間效率有了很大的提升，但是影響范圍效果仍然比不上Greedy算法[3]。

Kempe等[3]已經(jīng)證明具有子模性的影響范圍函數(shù)使用Greedy算法求解，能取得最優(yōu)解的63%[9]。該結論表明當前取得最大影響范圍的Greedy算法和最優(yōu)解仍有差距。 為了縮小現(xiàn)有影響最大化算法和最優(yōu)解的差距，本文提出一種采用k-核過濾的算法，可以應用于現(xiàn)有的大多數(shù)基于子模性質的影響最大化算法，擴大它們的影響范圍，降低它們的時間復雜度?；谠搆-核過濾算法，本文對PMIA算法、CCA、OutDegree算法、Random算法分別進行優(yōu)化，擴大了影響范圍， 降低了執(zhí)行時間，尤其對于CCA，在不減小影響范圍的情況下執(zhí)行時間縮短了28.5%。并且通過預訓練k首次發(fā)現(xiàn)同一算法在同一數(shù)據(jù)集上取得最佳優(yōu)化效果的k是固定值。李國良等[10]提出了一種針對多網(wǎng)絡實體影響最大化的算法，本文將k-核過濾算法結合該算法思想應用到單個社交網(wǎng)絡上，提出了一種新的影響最大化算法GIMS(General Influence Maximization in Social networks)，該算法比PMIA和IRIE的影響范圍更大，執(zhí)行時間更短。

1　傳播模型和問題定義

設有向圖G=(V,E)表示一個社交網(wǎng)絡，其中:V表示節(jié)點集合，n表示節(jié)點總數(shù)；E表示邊集，m表示邊的總數(shù)。?v∈V表示節(jié)點，?e(u,v)∈E表示一條u指向v的有向邊。

1.1　獨立級聯(lián)模型

獨立級聯(lián)模型是一個概率模型。對于網(wǎng)絡G中的每個節(jié)點都有兩個狀態(tài)：激活和未激活。每個節(jié)點只能從未激活狀態(tài)轉變?yōu)榧せ顮顟B(tài)，每個節(jié)點可以被它的相鄰節(jié)點激活。對于每條邊e(u,v)∈E，需指定一個影響概率p(u,v)∈[0,1],p(u,v)表示節(jié)點u通過邊e(u,v)影響節(jié)點v的概率。給定初始激活節(jié)點集合S0，傳播過程以如下方式進行：當傳播至第t+1步時，利用在第t步中被激活的節(jié)點，根據(jù)成功概率p(u,v)試圖去激活它們的鄰居節(jié)點，并將在這一步中被激活的節(jié)點加入到St形成St+1；重復這一過程，直至不再有新的節(jié)點被激活。整個過程中u只嘗試激活v一次，激活成功則v由未激活變?yōu)榧せ顮顟B(tài)，激活失敗則不再嘗試激活。

1.2　問題定義

定義1有向圖G=(V,E)中，給定一個輸入t，獨立級聯(lián)模型下的影響最大化(Influence Maximization, IM)問題是找到G一個節(jié)點子集S*∈V，S*的最終影響范圍σ(S*)滿足：

σ(S*)=max{σ(S)||S|=t,S?V}

s.t.|S*|=t

定義2一個集合函數(shù)f:2V→R是單調的，如果f(S)≤f(T)對所有S?T都成立。

定義3一個集合函數(shù)f:2V→R是子模的，如果f(S∪{u})-f(S)≥f(T∪{u})-f(T)對所有S?T?V和u∈V都成立。

Kempe等[3]證明了影響最大化問題是NP難問題，并且證明影響范圍函數(shù)滿足單調性和子模性，由此提出了可獲得(1-1/e)的近似最優(yōu)解Greedy算法。Greedy算法的影響范圍是現(xiàn)有影響最大化算法中效果最好的，能取得最優(yōu)解的63%[3]，但時間效率很低，執(zhí)行一次需要幾個小時甚至幾天。本文提出一種k-核過濾算法，可以擴大現(xiàn)有算法的影響范圍，并且降低算法的執(zhí)行時間復雜度。

2　基于k-核過濾的影響最大化算法

本文提出了一種k-核過濾算法，可以應用于很多影響最大化算法，擴大它們的影響范圍，縮短其執(zhí)行時間。同時，本文還提出了一種新的單社交網(wǎng)絡影響最大化算法GIMS，其影響范圍比廣泛認可的PMIA算法和IRIE算法效果更好，執(zhí)行時間比PMIA算法更少。

2.1　k-核

定義4集合Vk?V的任一節(jié)點v的度數(shù)不少于k，由Vk所推導出的最大誘導子圖Gk(Vk,Ek)稱為k-核。

k-核概念由Seidman[11]于1983年提出，可用來描述度分布所不能描述的網(wǎng)絡特征，揭示源于系統(tǒng)特殊結構的結構性質和層次性質。雖然節(jié)點度在影響最大化問題中被研究者廣泛關注，但是度較大的節(jié)點可能較為分散，而k-核使得度較大的節(jié)點聚集起來，網(wǎng)絡分布越集中，就越能受到彼此影響，從而產(chǎn)生更大的網(wǎng)絡影響力。因此本文采用k-核來優(yōu)化現(xiàn)有影響最大化算法。

2.2　k-核過濾算法

本文提出的k-核過濾算法不是一個獨立的影響最大化算法，而是通過與現(xiàn)有影響最大化算法相結合來擴大現(xiàn)有算法的影響范圍，并縮短其執(zhí)行時間。k-核過濾算法的基本思想是通過預訓練k，找到對現(xiàn)有算法具有最佳優(yōu)化效果、并且與選擇種子節(jié)點數(shù)t無關的固定k值，在給定需要選擇的節(jié)點數(shù)t時，通過計算圖的k-核過濾不屬于k-核子圖的節(jié)點和邊，在k-核子圖上執(zhí)行現(xiàn)有影響最大化算法，從而達到減少計算量的目的。

k-核過濾算法涉及兩個步驟：1)通過預先訓練找到能產(chǎn)生優(yōu)化效果最好的參數(shù)k，如算法1所示；2)計算網(wǎng)絡的k-核，并應用在現(xiàn)有算法中，如算法2所示。

算法1預訓練k。

輸入有向圖G=(V,E)， 迭代次數(shù)iter；

輸出最佳優(yōu)化效果k。

1)

optk=0,k=0,t=rand(0, 10),σopt=0;

2)

whilek

3)

computeGk， thek-core subgraph ofG;

4)

imply existing IM algorithm onGk;

5)

ifσk>σopt

6)

optk=k;σopt=σk;

7)

k++;

8)

returnoptk;

算法2k-核優(yōu)化現(xiàn)有算法。

輸入有向圖G=(V,E)， 最佳優(yōu)化效果k，種子節(jié)點數(shù)t;

輸出種子集合S。

1)

computeGk， thek-core subgraph ofG;

2)

S=existing IM algorithm onGk;

3)

returnS;

算法1的預訓練過程需要提前完成以選出最佳優(yōu)化效果k，由本文實驗可知，在選取不同的種子個數(shù)t時，取得最佳優(yōu)化效果的k是固定值。接著采用算法2計算G的種子集合S，此時的執(zhí)行時間會減少很多，影響范圍效果也會更好。本文利用Batagelj等[12]提出的算法計算k-核子圖Gk，通過迭代刪除度小于k的所有頂點和與之相連的邊，剩下的子圖就是k-核，時間復雜度為O(m)。針對不同的現(xiàn)有算法，k-核過濾算法有不同的結合方式，算法的時間復雜度取決于現(xiàn)有算法的時間復雜度，但通常比結合前的原算法效率更高。假設現(xiàn)有算法的時間復雜度為f(n,m)，那么k-核過濾算法的時間復雜度為max{O(m),f(nk,mk)}，其中nk和mk表示k-核子圖的節(jié)點數(shù)和邊數(shù)。通常f(n,m)都是大于O(m)的復雜度，通過k-核過濾之后算法時間復雜度不超過O(m)和f(nk,mk)的最大值，但一定小于f(n,m)。算法2也可以脫離算法1直接執(zhí)行，可以任意選擇k，對現(xiàn)有算法的影響范圍和執(zhí)行時間都會有改進，只是沒有預訓練k的優(yōu)化效果好。

2.3　k-核優(yōu)化現(xiàn)有算法

現(xiàn)有影響最大化算法中，PMIA算法和IRIE算法傳播影響效果較好，其中PMIA的內(nèi)存耗費較大，IRIE算法執(zhí)行時間較長。本文將k-核過濾算法分別與CCA[6]、PMIA算法[7]、OutDegree算法[1]和Random算法相結合，得到KCoreCCA算法、KCorePMIA算法、KCoreOutDegree算法和KCoreRandom算法，以擴大原算法的影響范圍，縮短其執(zhí)行時間。IRIE算法[8]和PageRank算法[13]是基于節(jié)點排名的算法，節(jié)點排名依賴于整個網(wǎng)絡所有節(jié)點的收斂，k-核過濾算法原理是先剪枝不重要的節(jié)點，因此無法應用在這兩個算法中。

2.3.1KCoreCCA

核覆蓋算法(CCA)是基于覆蓋距離選擇核數(shù)最大的t個節(jié)點作為種子節(jié)點。核數(shù)k表示節(jié)點屬于k-核，而不屬于(k+1)-核。CCA和k-核過濾算法都是基于k-核的概念提出的，較小核數(shù)的節(jié)點對CCA毫無貢獻，剪枝核數(shù)較小的節(jié)點雖然對CCA的影響范圍沒有改變，但是可以大大縮短CCA的執(zhí)行時間。

算法3KCoreCCA。

輸入有向圖G(V,E)，種子節(jié)點數(shù)t， 覆蓋距離d；

輸出種子集合S。

1)

initializeS=?;

2)

computeGk(Vk,Ek)， thek-core subgraph ofG;

3)

computeCores(Gk);

4)

foreach vertexv∈Vkdo

5)

COv=false;

6)

fori=1 totdo

7)

8)

9)

S=S∪{u};

10)

foreach vertexvin {v|du,v≤d,v∈Vk} do

11)

COv=true;

12)

returnS;

其中:Cv為節(jié)點的核數(shù)，COv表示節(jié)點覆蓋屬性，du,v表示節(jié)點u和v之間的距離。算法3是將k-核過濾算法應用于CCA，CCA的時間復雜度是O(tm)[6]。KCoreCCA先計算出k-核子圖(第2)行)，時間復雜度是O(m)；第3)～12)行遵循CCA的基本思路，但只針對k-核計算，而不是整個網(wǎng)絡，時間復雜度是O(tmk)。所以 KCoreCCA的時間復雜度是max{O(m),O(tmk)}，因為剪枝了很多節(jié)點，減少了計算量。

KCoreCCA是以核數(shù)考量選擇種子節(jié)點，而以出度考量選取種子節(jié)點的算法，稱為OutDegree算法，類似優(yōu)化CCA的方式，應用k-核過濾算法于OutDegree算法，得到KCoreOutDegree算法，OutDegree算法時間復雜度為O(n+m),KCoreOutDegree算法時間復雜度為max{O(m),O(nk,mk)}。k-核過濾算法應用于隨機選取種子節(jié)點的Random算法，得到KCoreRandom算法，Random算法時間復雜度為O(t),KCoreRandom算法時間復雜度為max{O(m),O(t)}=O(m)。

2.3.2KCorePMIA算法

PMIA算法先計算每個節(jié)點?v∈V的本地樹結構PMIIA和PMIOA，基于本地樹結構PMIIA計算當前種子集合S對每個節(jié)點u的影響ap(u,S,PMIIA(v,θ))，并根據(jù)影響線性(Influence Linearity)性質計算影響系數(shù)α(v,u)，然后根據(jù)本地樹結構結合子模性選出影響最大的t個節(jié)點。PMIA算法需計算每個節(jié)點的本地樹結構，雖然加快了影響傳播的計算和更新，但保存每個節(jié)點的本地樹結構需要耗費大量內(nèi)存，計算全部節(jié)點本地樹結構效率也較低。本文采用k-核過濾算法篩選出可能是最具影響力的節(jié)點，只需計算這些節(jié)點的本地樹結構，從而減少了大量計算。

算法4KCorePMIA算法。

輸入有向圖G(V,E)， 種子節(jié)點數(shù)t，路徑傳播閾值θ;

輸出種子集合S。

1)

setS=?;

2)

setIncInf(v)=0 for each nodev∈V

3)

computeGk(Vk,Ek)， thek-core subgraph ofG;

4)

foreach vertexv∈Gkdo

5)

compute PMIIA(v,θ,S);

6)

set ap(u,S,PMIIA(v,θ,S))=0,?u∈PMIIA(v,θ,S);

7)

computeα(v,u),?u∈PMIIA(v,θ,S)

8)

foreach vertexu∈PMIIA(v,θ,S) do

9)

IncInf(u)+=

α(v,u)*(1-ap(u,S,PMIIA(v,θ,S)));

10)

fori=1 totdo

11)

12)

compute PMIOA(u,θ,S);

13)

foreachv∈PMIOA(u,θ,S)∩Vkdo

14)

forw∈PMIIA(v,θ,S)Sdo

15)

IncInf(w)-=

α(v,w)*(1-ap(w,S,PMIIA(v,θ,S)));

16)

S=S∪{u};

17)

forv∈PMIOA(u,θ,S{u}){u}∩Vkdo

18)

compute PMIIA(v,θ,S);

19)

computeap(w,S,PMIIA(v,θ,S)),?w∈PMIIA(v,θ,S)

20)

computeα(v,w),?w∈PMIIA(v,θ,S)

21)

forw∈PMIIA(v,θ,S)Sdo

22)

IncInf(w)-=

α(v,w)*(1-ap(w,S,PMIIA(v,θ,S)));

23)

returnS;

PMIA算法的時間復雜度是O(ntiθ+tnoθniθlogn)，其中niθ和noθ分別是所有節(jié)點的PMIIA本地樹結構和PMIOA本地樹結構的最大節(jié)點數(shù)，tiθ是計算所有節(jié)點的PMIIA本地樹結構的最長時間[7]，由于每個節(jié)點都需要計算PMIIA和PMIOA子樹結構，PMIA算法的時間復雜度一定大于O(m)。而KCorePMIA算法先計算k-核子圖Gk(第3)行)，時間復雜度是O(m)，過濾掉部分節(jié)點后，只需在Gk上再執(zhí)行PMIA算法(第4)～23)行)，時間復雜度是O(nktiθk+tnoθkniθklognk)，因此KCorePMIA算法的時間復雜度為max{O(m),O(nktiθk+tnoθkniθklognk)}。當k較大時，nk遠小于n，KCorePMIA算法的時間復雜度不大于O(m)。

2.4　GIMS算法

李國良等[10]提出的BoundBasedIMMS(BoundBased Influence Maximization in Multiple Social networks)算法可以有效解決存在實體對應關系的多網(wǎng)絡影響最大化問題，本文對該算法進行擴展，以設計一種可以有效解決單個社交網(wǎng)絡上的影響最大化問題的算法GIMS。GIMS擴展了基于樹的算法模型[7]，結合獨立級聯(lián)模型的單調性和子模性，降低了時間復雜度，同時也保證了影響范圍效果。

路徑Pu,v=(n1=u,n2,…,nm=v)表示經(jīng)由節(jié)點u到節(jié)點v的一條路徑。在獨立級聯(lián)模型下，節(jié)點u沿路徑P激活節(jié)點v的概率為：

節(jié)點u可以通過多條路徑影響到節(jié)點v，為減少計算量，采用最大影響路徑MPP(u,v)來近似節(jié)點u對節(jié)點v的影響概率：

pp(u,v)≈pp(MPP(u,v))=pp(arg max(pp(Pu,v)))

通過計算所有節(jié)點到節(jié)點u的影響概率，可以構建最大逆向傳播樹ITree(u)，考慮到當pp(u,v)小于某一個閾值θ時，節(jié)點v被u激活的概率較小，則忽略此節(jié)點。同理，計算節(jié)點u到所有其他節(jié)點的影響概率，可以構建最大傳播樹Otree(u)。

給定激活的種子集合S，假設S中的每個節(jié)點獨立地影響其他未激活的節(jié)點，并且只在已構建的傳播樹中傳播影響，則S對未激活節(jié)點v的影響概率為：

在種子集合S中加入一個新激活的節(jié)點u后，種子集合對節(jié)點v的影響增益gain(u|S,v)為：

gain(u|S,v)=pp(S∪{u},v)-pp(S,v)=

假設每個節(jié)點都是獨立影響其他節(jié)點，那么種子集合S中新增加一個激活節(jié)點u后總的影響增益gain(u|S)為：

根據(jù)影響最大化問題的子模性，每次選取影響增益gain(u|S)最大的節(jié)點加入種子集合S中，直到選取t個節(jié)點。

算法5GIMS算法。

輸入有向圖G(V,E)， 種子節(jié)點數(shù)t，路徑傳播閾值θ;

輸出種子集合S。

1)

precomputeITree(v) andOTree(v) withθ， for ?v∈V;

2)

initialize big heapHof Node {v.id,v.spread,v.status}, for ?v∈V;

3)

setS=?;

4)

initializepp(S,v)=0, for ?v∈V;

5)

fori=1 totdo

6)

Nodetnode=H.top();

7)

while(tnode.status!=i) do

8)

computegain(tnode.id|S);

9)

tnode.spread=gain(tnode.id|S);

10)

tnode.status=i;

11)

H.sort();

12)

tnode=H.top();

13)

tnode=H.pop();

14)

S=S∪{tnode.id};

15)

updatepp(S,v), for ?v∈V;

16)

H.sort();

17)

returnS;

算法5通過構造樹模型近似計算傳播概率(第1)行)，時間復雜度是O(ntθ)，其中tθ是所有ITree(v)和OTree(v)的最大頂點數(shù)。然后依據(jù)獨立影響假設簡化了影響增益計算，構造大根堆避免了很多影響力小的節(jié)點的計算(第6)～16)行)。每次計算gain(tnode.id|S)的時間復雜度是O(tθ)，調整堆H的時間復雜度是O(logn),每次迭代更新常量次節(jié)點status即可選出最優(yōu)tnode，所以第6)～16)行的時間復雜度是O(tθ+logn)。因此GIMS的時間復雜度為O(ntθ+t(tθ+logn))。在此基礎上，本文應用k-核優(yōu)化GIMS算法，稱為KCoreGIMS算法。KCoreGIMS算法先通過計算k-核剪枝部分影響力小的節(jié)點，時間復雜度為O(m)，在計算算法5的第1)行和第2)行時無需計算全部網(wǎng)絡節(jié)點，而只需在k-核子圖上執(zhí)行GIMS算法從而減少計算量，時間復雜度為O(nktθ+t(tθ+lognk))。因此KCoreGIMS的算法時間復雜度為max{O(m),O(nktθ+t(tθ+lognk))}。

2.5　算法復雜度比較分析

經(jīng)過2.4節(jié)對各算法分析，總結各算法和其k-核過濾算法的時間復雜度如表1?？梢钥吹?，對于影響范圍效果好的算法GIMS、PMIA、CCA、OutDegree，計算k-核的時間復雜度是O(m)，但執(zhí)行現(xiàn)有影響最大化算法時由于只需要考慮k-核子圖的節(jié)點和邊，使得原算法的復雜度有所降低。對于效果較差的Random算法，由于是隨機選擇種子節(jié)點，使用k-核過濾時計算k-核使時間復雜度有所增加。因此，對于一般影響最大化算法而言，k-核過濾算法使得原算法的時間復雜度有所降低。

表1　不同影響最大化算法及其k-核過濾算法的時間復雜度比較Tab. 1　Time complexity comparison of different IM algorithms and their k-core filtered versions

3　實驗與分析

3.1　數(shù)據(jù)集

本文實驗在三個真實數(shù)據(jù)集上進行，分別是ArXiv(https://arxiv.org/)物理領域作者合作關系網(wǎng)絡NetHEPT(collaboration Network of High Energy Physics Theory from arXiv.org)、社交網(wǎng)絡Slashdot和商品團購網(wǎng)絡Amazon(http://snap.stanford.edu/data/index.html)。這三個數(shù)據(jù)集的統(tǒng)計特性如表2所示。

表2　實驗中的數(shù)據(jù)集Tab. 2　Experimental datasets

3.2　實驗設計

本文實驗比較了GIMS算法、PMIA算法、IRIE算法、CCA、OutDegree算法、PageRank算法和Random算法，以及

它們的k-核過濾算法。其中IRIE算法和PageRank由于依賴全局節(jié)點排名不適合k-核過濾；CCA的覆蓋距離d設置為2；GIMS算法、PMIA算法傳播概率閾值θ設置為1/320；社交網(wǎng)絡中節(jié)點u到節(jié)點v的傳播概率初始化為1/InDeg(v)，其中InDeg(v)表示節(jié)點v的入度。由于模型的隨機性，在計算選擇的t個節(jié)點的影響范圍時采用蒙特卡羅重復模擬10 000次，取平均值。

所有程序代碼都是基于C++語言編程，計算機配置為：centos 6.6， Intel Xeon CPU E5- 2640 v3 2.60 GHz，8 GB內(nèi)存。

為了評估k-核過濾算法對現(xiàn)有算法的優(yōu)化效果，本文定義兩個評估指標，影響范圍優(yōu)化百分比influ_opt和執(zhí)行時間優(yōu)化百分比time_opt。假設A算法的k-核過濾算法是KCoreA，當選擇t個種子節(jié)點時，算法KCoreA的影響范圍和執(zhí)行時間分別是kcore_influ和kcore_time，算法A的影響范圍和執(zhí)行時間分別是influ和time，那么：

influ_opt=(kcore_influ-influ)/influ

time_opt=(time-kcore_time)/time

當種子節(jié)點數(shù)1≤t≤50時，定義平均影響范圍優(yōu)化百分比avg_influ_opt和平均執(zhí)行時間優(yōu)化百分比avg_time_opt分別為所有t值下influ_opt和time_opt的平均值。

3.3　實驗結果與分析

圖1(a)、(b)分別是NetHEPT上各個算法及其k-核過濾算法的傳播范圍和執(zhí)行時間。通過算法1的預訓練k發(fā)現(xiàn)選取不同種子個數(shù)時取得最佳優(yōu)化效果的k是固定值：KCoreGIMS最佳優(yōu)化效果k為3或4，KCorePMIA的最優(yōu)k為1或2，KCoreCCA的最優(yōu)k為8，KCoreOutDegree的最優(yōu)k為3，KCoreRandom的最優(yōu)k為4或5。從圖1可以看到，本文提出的GIMS算法及其優(yōu)化算法KCoreGIMS比現(xiàn)有算法中效果較好的PMIA算法和IRIE算法選出的節(jié)點傳播效果更好，執(zhí)行時間保持在毫秒級別，比IRIE算法更有效率。k-核過濾對于不同算法的優(yōu)化效果不同。對算法本身效果較優(yōu)的GIMS算法、PMIA算法來說，k-核優(yōu)化效果比原算法的影響范圍擴大了1%左右；對OutDegree算法和Random算法影響范圍擴大了10%以上；對CCA傳播范圍沒有影響，但是執(zhí)行時間縮短了27%。也即，對所有算法影響范圍都擴大了，執(zhí)行時間都縮短了。

圖1　NetHEPT數(shù)據(jù)集上的傳播范圍和執(zhí)行時間Fig. 1　Influence range and execution time on NetHEPT dataset

圖2(a)、(b)分別是Slashdot數(shù)據(jù)集上各個算法及其k-核過濾算法的傳播范圍和執(zhí)行時間。通過算法1的預訓練k發(fā)現(xiàn)選取不同種子個數(shù)時取得最佳優(yōu)化效果的k是固定值：KCoreGIMS的最優(yōu)k為22或44，KCorePMIA的最優(yōu)k為5或6，KCoreCCA的最優(yōu)k為50，KCoreOutDegree的最優(yōu)k為40或50，KCoreRandom的最優(yōu)k為42或44。從圖2可以看到，本文提出的GIMS算法及其優(yōu)化算法KCoreGIMS仍然是傳播范圍最好的算法，比PMIA算法和IRIE算法高出2 000多節(jié)點，執(zhí)行時間遠少于IRIE算法和PMIA算法。k-核過濾算法對GIMS算法和PMIA算法影響范圍擴大了2%以上，執(zhí)行時間縮短了2%以上，對CCA和OutDegree算法執(zhí)行時間縮短了27%左右。

圖3(a)、(b)是Amazon數(shù)據(jù)集上各算法及其k-核過濾算法的影響范圍和執(zhí)行時間。通過算法1的預訓練k發(fā)現(xiàn)選取

不同種子個數(shù)時取得最佳優(yōu)化效果的k是固定值：GIMS的最優(yōu)k為11，KCorePMIA的最優(yōu)k為10，KCoreCCA的最優(yōu)k為19，KCoreOutDegree的最優(yōu)k為5或7，KCoreRandom的最優(yōu)k為3或6。從圖3可以看到，本文提出的GIMS及其優(yōu)化算法KCoreGIMS仍是影響范圍最大的算法，執(zhí)行時間也遠低于IRIE算法。K-核過濾算法對GIMS算法和PMIA算法影響范圍擴大了1%以上，對OutDegree算法影響范圍擴大了21%以上，對CCA的執(zhí)行時間縮短了28%左右。

圖2　Slashdot數(shù)據(jù)集上的傳播范圍和執(zhí)行時間Fig. 2　Influence range and execution time on Slashdot dataset

圖3　Amazon數(shù)據(jù)集上的傳播范圍和執(zhí)行時間Fig. 3　Influence range and execution time on Amazon dataset

從圖性質來看，Amazon是稀疏的大網(wǎng)絡，Slashdot和NetHEPT是稠密的小網(wǎng)絡，但GIMS和KCoreGIMS保持了更大的影響范圍和有競爭力的執(zhí)行時間，k-核過濾算法對各算法的影響范圍和執(zhí)行效率都有不錯的優(yōu)化效果。這說明了GIMS算法和k-核過濾算法的魯棒性。為了更好地展示k-核過濾算法對各算法的影響范圍和執(zhí)行效率的優(yōu)化效果，表3給出了各算法的平均影響范圍和執(zhí)行時間優(yōu)化百分比，也就是定義在3.2節(jié)的avg_influ_opt和avg_time_opt。

從表3可以看到，k-核過濾算法對GIMS算法和PMIA算法的優(yōu)化效果較弱，但是也有提高；對CCA的影響范圍沒有擴大，但是大大縮短了CCA的執(zhí)行時間；對OutDegree算法和Random算法擴大了影響范圍，縮短了執(zhí)行時間。

通過對圖1～3和表3的綜合分析可以得出以下結論：1)本文提出的GIMS算法及其k-核過濾算法影響范圍比現(xiàn)有的算法更好，執(zhí)行時間也更有競爭力；2)k-核過濾算法對現(xiàn)有大多數(shù)算法都可以擴大影響范圍，減少執(zhí)行時間；3)k-核過濾算法在保證不降低影響范圍的情況下，能大大減少CCA的執(zhí)行時間。

表3　k-核過濾影響范圍和執(zhí)行時間百分比對比　%Tab. 3　Comparison of avg_influ_opt (AIO) and avg_time_opt (ATO)　%

4　結語

針對近幾年研究熱點社交網(wǎng)絡影響最大化問題，提出了一種影響范圍和執(zhí)行時間更優(yōu)的GIMS算法，并通過k-核計算剪枝影響范圍小的節(jié)點，提出了一種可以擴大現(xiàn)有算法影響范圍和減少它們執(zhí)行時間的k-核過濾算法。實驗表明：GIMS算法影響范圍超過現(xiàn)有算法，執(zhí)行時間也很有競爭力；k-核過濾算法能擴大現(xiàn)有算法的影響范圍并減少它們的執(zhí)行時間，對CCA尤其有效；并且，首次發(fā)現(xiàn)同一算法在同一數(shù)據(jù)集上預訓練k選取不同種子個數(shù)時取得最佳優(yōu)化效果的k是固定值。下一步的研究方向可以考慮使用其他方式來剪枝影響力小的節(jié)點，還可以考慮優(yōu)化帶有成本或地理位置限制的影響最大化問題[14]。

參考文獻:

[1]WASSERMAN S, FAUST K. Social Network Analysis: Methods and Applications [M]. New York: Cambridge University Press, 1994: 148-161.

[2]DOMINGOS P, RICHARDSON M. Mining the network value of customers [C]// KDD 2001: Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2001: 57-66.

[3]KEMPE D, KLEINBERG J, TARDOS é. Maximizing the spread of influence through a social network [C]// KDD 2003: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2003: 137-146.

[4]LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks [C]// KDD 2007: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2007: 420-429.

[5]CHEN W, WANG Y, YANG S. Efficient influence maximization in social networks [C]// KDD 2009: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2009: 199-208.

[6]曹玖新,董丹,徐順,等.一種基于k-核的社會網(wǎng)絡影響最大化算法[J].計算機學報,2015,38(2):238-248. (CAO J X, DONG D, XU S, et al. Ak-core based algorithm for influence maximization in social networks [J]. Chinese Journal of Computers, 2015, 38(2): 238-248.)

[7]WANG C, CHEN W, WANG Y. Scalable influence maximization for independent cascade model in large-scale social networks [J]. Data Mining & Knowledge Discovery, 2012, 25(3): 545-576.

[8]JUNG K, HEO W, CHEN W. IRIE: scalable and robust influence maximization in social networks [C]// ICDM 2012: Proceedings of the 2012 IEEE 12th International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2012: 918-923.

[9]夏濤,陳云芳,張偉,等.社會網(wǎng)絡中的影響力綜述[J].計算機應用,2014,34(4):980-985. (XIA T, CHEN Y F, ZHANG W, et al. Survey of influence in social networks [J]. Journal of Computer Applications, 2014, 34(4): 980-985.)

[10]李國良,楚婭萍,馮建華,等.多社交網(wǎng)絡的影響力最大化分析[J].計算機學報,2016,39(4):643-656. (LI G L, CHU Y P, FENG J H, et al. Influence maximization on multiple social networks [J]. Chinese Journal of Computers, 2016, 39(4): 643-656.)

[11]SEIDMAN S B. Network structure and minimum degree [J]. Social Networks, 1983, 5(3): 269-287.

[13]BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine [J]. Computer Networks and ISDN Systems, 1998, 30(1/2/3/4/5/6/7): 107-117.

[14]劉院英,郭景峰,魏立東,等.成本控制下的快速影響最大化算法[J].計算機應用,2017,37(2):367-372. (LIU Y Y, GUO J F, WEI L D, et al. Fast influence maximization algorithm in social network under budget control [J]. Journal of Computer Applications, 2017, 37(2): 367-372.)