徐 浩，潘 理

（1.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海 200240；2.上海市信息安全綜合管理技術(shù)研究重點(diǎn)實(shí)驗(yàn)室，上海 200240）

0 引 言

隨著在線社交網(wǎng)絡(luò)分析在推薦系統(tǒng)、市場(chǎng)營(yíng)銷、信息檢索等依據(jù)影響力對(duì)用戶行為進(jìn)行預(yù)測(cè)的領(lǐng)域的廣泛應(yīng)用，影響力分析問題在學(xué)術(shù)界和工業(yè)界引起了越來越多重視?；谏缃痪W(wǎng)絡(luò)的市場(chǎng)營(yíng)銷，如何準(zhǔn)確找到最具影響力的個(gè)體集合、獲取最大的影響范圍，是極其關(guān)鍵的問題。對(duì)此，文獻(xiàn)[1]給出了準(zhǔn)確化定義，將影響力最大化問題轉(zhuǎn)化為如何選擇K個(gè)初始節(jié)點(diǎn)，通過激活這K個(gè)初始節(jié)點(diǎn)，在給定信息傳播模型下，使網(wǎng)絡(luò)中最終被激活的用戶節(jié)點(diǎn)數(shù)最多。已有的相關(guān)研究主要從個(gè)體的角度分析問題[2-4]，Kempe等人[2]首先使用貪婪爬山算法進(jìn)行影響力分析，證明了這一問題是NP難問題，用貪婪算法求解可以達(dá)到(1-1/e)的精度。但是，貪婪算法的時(shí)間復(fù)雜度太高。后來研究人員主要解決的問題是提高算法的運(yùn)行效率[5,6]，但是這些算法都是基于網(wǎng)絡(luò)全局進(jìn)行算法模型設(shè)計(jì)。當(dāng)面對(duì)大規(guī)模社交網(wǎng)絡(luò)時(shí)，過高的時(shí)間復(fù)雜度依舊是一個(gè)棘手的難題。因此，本文基于NVPA[7]社區(qū)劃分算法，提出了一種從局部角度解決影響力最大化問題的算法NVPA-IM。在傳統(tǒng)的社區(qū)劃分算法中，相似度衡量指標(biāo)一般都是節(jié)點(diǎn)的一跳鄰居節(jié)點(diǎn)數(shù)的重合度，而忽略了多跳鄰居節(jié)點(diǎn)集對(duì)相似度的影響。相對(duì)于傳統(tǒng)算法，NVPA算法在計(jì)算節(jié)點(diǎn)之間的相似度時(shí)，考慮了節(jié)點(diǎn)的多跳鄰居節(jié)點(diǎn)對(duì)相似度的貢獻(xiàn)，顯著提高了社區(qū)劃分的精度。同時(shí)，傳統(tǒng)的社區(qū)劃分算法一般將模塊度指標(biāo)[8]作為衡量社區(qū)劃分好壞的重要指標(biāo)，以模塊度最優(yōu)作為社區(qū)劃分過程迭代終止的判斷條件。所以，最終網(wǎng)絡(luò)中社區(qū)的個(gè)數(shù)并不能確定。相對(duì)于傳統(tǒng)社區(qū)劃分算法，NVPA算法在保證模塊度指標(biāo)優(yōu)異的情況下，可以將網(wǎng)絡(luò)指定劃分成K個(gè)社區(qū)。經(jīng)實(shí)驗(yàn)驗(yàn)證，該算法能夠精確挖掘網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。

1 NVPA-IM算法

在社交網(wǎng)絡(luò)研究中，一般將社交網(wǎng)絡(luò)抽象成一張有向（或無向）圖G=(V,E)。其中，用戶抽象成節(jié)點(diǎn)，V={v1,v2,…,vn}為節(jié)點(diǎn)集合。用戶之間的關(guān)系抽象成邊，E={(vi,vj)|vi,vj∈V}為邊的集合。

