李蜜佳 衛(wèi)紅權(quán) 李英樂 劉樹新
(中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 河南 鄭州 450001)
對(duì)復(fù)雜網(wǎng)絡(luò)進(jìn)行深度挖掘和分析在理論和現(xiàn)實(shí)中具有重要意義[1]。社會(huì)網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一個(gè)領(lǐng)域,包括人際關(guān)系網(wǎng)、Twitter網(wǎng)和論文合著網(wǎng)等。社會(huì)網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn),由于在網(wǎng)絡(luò)中的結(jié)構(gòu)地位以及活躍度的不同,所起的作用也不同,其中有一部分節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)局部或者全局影響較大,這類節(jié)點(diǎn)就叫做關(guān)鍵節(jié)點(diǎn)。通過挖掘社會(huì)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn),可以滿足我們的很多實(shí)際需求。比如在產(chǎn)品推銷網(wǎng)絡(luò)中,商家可以消耗最少的資源實(shí)現(xiàn)產(chǎn)品最高效的推廣;在輿論傳播網(wǎng)絡(luò)中,政府可以使用最少的干預(yù)手段去宣傳輿論或者禁止謠言;在犯罪嫌疑人關(guān)系網(wǎng)絡(luò)中,警察可以快速鎖定團(tuán)伙頭目,進(jìn)而集中警力抓捕。
目前,在關(guān)鍵節(jié)點(diǎn)挖掘方面,研究人員已經(jīng)從不同的角度探索了很多算法。在基于鄰居節(jié)點(diǎn)中心性的方法中,度中心性的方法用節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量來衡量節(jié)點(diǎn)重要性,計(jì)算復(fù)雜度低,但是僅考慮了節(jié)點(diǎn)局部重要性,沒有考慮節(jié)點(diǎn)的網(wǎng)絡(luò)位置及其他全局信息,準(zhǔn)確性不高。Chen等[2]提出了一種半局部中心性方法,該方法只統(tǒng)計(jì)節(jié)點(diǎn)的四層鄰居的信息,比局部中心性的方法更準(zhǔn)確且計(jì)算復(fù)雜度低,適合于大規(guī)模網(wǎng)絡(luò),但是由于該方法沒有考慮鄰居節(jié)點(diǎn)所處的不同層次,影響了關(guān)鍵節(jié)點(diǎn)挖掘的準(zhǔn)確性。之后,Chen等[3]綜合考慮了度中心性與聚集系數(shù),又提出ClusterRank中心性,該方法適用于大規(guī)模網(wǎng)絡(luò),但把網(wǎng)絡(luò)視為無向的,與多數(shù)現(xiàn)實(shí)情況不符。趙曉暉[4]綜合考慮節(jié)點(diǎn)的半局部中心性和聚類系數(shù),提出了一種歸一化的局部中心性節(jié)點(diǎn)影響力度量算法。Kitsak等[5]認(rèn)為節(jié)點(diǎn)距離網(wǎng)絡(luò)核心越近,所產(chǎn)生的影響力也就越大,由此提出K-Shell分解法,該方法計(jì)算復(fù)雜度低,在分析大規(guī)模網(wǎng)絡(luò)方面應(yīng)用較多,但是僅對(duì)節(jié)點(diǎn)進(jìn)行粗粒度劃分,準(zhǔn)確性不高。對(duì)此,嚴(yán)沛[6]在K-Shell的基礎(chǔ)上,使用雙向搜索樹方法提高算法準(zhǔn)確性。
在基于路徑中心性的方法中,Hage等[7]認(rèn)為節(jié)點(diǎn)的影響力與節(jié)點(diǎn)到其他節(jié)點(diǎn)的距離有關(guān),提出離心中心性,該算法很容易受到特殊值的影響。Freeman[8]提出接近中心性(Closeness Centrality),節(jié)點(diǎn)的緊密度越大,越靠近網(wǎng)絡(luò)中心,也就越重要。Freeman[9]提出介數(shù)中心性(Betweenness Centrality),將節(jié)點(diǎn)的重要性由通過該節(jié)點(diǎn)的最短路徑數(shù)目來表示,這兩種算法準(zhǔn)確度高但計(jì)算復(fù)雜度也高。與介數(shù)中心性僅考慮最短路徑不同,Katz中心性[10]考慮節(jié)點(diǎn)對(duì)之間的所有路徑,并根據(jù)路徑長(zhǎng)度對(duì)路徑加權(quán),這種算法的時(shí)間復(fù)雜度也比較高。
在基于特征向量的方法中,Bonacich[10]提出特征向量中心性(Eigenvector Centrality),認(rèn)為一個(gè)節(jié)點(diǎn)的重要性要綜合考慮其鄰居節(jié)點(diǎn)的數(shù)量和質(zhì)量。Poulin等[11]假設(shè)每個(gè)節(jié)點(diǎn)都在社會(huì)網(wǎng)絡(luò)中被提名,節(jié)點(diǎn)的重要性與節(jié)點(diǎn)本身及其鄰居節(jié)點(diǎn)被提名次數(shù)有關(guān),由此提出一種累計(jì)提名中心性(Cumulative Nomination Centrality),該算法比特征向量中心性收斂要快。Google引擎使用的PageRank算法[12]是特征向量中心性的變體,該算法綜合考慮指向該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目和鄰居節(jié)點(diǎn)自身的重要性。Lü等[13]提出LeaderRank方法,引入背景節(jié)點(diǎn)使原網(wǎng)絡(luò)變?yōu)閺?qiáng)連通網(wǎng)絡(luò),從而替代了PageRank算法中的跳轉(zhuǎn)概率c,性能較PageRank有較大提升。
基于路徑和特征向量中心性的關(guān)鍵節(jié)點(diǎn)挖掘算法雖然準(zhǔn)確度高,但是普遍時(shí)間復(fù)雜度高,無法在大規(guī)模網(wǎng)絡(luò)上進(jìn)行應(yīng)用;度中心性、K-Shell分解法等時(shí)間復(fù)雜度低的算法雖然適用于大型網(wǎng)絡(luò),但是其準(zhǔn)確度又不理想,其劃分結(jié)果難以滿足精細(xì)化節(jié)點(diǎn)重要性劃分的實(shí)際需求。
基于此,本文對(duì)K-Shell分解法進(jìn)行改進(jìn),在分解過程中綜合考慮節(jié)點(diǎn)的度數(shù)與節(jié)點(diǎn)被刪除時(shí)所處的迭代層次,以解決K-Shell劃分結(jié)果粗粒化的問題。隨后采用一種用微觀結(jié)構(gòu)去替代原有完整網(wǎng)絡(luò)的算法,根據(jù)改進(jìn)的K-Shell節(jié)點(diǎn)排名提取核心網(wǎng)絡(luò),并結(jié)合PageRank值對(duì)核心網(wǎng)絡(luò)中所有節(jié)點(diǎn)做定量分析,找出影響較大的節(jié)點(diǎn),最終形成分層次的重要節(jié)點(diǎn)劃分。在三個(gè)實(shí)際網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)驗(yàn)證,結(jié)果表明本文方法具有較低的時(shí)間復(fù)雜度,計(jì)算結(jié)果也更準(zhǔn)確。
圖G的鄰接矩陣A=(aij)N×N,A=(aij)N×N是一個(gè)N階方陣,其中:
式中:aij為節(jié)點(diǎn)i與j連接。
Kitsak等[5]指出在度量節(jié)點(diǎn)重要性時(shí),需要考慮節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的位置,他們認(rèn)為處在網(wǎng)絡(luò)核心位置的節(jié)點(diǎn)會(huì)產(chǎn)生較大的影響力,并提出了K-Shell分解法。
例如,圖1是一個(gè)由15個(gè)節(jié)點(diǎn)和19條邊組成的無權(quán)無向網(wǎng)絡(luò)圖。
圖1 無向網(wǎng)絡(luò)
針對(duì)圖1所示的無向網(wǎng)絡(luò),具體分解過程如下:刪除網(wǎng)絡(luò)中所有度為1的節(jié)點(diǎn)及連邊,記迭代層數(shù)為1。觀察剩余網(wǎng)絡(luò)中是否仍有度為1的節(jié)點(diǎn),如果有,刪除節(jié)點(diǎn)及連邊,迭代層數(shù)記作2。循環(huán)去除,直至網(wǎng)絡(luò)中沒有度為1的節(jié)點(diǎn),此時(shí)將所有被刪除節(jié)點(diǎn)K-Shell值記作1。依次迭代,刪除網(wǎng)絡(luò)中度為2、3、4、5、…的節(jié)點(diǎn),直至所有節(jié)點(diǎn)都被刪除。圖2為按照K-Shell分解法對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的劃分結(jié)果。
圖2 K-Shell分解
圖3 SIR模型狀態(tài)轉(zhuǎn)移
對(duì)圖1網(wǎng)絡(luò)記錄K-Shell分解全過程如表1所示。
表1 K-Shell分解過程
K-Shell方法計(jì)算復(fù)雜度低,在分析大規(guī)模網(wǎng)絡(luò)方面應(yīng)用較多,但也存在不足。第一,K-Shell分解法不區(qū)分入度與出度,而社交網(wǎng)絡(luò)基本都屬于有向網(wǎng)絡(luò)[14],節(jié)點(diǎn)受關(guān)注的程度由節(jié)點(diǎn)的入度表示,節(jié)點(diǎn)的合群程度由出度表示,忽略入度與出度的不同,會(huì)使一些節(jié)點(diǎn)以較小的代價(jià)通過建立與核心位置節(jié)點(diǎn)的單向連邊來提高自身核數(shù),從而導(dǎo)致挖掘結(jié)果出現(xiàn)較大偏差。第二,K-Shell分解法屬于粗粒度劃分,把屬于同一層的節(jié)點(diǎn)都看作同等地位,忽略了節(jié)點(diǎn)度和節(jié)點(diǎn)被刪除時(shí)所處迭代層數(shù)的影響,導(dǎo)致大量節(jié)點(diǎn)被劃分到同一層。如在圖2的網(wǎng)絡(luò)中,節(jié)點(diǎn)1和節(jié)點(diǎn)4被K-Shell分解法劃分到同一層,K-Shell值相同,但顯然節(jié)點(diǎn)4比節(jié)點(diǎn)1重要。
對(duì)此,本文對(duì)算法作如下改進(jìn):
(1) 針對(duì)社交網(wǎng)絡(luò)多為有向網(wǎng)絡(luò)的特點(diǎn),將傳統(tǒng)的K-Shell在分解過程中不區(qū)分節(jié)點(diǎn)入度出度的做法,改為僅考慮入度對(duì)節(jié)點(diǎn)進(jìn)行剝離。
詳細(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
PageRank算法[12]是谷歌搜索引擎的核心算法。它認(rèn)為一個(gè)節(jié)點(diǎn)的重要性取決于指向它的節(jié)點(diǎn)的數(shù)目和質(zhì)量。該算法作為有向網(wǎng)絡(luò)節(jié)點(diǎn)排序最經(jīng)典的算法,被廣泛應(yīng)用于對(duì)網(wǎng)頁(yè)的排序、對(duì)社交網(wǎng)絡(luò)上用戶的排序等。作為全局性算法,PageRank計(jì)算結(jié)果較準(zhǔn)確,但時(shí)間復(fù)雜度高于K-Shell分解法。由于兩種算法相關(guān)性不大,本文綜合了兩種算法的優(yōu)勢(shì),構(gòu)建關(guān)鍵節(jié)點(diǎn)挖掘模型的步驟如下:
(1) 根據(jù)社會(huì)網(wǎng)絡(luò)相關(guān)數(shù)據(jù),構(gòu)建鄰接矩陣。
(2) 用改進(jìn)的K-Shell分解法對(duì)網(wǎng)絡(luò)所有節(jié)點(diǎn)快速打分。
(3) 按照得分高低,依次刪除外圍大約80%的不重要的節(jié)點(diǎn)及其連邊,減小網(wǎng)絡(luò)規(guī)模。
(4) 對(duì)步驟(3)中提取的核心網(wǎng)絡(luò),運(yùn)用PageRank算法計(jì)算出每個(gè)節(jié)點(diǎn)的p值,并進(jìn)行歸一化和無量綱化處理。
本文算法框架被稱作inKD-Pr算法。
本文采用SIR(Susceptible-Infective-Removal)模型[15],將節(jié)點(diǎn)的最大傳播力作為節(jié)點(diǎn)重要性評(píng)價(jià)標(biāo)準(zhǔn)。SIR模型是Kermack等提出的傳染病模型中最經(jīng)典的模型,現(xiàn)在普遍應(yīng)用于疾病傳播、謠言傳播等領(lǐng)域。
SIR模型將網(wǎng)絡(luò)節(jié)點(diǎn)分為三類:易感狀態(tài)S,指?jìng)€(gè)體可能會(huì)被處于感染狀態(tài)的鄰居節(jié)點(diǎn)感染;感染狀態(tài)I,指節(jié)點(diǎn)已被感染且具備感染力;免疫狀態(tài)R,指節(jié)點(diǎn)失去感染其他節(jié)點(diǎn)的能力。剛開始傳播時(shí),處在感染狀態(tài)I的節(jié)點(diǎn),以β的概率感染處在S狀態(tài)的鄰居節(jié)點(diǎn),隨后,處在I狀態(tài)的節(jié)點(diǎn)以概率γ轉(zhuǎn)變成為R狀態(tài),不再參與傳染。重復(fù)上述步驟直至網(wǎng)絡(luò)到達(dá)穩(wěn)態(tài)。模型可用微分方程表示如下:
在SIR模型中,全部節(jié)點(diǎn)的數(shù)量N=S(t)+I(t)+R(t),其中S(t)、I(t)、R(t)分別為在t時(shí)刻網(wǎng)絡(luò)中三種狀態(tài)節(jié)點(diǎn)的數(shù)量。
不同挖掘算法的優(yōu)劣可通過各算法挖掘的重要節(jié)點(diǎn)在SIR模型上的傳播范圍來衡量。設(shè)置一個(gè)(組)重要節(jié)點(diǎn)為S狀態(tài)在SIR模型上進(jìn)行傳播,觀察最終穩(wěn)態(tài)時(shí)處于R狀態(tài)的節(jié)點(diǎn)數(shù)量。如果一種算法的挖掘結(jié)果可使網(wǎng)絡(luò)流傳播地又快又廣,即可說明該算法挖掘效果優(yōu)于其他算法。
科布倫茨數(shù)據(jù)資料庫(kù)是公布在網(wǎng)上,供從事大規(guī)模數(shù)據(jù)處理的人員用來進(jìn)行網(wǎng)絡(luò)科學(xué)及相關(guān)領(lǐng)域研究的工具。本文選取了該資料庫(kù)三個(gè)有向無權(quán)的網(wǎng)絡(luò)數(shù)據(jù)集作為實(shí)驗(yàn)網(wǎng)絡(luò),數(shù)據(jù)集信息如表2所示。
表2 數(shù)據(jù)集的基本特性
(1) Physicians社交網(wǎng)絡(luò)數(shù)據(jù)集:節(jié)點(diǎn)代表醫(yī)生,邊表示一位醫(yī)生遇到問題會(huì)向另一位醫(yī)生求助。
(2) Blogs超鏈接數(shù)據(jù)集:節(jié)點(diǎn)代表用戶,邊表示一個(gè)用戶鏈接了另一個(gè)用戶。
(3) Ciation數(shù)據(jù)集:節(jié)點(diǎn)表示一個(gè)機(jī)場(chǎng),邊表示從一個(gè)機(jī)場(chǎng)到另一個(gè)機(jī)場(chǎng)的航班。
這三個(gè)數(shù)據(jù)集的基本情況如表2所示,稀疏性表示網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間存在連邊的概率,即網(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é)點(diǎn)數(shù)。
為了驗(yàn)證本文方法的有效性,選取3種排序方法對(duì)比分析,分別是度中心性、PageRank算法、LeaderRank算法。
本文采用單一節(jié)點(diǎn)傳播的方式,分別對(duì)排名前k(為了分析方便,設(shè)置k=10)的節(jié)點(diǎn)進(jìn)行SIR模型檢測(cè),每個(gè)節(jié)點(diǎn)都作為單一感染源進(jìn)行傳播,運(yùn)行300次取均值,每種算法的有效性由該算法挖掘出的排名前10的節(jié)點(diǎn)傳播能力總和來表示。這里將免疫率γ取為0.5。對(duì)于感染概率β,如該值太小,很難在一個(gè)較小的網(wǎng)絡(luò)區(qū)域中區(qū)分開不同算法[16]。當(dāng)β非常高,不管是從哪個(gè)節(jié)點(diǎn)開始傳播,最后傳播范圍都將覆蓋幾乎整個(gè)網(wǎng)絡(luò),導(dǎo)致無法區(qū)分節(jié)點(diǎn)的作用。對(duì)此,本文使用一個(gè)溫和的感染概率β=0.3。
如圖4所示,將免疫狀態(tài)的節(jié)點(diǎn)的累計(jì)數(shù)量繪制成時(shí)間的函數(shù),累計(jì)免疫節(jié)點(diǎn)隨時(shí)間增加,最終達(dá)到穩(wěn)定狀態(tài)。在網(wǎng)絡(luò)規(guī)模較小時(shí)(如Physicians數(shù)據(jù)集),度中心性的表現(xiàn)要優(yōu)于inKD-Pr算法和PageRank算法,但是度中心性算法的準(zhǔn)確率與網(wǎng)絡(luò)規(guī)模有關(guān),當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)增多時(shí),準(zhǔn)確率呈現(xiàn)顯著下降趨勢(shì)。這種現(xiàn)象與度中心性本身的算法有關(guān),度中心性僅以節(jié)點(diǎn)的局部信息作為衡量標(biāo)準(zhǔn),而沒有考慮節(jié)點(diǎn)所處位置、更高階鄰居等因素,這就導(dǎo)致一些邊緣節(jié)點(diǎn)可以通過與大量普通節(jié)點(diǎn)建立連邊來提高度值,而這樣的算法,在inKD-Pr算法中完全占不到優(yōu)勢(shì),inKD-Pr算法以節(jié)點(diǎn)入度為參考值去提取核心網(wǎng)絡(luò),既刪除了大量非核心節(jié)點(diǎn),同時(shí)也確保了一些節(jié)點(diǎn)無法通過僅僅依靠增加出度而進(jìn)入到核心網(wǎng)絡(luò)中。Blogs網(wǎng)絡(luò)上,度中心性算法和PageRank算法、inKD-Pr算法曲線近乎一致,即由這三種算法挖掘的前10名重要節(jié)點(diǎn)在網(wǎng)絡(luò)中的傳播能力基本相同。
(a) Physicians網(wǎng)絡(luò)
LeaderRank算法和PageRank算法在準(zhǔn)確度方面的穩(wěn)定性較佳但算法復(fù)雜度高。LeaderRank算法的準(zhǔn)確率始終優(yōu)于PageRank算法,這是因?yàn)樾枰罅繉?shí)驗(yàn)才能獲取PageRank算法中的阻尼系數(shù)s,且會(huì)改變?cè)瓉淼木仃嚱Y(jié)構(gòu)。而LeaderRank[17]在PageRank的基礎(chǔ)上,加入一個(gè)與其他節(jié)點(diǎn)都有雙向連邊的節(jié)點(diǎn),實(shí)現(xiàn)網(wǎng)絡(luò)的強(qiáng)連通,以此得到一個(gè)無參數(shù)的算法。實(shí)驗(yàn)證明,這種算法比PageRank算法更準(zhǔn)確。
inKD-Pr算法在網(wǎng)絡(luò)規(guī)模小的時(shí)候準(zhǔn)確率比較低,這是因?yàn)镵-Shell算法對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)只能做粗粒度的劃分。節(jié)點(diǎn)的K-Shell值越大,節(jié)點(diǎn)就越重要[5]。但具體到兩個(gè)節(jié)點(diǎn),只有K-Shell值相差很大,比如在10倍以上時(shí),節(jié)點(diǎn)影響力才有顯著差距。而在小規(guī)模網(wǎng)絡(luò)中,節(jié)點(diǎn)的K-Shell值相差都不大,這就導(dǎo)致部分重要節(jié)點(diǎn)在用K-Shell分解法提取核心網(wǎng)絡(luò)時(shí)被刪除。在本文的實(shí)驗(yàn)中可以看到,隨著網(wǎng)絡(luò)規(guī)模變大,這種算法的準(zhǔn)確度也越高。在Ciation網(wǎng)絡(luò)中,inKD-Pr算法的準(zhǔn)確率甚至優(yōu)于LeaderRank算法,這是因?yàn)镵-Shell分解法可以有效剔除一些大度節(jié)點(diǎn)的干擾。
本文將各算法挖掘出的Top-10節(jié)點(diǎn)與SIR模型挖掘出的Top-10節(jié)點(diǎn)進(jìn)行對(duì)比,比值為各算法挖掘Top-10節(jié)點(diǎn)的準(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模型每一次傳播到達(dá)穩(wěn)態(tài)需要的時(shí)間比較長(zhǎng),本文最大只選取節(jié)點(diǎn)數(shù)為12 000多的社交網(wǎng)絡(luò)進(jìn)行計(jì)算。從實(shí)驗(yàn)結(jié)果可以預(yù)見,網(wǎng)絡(luò)規(guī)模越大,inKD-Pr算法挖掘重要節(jié)點(diǎn)的效果會(huì)更好。
表3 各算法挖掘出的Top-10節(jié)點(diǎn)準(zhǔn)確率與SIR模型對(duì)比
本文提出的inKD-Pr算法是在K-Shell分解法的基礎(chǔ)上進(jìn)行改進(jìn)的,可近似看作O(n),與K-Shell分解法相同。PageRank的計(jì)算復(fù)雜度為O(mI),度中心性的時(shí)間復(fù)雜度為O(n),介數(shù)中心性的時(shí)間復(fù)雜度為O(mn),其中:n和m分別為網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊的數(shù)量;I為迭代次數(shù)。從表4可以看出,本文所提出的inKD-Pr算法計(jì)算復(fù)雜度相對(duì)較低。
表4 部分重要節(jié)點(diǎn)挖掘算法時(shí)間復(fù)雜度