李閱志，祝園園，鐘　鳴

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

0　引言

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

影響最大化問題最早由Domingos等[2]定義為如何尋找t個初始節(jié)點，使得信息的最終傳播范圍最廣。 Kempe等[3]將影響最大化定義為一個離散優(yōu)化問題，證實了這個問題在獨立級聯模型下是NP難問題，提出了對后續(xù)研究影響極大的兩種傳播模型：獨立級聯(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算法被認為是現有影響力最大化算法中影響范圍和時間效率排名靠前的算法。這些算法基本都使用了子模性質，雖然時間效率有了很大的提升，但是影響范圍效果仍然比不上Greedy算法[3]。

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

1　傳播模型和問題定義

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

1.1　獨立級聯模型

獨立級聯模型是一個概率模型。對于網絡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é)點，根據成功概率p(u,v)試圖去激活它們的鄰居節(jié)點，并將在這一步中被激活的節(jié)點加入到St形成St+1；重復這一過程，直至不再有新的節(jié)點被激活。整個過程中u只嘗試激活v一次，激活成功則v由未激活變?yōu)榧せ顮顟B(tài)，激活失敗則不再嘗試激活。

1.2　問題定義

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

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

s.t.|S*|=t

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

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

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

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

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

2.1　k-核

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

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

2.2　k-核過濾算法

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

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

算法1預訓練k。

輸入有向圖G=(V,E)， 迭代次數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)化現有算法。

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

輸出種子集合S。

1)

computeGk， thek-core subgraph ofG;

2)

S=existing IM algorithm onGk;

3)

returnS;

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

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

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

2.3.1KCoreCCA

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

算法3KCoreCCA。

輸入有向圖G(V,E)，種子節(jié)點數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é)點的核數，COv表示節(jié)點覆蓋屬性，du,v表示節(jié)點u和v之間的距離。算法3是將k-核過濾算法應用于CCA，CCA的時間復雜度是O(tm)[6]。KCoreCCA先計算出k-核子圖(第2)行)，時間復雜度是O(m)；第3)～12)行遵循CCA的基本思路，但只針對k-核計算，而不是整個網絡，時間復雜度是O(tmk)。所以 KCoreCCA的時間復雜度是max{O(m),O(tmk)}，因為剪枝了很多節(jié)點，減少了計算量。

KCoreCCA是以核數考量選擇種子節(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,θ))，并根據影響線性(Influence Linearity)性質計算影響系數α(v,u)，然后根據本地樹結構結合子模性選出影響最大的t個節(jié)點。PMIA算法需計算每個節(jié)點的本地樹結構，雖然加快了影響傳播的計算和更新，但保存每個節(jié)點的本地樹結構需要耗費大量內存，計算全部節(jié)點本地樹結構效率也較低。本文采用k-核過濾算法篩選出可能是最具影響力的節(jié)點，只需計算這些節(jié)點的本地樹結構，從而減少了大量計算。

算法4KCorePMIA算法。

輸入有向圖G(V,E)， 種子節(jié)點數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é)點數，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)算法可以有效解決存在實體對應關系的多網絡影響最大化問題，本文對該算法進行擴展，以設計一種可以有效解決單個社交網絡上的影響最大化問題的算法GIMS。GIMS擴展了基于樹的算法模型[7]，結合獨立級聯模型的單調性和子模性，降低了時間復雜度，同時也保證了影響范圍效果。

路徑Pu,v=(n1=u,n2,…,nm=v)表示經由節(jié)點u到節(jié)點v的一條路徑。在獨立級聯模型下，節(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)為：

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

算法5GIMS算法。

輸入有向圖G(V,E)， 種子節(jié)點數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)的最大頂點數。然后依據獨立影響假設簡化了影響增益計算，構造大根堆避免了很多影響力小的節(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)行時無需計算全部網絡節(jié)點，而只需在k-核子圖上執(zhí)行GIMS算法從而減少計算量，時間復雜度為O(nktθ+t(tθ+lognk))。因此KCoreGIMS的算法時間復雜度為max{O(m),O(nktθ+t(tθ+lognk))}。

2.5　算法復雜度比較分析

經過2.4節(jié)對各算法分析，總結各算法和其k-核過濾算法的時間復雜度如表1?？梢钥吹?，對于影響范圍效果好的算法GIMS、PMIA、CCA、OutDegree，計算k-核的時間復雜度是O(m)，但執(zhí)行現有影響最大化算法時由于只需要考慮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　數據集

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

表2　實驗中的數據集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；社交網絡中節(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內存。

為了評估k-核過濾算法對現有算法的優(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é)點數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ā)現選取不同種子個數時取得最佳優(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比現有算法中效果較好的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數據集上的傳播范圍和執(zhí)行時間Fig. 1　Influence range and execution time on NetHEPT dataset

圖2(a)、(b)分別是Slashdot數據集上各個算法及其k-核過濾算法的傳播范圍和執(zhí)行時間。通過算法1的預訓練k發(fā)現選取不同種子個數時取得最佳優(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數據集上各算法及其k-核過濾算法的影響范圍和執(zhí)行時間。通過算法1的預訓練k發(fā)現選取

不同種子個數時取得最佳優(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數據集上的傳播范圍和執(zhí)行時間Fig. 2　Influence range and execution time on Slashdot dataset

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

從圖性質來看，Amazon是稀疏的大網絡，Slashdot和NetHEPT是稠密的小網絡，但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-核過濾算法影響范圍比現有的算法更好，執(zhí)行時間也更有競爭力；2)k-核過濾算法對現有大多數算法都可以擴大影響范圍，減少執(zhí)行時間；3)k-核過濾算法在保證不降低影響范圍的情況下，能大大減少CCA的執(zhí)行時間。

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

4　結語

針對近幾年研究熱點社交網絡影響最大化問題，提出了一種影響范圍和執(zhí)行時間更優(yōu)的GIMS算法，并通過k-核計算剪枝影響范圍小的節(jié)點，提出了一種可以擴大現有算法影響范圍和減少它們執(zhí)行時間的k-核過濾算法。實驗表明：GIMS算法影響范圍超過現有算法，執(zhí)行時間也很有競爭力；k-核過濾算法能擴大現有算法的影響范圍并減少它們的執(zhí)行時間，對CCA尤其有效；并且，首次發(fā)現同一算法在同一數據集上預訓練k選取不同種子個數時取得最佳優(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-核的社會網絡影響最大化算法[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]夏濤,陳云芳,張偉,等.社會網絡中的影響力綜述[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]李國良,楚婭萍,馮建華,等.多社交網絡的影響力最大化分析[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.)