定義1 影響力最大化。給定一個(gè)社交網(wǎng)絡(luò)G=(V,E)和一個(gè)正整數(shù)K，要求從社交網(wǎng)絡(luò)中尋找K個(gè)初始活躍節(jié)點(diǎn)集合S(|S|=K,S?V)，S在社交網(wǎng)絡(luò)中按照某種信息傳播規(guī)律傳播影響，要求最終活躍的節(jié)點(diǎn)數(shù)目最多。用影響力函數(shù)σ(·)表示社交網(wǎng)絡(luò)中最終活躍節(jié)點(diǎn)的數(shù)目。影響力最大化問題即要求尋找合適的集合S使得σ(·)最大化，一般將集合S稱為種子集，形式化描述如下：

1.1 NVPA算法

NVPA算法是一種基于社交網(wǎng)絡(luò)結(jié)構(gòu)而進(jìn)行社區(qū)劃分的算法。如上介紹，為了更精確地挖掘網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，在計(jì)算節(jié)點(diǎn)之間相似度時(shí)，NVPA算法考慮了與節(jié)點(diǎn)距離為d(d＞1)的鄰居節(jié)點(diǎn)對(duì)結(jié)果的影響。該算法定義節(jié)點(diǎn)的m跳鄰居節(jié)點(diǎn)集如下：

式中d(u,v)是節(jié)點(diǎn)u到節(jié)點(diǎn)v的距離。同時(shí)，該算法定義鄰域向量Zi用于保存節(jié)點(diǎn)i的拓?fù)浣Y(jié)構(gòu)信息。Zi是歸一化向量，能夠有效表示節(jié)點(diǎn)在空間中所處的位置。在一個(gè)具有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)圖中，節(jié)點(diǎn)vi的鄰域向量定義為：

在n維歐式空間中，Z^i是一個(gè)單位向量，反映了節(jié)點(diǎn)和其鄰居節(jié)點(diǎn)之間的關(guān)系?；谝陨蟽蓚€(gè)定義，NVPA算法設(shè)計(jì)了一個(gè)鄰域向量傳播規(guī)則：

式（4）對(duì)節(jié)點(diǎn)的鄰域向量進(jìn)行初始化，{α1,α2,…,αn}是歐式空間 Rn的正交基；式（5）中 di表示節(jié)點(diǎn)的度。依據(jù)式（5）、式（6），循環(huán)更新節(jié)點(diǎn)的鄰域向量值m次，則每個(gè)節(jié)點(diǎn)的鄰域向量Zi都包含了節(jié)點(diǎn)的m跳及m跳以內(nèi)的鄰居節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息?；诠?jié)點(diǎn)的鄰域向量計(jì)算相鄰節(jié)點(diǎn)的cosine相似度即式（7），將相似度最大的兩個(gè)節(jié)點(diǎn)vi、vj組合成一個(gè)社區(qū)，用節(jié)點(diǎn)vi表示該新社區(qū)，同時(shí)將節(jié)點(diǎn)vj從網(wǎng)絡(luò)中刪除。最后，按照一定的降維規(guī)則將維度αj刪除。循環(huán)以上過程，直至網(wǎng)絡(luò)中只包含K個(gè)節(jié)點(diǎn)時(shí)，社區(qū)劃分結(jié)束，這K個(gè)節(jié)點(diǎn)即是獲取的K個(gè)社區(qū)。

1.2 種子節(jié)點(diǎn)選取

利用NVPA算法劃分后的網(wǎng)絡(luò)包含K個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)代表一個(gè)社區(qū)。從每個(gè)社區(qū)中挖掘出一個(gè)影響力最大的種子節(jié)點(diǎn)，即組成種子集S。通常，啟發(fā)式算法在選取種子節(jié)點(diǎn)時(shí)效率較高，如傳統(tǒng)的度中心算法。該算法認(rèn)為，社區(qū)中度最大的節(jié)點(diǎn)即一跳鄰居節(jié)點(diǎn)數(shù)最多的節(jié)點(diǎn)，在傳播過程中具有重要作用。由NVPA算法可知，節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中的重要性也受節(jié)點(diǎn)的m跳及m跳以內(nèi)鄰居節(jié)點(diǎn)數(shù)的影響。所以，本文設(shè)計(jì)了基于式（8）的種子節(jié)點(diǎn)選取算法NVPA-IM：

