基于改進K-Shell的社會網(wǎng)絡(luò)關(guān)鍵節(jié)點挖掘算法

李蜜佳 衛(wèi)紅權(quán) 李英樂 劉樹新

(中國人民解放軍戰(zhàn)略支援部隊信息工程大學(xué) 河南 鄭州 450001)

0 引 言

對復(fù)雜網(wǎng)絡(luò)進行深度挖掘和分析在理論和現(xiàn)實中具有重要意義[1]。社會網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一個領(lǐng)域,包括人際關(guān)系網(wǎng)、Twitter網(wǎng)和論文合著網(wǎng)等。社會網(wǎng)絡(luò)中的各個節(jié)點,由于在網(wǎng)絡(luò)中的結(jié)構(gòu)地位以及活躍度的不同,所起的作用也不同,其中有一部分節(jié)點對網(wǎng)絡(luò)局部或者全局影響較大,這類節(jié)點就叫做關(guān)鍵節(jié)點。通過挖掘社會網(wǎng)絡(luò)中的關(guān)鍵節(jié)點,可以滿足我們的很多實際需求。比如在產(chǎn)品推銷網(wǎng)絡(luò)中,商家可以消耗最少的資源實現(xiàn)產(chǎn)品最高效的推廣;在輿論傳播網(wǎng)絡(luò)中,政府可以使用最少的干預(yù)手段去宣傳輿論或者禁止謠言;在犯罪嫌疑人關(guān)系網(wǎng)絡(luò)中,警察可以快速鎖定團伙頭目,進而集中警力抓捕。

目前,在關(guān)鍵節(jié)點挖掘方面,研究人員已經(jīng)從不同的角度探索了很多算法。在基于鄰居節(jié)點中心性的方法中,度中心性的方法用節(jié)點的鄰居節(jié)點數(shù)量來衡量節(jié)點重要性,計算復(fù)雜度低,但是僅考慮了節(jié)點局部重要性,沒有考慮節(jié)點的網(wǎng)絡(luò)位置及其他全局信息,準(zhǔn)確性不高。Chen等[2]提出了一種半局部中心性方法,該方法只統(tǒng)計節(jié)點的四層鄰居的信息,比局部中心性的方法更準(zhǔn)確且計算復(fù)雜度低,適合于大規(guī)模網(wǎng)絡(luò),但是由于該方法沒有考慮鄰居節(jié)點所處的不同層次,影響了關(guān)鍵節(jié)點挖掘的準(zhǔn)確性。之后,Chen等[3]綜合考慮了度中心性與聚集系數(shù),又提出ClusterRank中心性,該方法適用于大規(guī)模網(wǎng)絡(luò),但把網(wǎng)絡(luò)視為無向的,與多數(shù)現(xiàn)實情況不符。趙曉暉[4]綜合考慮節(jié)點的半局部中心性和聚類系數(shù),提出了一種歸一化的局部中心性節(jié)點影響力度量算法。Kitsak等[5]認(rèn)為節(jié)點距離網(wǎng)絡(luò)核心越近,所產(chǎn)生的影響力也就越大,由此提出K-Shell分解法,該方法計算復(fù)雜度低,在分析大規(guī)模網(wǎng)絡(luò)方面應(yīng)用較多,但是僅對節(jié)點進行粗粒度劃分,準(zhǔn)確性不高。對此,嚴(yán)沛[6]在K-Shell的基礎(chǔ)上,使用雙向搜索樹方法提高算法準(zhǔn)確性。

在基于路徑中心性的方法中,Hage等[7]認(rèn)為節(jié)點的影響力與節(jié)點到其他節(jié)點的距離有關(guān),提出離心中心性,該算法很容易受到特殊值的影響。Freeman[8]提出接近中心性(Closeness Centrality),節(jié)點的緊密度越大,越靠近網(wǎng)絡(luò)中心,也就越重要。Freeman[9]提出介數(shù)中心性(Betweenness Centrality),將節(jié)點的重要性由通過該節(jié)點的最短路徑數(shù)目來表示,這兩種算法準(zhǔn)確度高但計算復(fù)雜度也高。與介數(shù)中心性僅考慮最短路徑不同,Katz中心性[10]考慮節(jié)點對之間的所有路徑,并根據(jù)路徑長度對路徑加權(quán),這種算法的時間復(fù)雜度也比較高。

在基于特征向量的方法中,Bonacich[10]提出特征向量中心性(Eigenvector Centrality),認(rèn)為一個節(jié)點的重要性要綜合考慮其鄰居節(jié)點的數(shù)量和質(zhì)量。Poulin等[11]假設(shè)每個節(jié)點都在社會網(wǎng)絡(luò)中被提名,節(jié)點的重要性與節(jié)點本身及其鄰居節(jié)點被提名次數(shù)有關(guān),由此提出一種累計提名中心性(Cumulative Nomination Centrality),該算法比特征向量中心性收斂要快。Google引擎使用的PageRank算法[12]是特征向量中心性的變體,該算法綜合考慮指向該節(jié)點的鄰居節(jié)點數(shù)目和鄰居節(jié)點自身的重要性。Lü等[13]提出LeaderRank方法,引入背景節(jié)點使原網(wǎng)絡(luò)變?yōu)閺娺B通網(wǎng)絡(luò),從而替代了PageRank算法中的跳轉(zhuǎn)概率c,性能較PageRank有較大提升。

基于路徑和特征向量中心性的關(guān)鍵節(jié)點挖掘算法雖然準(zhǔn)確度高,但是普遍時間復(fù)雜度高,無法在大規(guī)模網(wǎng)絡(luò)上進行應(yīng)用;度中心性、K-Shell分解法等時間復(fù)雜度低的算法雖然適用于大型網(wǎng)絡(luò),但是其準(zhǔn)確度又不理想,其劃分結(jié)果難以滿足精細(xì)化節(jié)點重要性劃分的實際需求。

基于此,本文對K-Shell分解法進行改進,在分解過程中綜合考慮節(jié)點的度數(shù)與節(jié)點被刪除時所處的迭代層次,以解決K-Shell劃分結(jié)果粗?；膯栴}。隨后采用一種用微觀結(jié)構(gòu)去替代原有完整網(wǎng)絡(luò)的算法,根據(jù)改進的K-Shell節(jié)點排名提取核心網(wǎng)絡(luò),并結(jié)合PageRank值對核心網(wǎng)絡(luò)中所有節(jié)點做定量分析,找出影響較大的節(jié)點,最終形成分層次的重要節(jié)點劃分。在三個實際網(wǎng)絡(luò)中進行實驗驗證,結(jié)果表明本文方法具有較低的時間復(fù)雜度,計算結(jié)果也更準(zhǔn)確。

1 算法設(shè)計

圖G的鄰接矩陣A=(aij)N×N,A=(aij)N×N是一個N階方陣,其中:

式中:aij為節(jié)點i與j連接。

1.1 K-Shell分解法

Kitsak等[5]指出在度量節(jié)點重要性時,需要考慮節(jié)點在整個網(wǎng)絡(luò)中的位置,他們認(rèn)為處在網(wǎng)絡(luò)核心位置的節(jié)點會產(chǎn)生較大的影響力,并提出了K-Shell分解法。

例如,圖1是一個由15個節(jié)點和19條邊組成的無權(quán)無向網(wǎng)絡(luò)圖。

圖1 無向網(wǎng)絡(luò)

針對圖1所示的無向網(wǎng)絡(luò),具體分解過程如下:刪除網(wǎng)絡(luò)中所有度為1的節(jié)點及連邊,記迭代層數(shù)為1。觀察剩余網(wǎng)絡(luò)中是否仍有度為1的節(jié)點,如果有,刪除節(jié)點及連邊,迭代層數(shù)記作2。循環(huán)去除,直至網(wǎng)絡(luò)中沒有度為1的節(jié)點,此時將所有被刪除節(jié)點K-Shell值記作1。依次迭代,刪除網(wǎng)絡(luò)中度為2、3、4、5、…的節(jié)點,直至所有節(jié)點都被刪除。圖2為按照K-Shell分解法對網(wǎng)絡(luò)中所有節(jié)點的劃分結(jié)果。

圖2 K-Shell分解

圖3 SIR模型狀態(tài)轉(zhuǎn)移

對圖1網(wǎng)絡(luò)記錄K-Shell分解全過程如表1所示。

表1 K-Shell分解過程

1.2 改進的K-Shell分解法