該算法基于NVPA算法的性質(zhì)，對(duì)度中心算法進(jìn)行擴(kuò)展。在NVPA社區(qū)劃分算法中，計(jì)算相鄰節(jié)點(diǎn)之間的相似度時(shí)考慮到了距節(jié)點(diǎn)距離小于等于m的所有鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)之間相似度的貢獻(xiàn)，即相對(duì)于傳統(tǒng)的相似度算法，NVPA算法在計(jì)算相鄰節(jié)點(diǎn)相似度時(shí)不僅僅只考慮一階鄰居節(jié)點(diǎn)數(shù)目。所以在選取社區(qū)中重要的節(jié)點(diǎn)時(shí)，本文將度中心算法的衡量指標(biāo)一跳鄰居節(jié)點(diǎn)數(shù)擴(kuò)展到m跳及m跳以內(nèi)的鄰居節(jié)點(diǎn)數(shù)，m的取值由社區(qū)劃分階段鄰域向量的傳播次數(shù)決定。在式（8）中，Ni(v)是節(jié)點(diǎn)v的i跳鄰居節(jié)點(diǎn)集合包含的節(jié)點(diǎn)數(shù)。Γm(v)值越大，說明以節(jié)點(diǎn)v為中心，到節(jié)點(diǎn)v距離為m及m以內(nèi)的節(jié)點(diǎn)集覆蓋的范圍越廣，節(jié)點(diǎn)v在影響力傳播方面的作用越大。在社區(qū)劃分階段，一般情況下設(shè)置m為2～4的整數(shù)。在本文實(shí)驗(yàn)階段，設(shè)置m的值為3。綜上所述，NVPA-IM算法的偽代碼如下：

輸入：網(wǎng)絡(luò)G=V∈E；鄰域向量傳播次數(shù)m；種子節(jié)點(diǎn)數(shù)K

輸出：包含K個(gè)節(jié)點(diǎn)的種子集S

//第一部分：社區(qū)劃分

2 for each viin V, do:

3 根據(jù)式（4）初始化節(jié)點(diǎn)vi的鄰域向量

4 for t=1 to m,

5 根據(jù)式（5）和式（6）更新網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)的鄰域向量

6 for each eijin E, do:

8 for l=1 to n-K

9 選擇相似度最大的兩個(gè)節(jié)點(diǎn)vi,vj，將它們組合成一個(gè)新社區(qū)，用vi表示該社區(qū)

//空間降維

13 刪除維度αj并且歸一化更新后的鄰域向量

//第二部分：種子節(jié)點(diǎn)選取

14 for each Ci

15 for each v in Ci

17 在社區(qū)Ci中選擇Γm(v)值最大的節(jié)點(diǎn)v

18 S=S∪v

19 return S

可見，NVPA-IM算法首先利用NVPA算法對(duì)社交網(wǎng)絡(luò)進(jìn)行社區(qū)劃分（lines1～lines13）。該階段中，網(wǎng)絡(luò)中每一個(gè)節(jié)點(diǎn)都代表一個(gè)社區(qū)。因此，line9中是將社區(qū)vj組合到社區(qū)vi中，且line10中的ni、nj分別表示社區(qū)vi、vj中用戶的個(gè)數(shù)。然后，該算法從每個(gè)社區(qū)中進(jìn)行種子節(jié)點(diǎn)選?。╨ines14～lines18），用社區(qū)C1,C2,…,Ck表示第一部分社區(qū)劃分的結(jié)果v1,v2,…,vk，并依據(jù)Γm(v)指標(biāo)挖掘種子節(jié)點(diǎn)集。

2 實(shí)驗(yàn)與結(jié)果分析

本文實(shí)驗(yàn)使用Mcauley[9]于2012年從Facebook上獲取的數(shù)據(jù)集和文獻(xiàn)[10]中提到的LRF基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集。LRF數(shù)據(jù)集是人工數(shù)據(jù)集。在生成該數(shù)據(jù)集的過程中，同時(shí)考慮了社區(qū)內(nèi)部的緊密連接特征和現(xiàn)實(shí)世界復(fù)雜網(wǎng)絡(luò)的真實(shí)特征。Facebook數(shù)據(jù)集包含4 039個(gè)節(jié)點(diǎn)和88 234條邊；LRF人工數(shù)據(jù)集包含1 000個(gè)節(jié)點(diǎn)和9 935條邊。本文實(shí)驗(yàn)的實(shí)驗(yàn)環(huán)境是Intel Corei7-6700 3.4G處理器，16 GB內(nèi)存。

為了便于對(duì)比分析，在實(shí)驗(yàn)階段主要用影響收益來評(píng)估算法的性能。影響收益是指在社交網(wǎng)絡(luò)中選取K個(gè)初始節(jié)點(diǎn)并激活，在影響傳播結(jié)束后，網(wǎng)絡(luò)中被激活的節(jié)點(diǎn)數(shù)w與網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)n的比值w/n。該值的取值范圍是0～1。算法的影響收益越大，說明該算法的種子節(jié)點(diǎn)集選取的越準(zhǔn)確。通過激活該種子節(jié)點(diǎn)集合獲取的信息，傳播范圍越廣。

本文實(shí)驗(yàn)內(nèi)容主要包括兩部分：（1）從影響收益角度驗(yàn)證NVPA社區(qū)劃分算法的性能；（2）通過與已有的種子挖掘算法對(duì)比，驗(yàn)證NVPA-IM算法的精度與效率。算法精度主要用影響收益衡量，而算法效率主要用實(shí)驗(yàn)運(yùn)行時(shí)間衡量。

首先，為了評(píng)估NVPA社區(qū)劃分算法在解決影響力最大化問題時(shí)的性能，本文將其和目前已有的幾種典型的社區(qū)劃分算法進(jìn)行對(duì)比，即基于模塊度最大化的貪心算法FN[11]、基于圖的半監(jiān)督學(xué)習(xí)算法標(biāo)簽傳播算法LPA[12]和基于相似度的聚合算法H-Clustering[13]。在實(shí)驗(yàn)結(jié)果分析階段，本文先利用以上4種社區(qū)劃分算法將網(wǎng)絡(luò)進(jìn)行社區(qū)劃分，然后依據(jù)社區(qū)規(guī)模大小選擇前K個(gè)社區(qū)，隨機(jī)從每個(gè)社區(qū)中選擇一個(gè)節(jié)點(diǎn)組成種子節(jié)點(diǎn)集，最后在獨(dú)立級(jí)聯(lián)傳播模型（IC）上對(duì)比分析種子節(jié)點(diǎn)集的影響收益。在該階段，種子節(jié)點(diǎn)數(shù)目K的取值范圍是1～15。同時(shí)，下文分別用NVPA-R、FN-R、H-Clustering-R、LPA-R表示以上4種種子節(jié)點(diǎn)選取算法。

在IC模型中，本文設(shè)置每條邊的傳播概率為0.05。在LRF數(shù)據(jù)集上，4種社區(qū)劃分算法的影響收益如圖1所示。

圖1 不同社區(qū)劃分算法在LRF數(shù)據(jù)集上的影響收益對(duì)比

如圖1所示，當(dāng)種子節(jié)點(diǎn)數(shù)目K屬于1～15時(shí)，F(xiàn)N-R、LPA-R、H-Clustering-R這3種算法的影響收益近似，而NVPA-R算法的影響收益要明顯優(yōu)于其余3種算法。在Facebook數(shù)據(jù)集上，4種社區(qū)劃分算法的影響收益如圖2所示。