K-Shell方法計算復(fù)雜度低,在分析大規(guī)模網(wǎng)絡(luò)方面應(yīng)用較多,但也存在不足。第一,K-Shell分解法不區(qū)分入度與出度,而社交網(wǎng)絡(luò)基本都屬于有向網(wǎng)絡(luò)[14],節(jié)點受關(guān)注的程度由節(jié)點的入度表示,節(jié)點的合群程度由出度表示,忽略入度與出度的不同,會使一些節(jié)點以較小的代價通過建立與核心位置節(jié)點的單向連邊來提高自身核數(shù),從而導(dǎo)致挖掘結(jié)果出現(xiàn)較大偏差。第二,K-Shell分解法屬于粗粒度劃分,把屬于同一層的節(jié)點都看作同等地位,忽略了節(jié)點度和節(jié)點被刪除時所處迭代層數(shù)的影響,導(dǎo)致大量節(jié)點被劃分到同一層。如在圖2的網(wǎng)絡(luò)中,節(jié)點1和節(jié)點4被K-Shell分解法劃分到同一層,K-Shell值相同,但顯然節(jié)點4比節(jié)點1重要。

對此,本文對算法作如下改進:

(1) 針對社交網(wǎng)絡(luò)多為有向網(wǎng)絡(luò)的特點,將傳統(tǒng)的K-Shell在分解過程中不區(qū)分節(jié)點入度出度的做法,改為僅考慮入度對節(jié)點進行剝離。

詳細(xì)分解步驟為:

偽代碼如下:

輸入:nodes list V,Links list B。

Ks=1;

n=1;

while(|V|≠0)

add removal node i into set Vk-core(n);

add removal node i into set Vk-core(Ks);

end while

delete node i and related links;

update V and E;

n++;

end while

core++;

end while

1.3 inKD-Pr算法

PageRank算法[12]是谷歌搜索引擎的核心算法。它認(rèn)為一個節(jié)點的重要性取決于指向它的節(jié)點的數(shù)目和質(zhì)量。該算法作為有向網(wǎng)絡(luò)節(jié)點排序最經(jīng)典的算法,被廣泛應(yīng)用于對網(wǎng)頁的排序、對社交網(wǎng)絡(luò)上用戶的排序等。作為全局性算法,PageRank計算結(jié)果較準(zhǔn)確,但時間復(fù)雜度高于K-Shell分解法。由于兩種算法相關(guān)性不大,本文綜合了兩種算法的優(yōu)勢,構(gòu)建關(guān)鍵節(jié)點挖掘模型的步驟如下:

(1) 根據(jù)社會網(wǎng)絡(luò)相關(guān)數(shù)據(jù),構(gòu)建鄰接矩陣。

(2) 用改進的K-Shell分解法對網(wǎng)絡(luò)所有節(jié)點快速打分。

(3) 按照得分高低,依次刪除外圍大約80%的不重要的節(jié)點及其連邊,減小網(wǎng)絡(luò)規(guī)模。

(4) 對步驟(3)中提取的核心網(wǎng)絡(luò),運用PageRank算法計算出每個節(jié)點的p值,并進行歸一化和無量綱化處理。

本文算法框架被稱作inKD-Pr算法。

2 評估標(biāo)準(zhǔn)及數(shù)據(jù)集介紹

2.1 評估標(biāo)準(zhǔn)

本文采用SIR(Susceptible-Infective-Removal)模型[15],將節(jié)點的最大傳播力作為節(jié)點重要性評價標(biāo)準(zhǔn)。SIR模型是Kermack等提出的傳染病模型中最經(jīng)典的模型,現(xiàn)在普遍應(yīng)用于疾病傳播、謠言傳播等領(lǐng)域。

SIR模型將網(wǎng)絡(luò)節(jié)點分為三類:易感狀態(tài)S,指個體可能會被處于感染狀態(tài)的鄰居節(jié)點感染;感染狀態(tài)I,指節(jié)點已被感染且具備感染力;免疫狀態(tài)R,指節(jié)點失去感染其他節(jié)點的能力。剛開始傳播時,處在感染狀態(tài)I的節(jié)點,以β的概率感染處在S狀態(tài)的鄰居節(jié)點,隨后,處在I狀態(tài)的節(jié)點以概率γ轉(zhuǎn)變成為R狀態(tài),不再參與傳染。重復(fù)上述步驟直至網(wǎng)絡(luò)到達穩(wěn)態(tài)。模型可用微分方程表示如下:

在SIR模型中,全部節(jié)點的數(shù)量N=S(t)+I(t)+R(t),其中S(t)、I(t)、R(t)分別為在t時刻網(wǎng)絡(luò)中三種狀態(tài)節(jié)點的數(shù)量。

不同挖掘算法的優(yōu)劣可通過各算法挖掘的重要節(jié)點在SIR模型上的傳播范圍來衡量。設(shè)置一個(組)重要節(jié)點為S狀態(tài)在SIR模型上進行傳播,觀察最終穩(wěn)態(tài)時處于R狀態(tài)的節(jié)點數(shù)量。如果一種算法的挖掘結(jié)果可使網(wǎng)絡(luò)流傳播地又快又廣,即可說明該算法挖掘效果優(yōu)于其他算法。

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

科布倫茨數(shù)據(jù)資料庫是公布在網(wǎng)上,供從事大規(guī)模數(shù)據(jù)處理的人員用來進行網(wǎng)絡(luò)科學(xué)及相關(guān)領(lǐng)域研究的工具。本文選取了該資料庫三個有向無權(quán)的網(wǎng)絡(luò)數(shù)據(jù)集作為實驗網(wǎng)絡(luò),數(shù)據(jù)集信息如表2所示。

表2 數(shù)據(jù)集的基本特性

(1) Physicians社交網(wǎng)絡(luò)數(shù)據(jù)集:節(jié)點代表醫(yī)生,邊表示一位醫(yī)生遇到問題會向另一位醫(yī)生求助。

(2) Blogs超鏈接數(shù)據(jù)集:節(jié)點代表用戶,邊表示一個用戶鏈接了另一個用戶。

(3) Ciation數(shù)據(jù)集:節(jié)點表示一個機場,邊表示從一個機場到另一個機場的航班。

這三個數(shù)據(jù)集的基本情況如表2所示,稀疏性表示網(wǎng)絡(luò)中任意兩個節(jié)點間存在連邊的概率,即網(wǎng)絡(luò)中存在的連邊數(shù)量占網(wǎng)絡(luò)中所有可能連邊數(shù)的比例。在有向無環(huán)網(wǎng)絡(luò)中,網(wǎng)絡(luò)的稀疏性=m/[n(n-1)],其中:m為網(wǎng)絡(luò)中邊的數(shù)目;n為網(wǎng)絡(luò)中節(jié)點數(shù)。

3 仿真驗證

3.1 實驗設(shè)計

為了驗證本文方法的有效性,選取3種排序方法對比分析,分別是度中心性、PageRank算法、LeaderRank算法。

本文采用單一節(jié)點傳播的方式,分別對排名前k(為了分析方便,設(shè)置k=10)的節(jié)點進行SIR模型檢測,每個節(jié)點都作為單一感染源進行傳播,運行300次取均值,每種算法的有效性由該算法挖掘出的排名前10的節(jié)點傳播能力總和來表示。這里將免疫率γ取為0.5。對于感染概率β,如該值太小,很難在一個較小的網(wǎng)絡(luò)區(qū)域中區(qū)分開不同算法[16]。當(dāng)β非常高,不管是從哪個節(jié)點開始傳播,最后傳播范圍都將覆蓋幾乎整個網(wǎng)絡(luò),導(dǎo)致無法區(qū)分節(jié)點的作用。對此,本文使用一個溫和的感染概率β=0.3。

3.2 實驗結(jié)果

如圖4所示,將免疫狀態(tài)的節(jié)點的累計數(shù)量繪制成時間的函數(shù),累計免疫節(jié)點隨時間增加,最終達到穩(wěn)定狀態(tài)。在網(wǎng)絡(luò)規(guī)模較小時(如Physicians數(shù)據(jù)集),度中心性的表現(xiàn)要優(yōu)于inKD-Pr算法和PageRank算法,但是度中心性算法的準(zhǔn)確率與網(wǎng)絡(luò)規(guī)模有關(guān),當(dāng)網(wǎng)絡(luò)中節(jié)點數(shù)增多時,準(zhǔn)確率呈現(xiàn)顯著下降趨勢。這種現(xiàn)象與度中心性本身的算法有關(guān),度中心性僅以節(jié)點的局部信息作為衡量標(biāo)準(zhǔn),而沒有考慮節(jié)點所處位置、更高階鄰居等因素,這就導(dǎo)致一些邊緣節(jié)點可以通過與大量普通節(jié)點建立連邊來提高度值,而這樣的算法,在inKD-Pr算法中完全占不到優(yōu)勢,inKD-Pr算法以節(jié)點入度為參考值去提取核心網(wǎng)絡(luò),既刪除了大量非核心節(jié)點,同時也確保了一些節(jié)點無法通過僅僅依靠增加出度而進入到核心網(wǎng)絡(luò)中。Blogs網(wǎng)絡(luò)上,度中心性算法和PageRank算法、inKD-Pr算法曲線近乎一致,即由這三種算法挖掘的前10名重要節(jié)點在網(wǎng)絡(luò)中的傳播能力基本相同。

(a) Physicians網(wǎng)絡(luò)

LeaderRank算法和PageRank算法在準(zhǔn)確度方面的穩(wěn)定性較佳但算法復(fù)雜度高。LeaderRank算法的準(zhǔn)確率始終優(yōu)于PageRank算法,這是因為需要大量實驗才能獲取PageRank算法中的阻尼系數(shù)s,且會改變原來的矩陣結(jié)構(gòu)。而LeaderRank[17]在PageRank的基礎(chǔ)上,加入一個與其他節(jié)點都有雙向連邊的節(jié)點,實現(xiàn)網(wǎng)絡(luò)的強連通,以此得到一個無參數(shù)的算法。實驗證明,這種算法比PageRank算法更準(zhǔn)確。

inKD-Pr算法在網(wǎng)絡(luò)規(guī)模小的時候準(zhǔn)確率比較低,這是因為K-Shell算法對網(wǎng)絡(luò)中的節(jié)點只能做粗粒度的劃分。節(jié)點的K-Shell值越大,節(jié)點就越重要[5]。但具體到兩個節(jié)點,只有K-Shell值相差很大,比如在10倍以上時,節(jié)點影響力才有顯著差距。而在小規(guī)模網(wǎng)絡(luò)中,節(jié)點的K-Shell值相差都不大,這就導(dǎo)致部分重要節(jié)點在用K-Shell分解法提取核心網(wǎng)絡(luò)時被刪除。在本文的實驗中可以看到,隨著網(wǎng)絡(luò)規(guī)模變大,這種算法的準(zhǔn)確度也越高。在Ciation網(wǎng)絡(luò)中,inKD-Pr算法的準(zhǔn)確率甚至優(yōu)于LeaderRank算法,這是因為K-Shell分解法可以有效剔除一些大度節(jié)點的干擾。

3.3 準(zhǔn)確率分析

本文將各算法挖掘出的Top-10節(jié)點與SIR模型挖掘出的Top-10節(jié)點進行對比,比值為各算法挖掘Top-10節(jié)點的準(zhǔn)確率。表3的結(jié)果表明,網(wǎng)絡(luò)規(guī)模越大,度中心性挖掘算法的準(zhǔn)確性越低。相比,在不同規(guī)模的網(wǎng)絡(luò)中,PageRank算法和LeaderRank算法具有更好的穩(wěn)定性。本文提出的inKD-Pr算法隨著網(wǎng)絡(luò)規(guī)模增大,準(zhǔn)確率也越高。但由于SIR模型每一次傳播到達穩(wěn)態(tài)需要的時間比較長,本文最大只選取節(jié)點數(shù)為12 000多的社交網(wǎng)絡(luò)進行計算。從實驗結(jié)果可以預(yù)見,網(wǎng)絡(luò)規(guī)模越大,inKD-Pr算法挖掘重要節(jié)點的效果會更好。

表3 各算法挖掘出的Top-10節(jié)點準(zhǔn)確率與SIR模型對比

3.4 時間復(fù)雜度分析

本文提出的inKD-Pr算法是在K-Shell分解法的基礎(chǔ)上進行改進的,可近似看作O(n),與K-Shell分解法相同。PageRank的計算復(fù)雜度為O(mI),度中心性的時間復(fù)雜度為O(n),介數(shù)中心性的時間復(fù)雜度為O(mn),其中:n和m分別為網(wǎng)絡(luò)中的節(jié)點和邊的數(shù)量;I為迭代次數(shù)。從表4可以看出,本文所提出的inKD-Pr算法計算復(fù)雜度相對較低。

表4 部分重要節(jié)點挖掘算法時間復(fù)雜度

4 結(jié) 語