圖2 不同社區(qū)劃分算法在Facebook數(shù)據(jù)集上的影響收益對(duì)比

如圖2所示，隨著K值的增加，F(xiàn)N-R、LPA-R、H-Clustering-R及NVPA-R這4種算法的影響收益都趨于穩(wěn)定，且前3種算法的影響收益要明顯小于NVPA-IM算法。由以上實(shí)驗(yàn)結(jié)果可知，對(duì)于從社區(qū)角度解決影響力最大化問題，本文選取的NVPA社區(qū)劃分算法的性能要明顯優(yōu)于已知的3種從不同角度進(jìn)行社區(qū)劃分的典型算法。

為了驗(yàn)證上文提出的NVPA-IM算法的性能，本文將其與從社區(qū)中選取度最大節(jié)點(diǎn)的度中心算法（NVPA-DEG）、從社區(qū)中隨機(jī)選取種子節(jié)點(diǎn)的算法（NVPA-R）以及從個(gè)體角度解決影響力最大化問題的貪婪算法（CELF++）進(jìn)行對(duì)比分析。因?yàn)槲墨I(xiàn)[2]中已經(jīng)證明貪婪算法能夠保證精度達(dá)到最優(yōu)解的(1-1/e)，而CELF++算法[5]是優(yōu)化后的貪婪算法。相對(duì)于傳統(tǒng)的貪婪算法，它將算法的運(yùn)行效率提高了35%～55%。所以，在貪婪算法方面，本文選擇CELF++算法，并將其影響收益作為算法精度對(duì)比分析的基準(zhǔn)。

在LRF數(shù)據(jù)集上，基于IC模型，4種算法的影響收益對(duì)比結(jié)果如圖3所示。

圖3 不同影響力最大化算法在LRF數(shù)據(jù)集上的影響收益對(duì)比

如圖3所示，NVPA-R算法獲得的影響收益最差，CELF++算法獲取的影響收益最好。相對(duì)于NVPA-DEG算法，NVPA-IM算法獲取的影響收益更接近于CELF++算法，即NVPA-IM算法能夠更準(zhǔn)確地挖掘影響力最大的種子節(jié)點(diǎn)。在Facebook數(shù)據(jù)集上，4種算法的影響收益對(duì)比結(jié)果如圖4所示。

如圖4所示，在Facebook數(shù)據(jù)集上，以CELF++算法獲取的影響收益為基準(zhǔn)，NVPA-IM算法的影響收益要明顯優(yōu)于NVPA-DEG算法和NVPA-R算法。該算法只有極小的精度損失，這與在LRF數(shù)據(jù)集上NVPA-IM算法的表現(xiàn)相同。由以上分析可知，本文提出的種子節(jié)點(diǎn)選取算法相對(duì)于已有算法顯著提高了算法精度。

圖4 不同影響力最大化算法在Facebook數(shù)據(jù)集上的影響收益對(duì)比

在驗(yàn)證算法效率階段，本文將其和CELF++算法進(jìn)行對(duì)比分析。為了保證算法的精度，CELF++算法為每個(gè)節(jié)點(diǎn)計(jì)算邊際收益時(shí)，均需進(jìn)行R次蒙特卡羅模擬，R一般取值為20 000。蒙特卡羅模擬的時(shí)間復(fù)雜度與網(wǎng)絡(luò)中的邊的數(shù)量成線性關(guān)系。所以，當(dāng)網(wǎng)絡(luò)的平均度較大、連邊數(shù)量較多時(shí)，CELF++算法一般效率較低。而NVPA-IM算法主要的時(shí)間開銷在社區(qū)劃分階段，由文獻(xiàn)[7]實(shí)驗(yàn)證明，NVPA社區(qū)劃分算法的效率較高。在本文實(shí)驗(yàn)中，基于IC傳播模型，在LRF數(shù)據(jù)集上，當(dāng)挖掘50個(gè)種子節(jié)點(diǎn)時(shí)，NVPA-IM算法只需要55 s，而CELF++算法需要729 s。可見，前一種算法用時(shí)只占到CELF++算法的7.5%。

3 結(jié) 語

本文提出了一種從社區(qū)層面解決影響力最大化問題的算法?；谏缃痪W(wǎng)絡(luò)的結(jié)構(gòu)，本文首先使用NVPA算法對(duì)網(wǎng)絡(luò)進(jìn)行社區(qū)劃分。考慮到劃分的過程，節(jié)點(diǎn)之間的相似度受節(jié)點(diǎn)的m跳鄰居節(jié)點(diǎn)影響。所以，本文設(shè)計(jì)了一個(gè)基于節(jié)點(diǎn)m跳及m跳以內(nèi)的種子節(jié)點(diǎn)選取算法，從劃分后的每個(gè)社區(qū)中挖掘出一個(gè)種子節(jié)點(diǎn)組成種子節(jié)點(diǎn)集。通過實(shí)驗(yàn)驗(yàn)證分析，在解決影響力最大化問題方面，與傳統(tǒng)貪心算法相比，NVPA-IM算法以一定的算法精度為代價(jià)，顯著提高了算法的運(yùn)行效率。當(dāng)然，該算法也存在一定不足，后續(xù)研究中，在影響力挖掘方面應(yīng)該更加全面地結(jié)合網(wǎng)絡(luò)和用戶的各種屬性特征進(jìn)一步精確影響效果，貼近真實(shí)。

參考文獻(xiàn)：

[1] Richardson M,Domingos P.Mining Knowledge-Sharing Sites for Viral Marketing[C].Proceedings of the Eighth ACM SIGKDD International Conference On Knowledge Discovery And Data Mining ACM,2002:61-70.

[2] Kempe D,Kleinberg J,Tardos é.Maximizing the Spread of Influence Through a Social Network[C].Proceedings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining ACM,2003:137-146.

[3] Kempe D,Kleinberg J M,Tardos é.Maximizing the Spread of Influence through a Social Network[J].Theory of Computing,2015,11(04):105-147.

[4] Morone F,Makse H A.Influence Maximization Incomplex Networks Through Optimal Percolation[J].Nature,2015,524(7563):65-68.

[5] Goyal A,Lu W,Lakshmanan L V S.Celf++:Optimizing the Greedy Algorithm for Influence Maximization in Social Networks[C].Proceedings of the 20th International Conference Companion On World Wide Web ACM,2011:47-48.

[6] Tang Y,Xiao X,Shi Y.Influence Maximization:Nearoptimal Time Complexity Meets Practical Efficiency[C].Proceedings of the 2014 ACM SIGMOD International Conference On Management of Data ACM,2014:75-86.

[7] Liang X,Tang J,Pan L.A Neighborhood Vector Propagation Algorithm for Community Detection[C].Global Communications Conference(GLOBECOM),2014:2923-2928.

[8] Newman M E J.Modularity and Community Structure in Networks[J].Proceedings of the National Academy of Scie nces,2006,103(23):8577-8582.

[9] Leskovec J,Mcauley J J.Learning to Discover Social Circles in Ego Networks[C].Advances in Neural Information Processing Systems,2012:539-547.

[10] Lancichinetti A,Fortunato S,Radicchi F.Benchmark Graphs for Testing Community Detection Algorithms[J].Physical Review E,2008,78(04):046110.

[11] Newman M E J.Fast Algorithm for Detecting Community Structure in Networks[J].Physical Review E,2004,69(06):066133.

[12] Raghavan U N,Albert R,Kumara S.Near Linear Time Algorithm to Detect Community Structures in Large-Scale Networks[J].Physical Review E,2007,76(03):036106.

[13] Chen Y C,Zhu W Y,Peng W C,et al.CIM:Communitybased Influence Maximization in Social Networks[J].ACM Transactions on Intelligent Systems and Technology(TIST),2014,5(02):25.