一種基于K-shell和半局部信息的節(jié)點(diǎn)重要性排序方法

謝越

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0 引言

隨著信息技術(shù)的快速發(fā)展，人類的社會(huì)活動(dòng)在越來越多的方面表現(xiàn)出網(wǎng)絡(luò)化的特征。目前，我們的生活中已經(jīng)充滿了各種各樣的網(wǎng)絡(luò)[1]，例如生物信息網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)、電力系統(tǒng)網(wǎng)絡(luò)以及在最近幾年迅猛發(fā)展的在線社交網(wǎng)絡(luò)等。研究者們通過對(duì)各種不同類型的網(wǎng)絡(luò)進(jìn)行統(tǒng)計(jì)分析，對(duì)這些網(wǎng)絡(luò)在傳播動(dòng)力學(xué)等方面表現(xiàn)出來的特性有了更進(jìn)一步的了解[2]。

近些年，網(wǎng)絡(luò)科學(xué)在信息技術(shù)的幫助下取得了快速發(fā)展，對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)按重要性進(jìn)行排序成為研究者們?nèi)找骊P(guān)注的問題。孫睿等[3]對(duì)在網(wǎng)絡(luò)輿論中對(duì)節(jié)點(diǎn)的重要性進(jìn)行排序的研究現(xiàn)狀進(jìn)行了介紹，并分別對(duì)基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和基于節(jié)點(diǎn)屬性進(jìn)行節(jié)點(diǎn)重要性排序的方法進(jìn)行了總結(jié)。但是，近幾年有越來越多的研究者開始從更多新的角度對(duì)節(jié)點(diǎn)排序問題進(jìn)行研究，例如Kitsak等人[4]于2010年首次提出了K-shell分解方法，并且通過該方法得到了比度指標(biāo)、介數(shù)中心性等方法更為準(zhǔn)確的排序結(jié)果，該方法的主要思想是認(rèn)為節(jié)點(diǎn)的重要性取決于節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置。這個(gè)方法提出后，受到了研究者們的廣泛關(guān)注，因此有必要對(duì)該方法進(jìn)行更加深入和廣泛的研究。

1 相關(guān)工作

1.1 網(wǎng)絡(luò)的表示方法

設(shè)網(wǎng)絡(luò)由圖G=（V,E）表示，則網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量為|V|，邊的數(shù)量為|E|，該網(wǎng)絡(luò)的鄰接矩陣記為AN×N=(aij)，無向網(wǎng)絡(luò)中aij=1當(dāng)且僅當(dāng)節(jié)點(diǎn)vi和vj之間有連邊，否則aij=0；有向網(wǎng)絡(luò)中，aij=1當(dāng)且僅當(dāng)存在一條從節(jié)點(diǎn)vi指向vj的有向邊，否則aij=0。將網(wǎng)絡(luò)中與節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的個(gè)數(shù)記為節(jié)點(diǎn)的度（de?gree）ki，具體表示為

多年以來，針對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)排序問題，已經(jīng)提出了許多的方法，如度中心性[4]、介數(shù)中心性[5]、接近中心性[6]和基于特征向量的中心性[7]方法。度中心性方法是一種簡(jiǎn)單有效的局部性方法，忽略了網(wǎng)絡(luò)的全局結(jié)構(gòu)；介數(shù)中心性和接近中心性方法能夠得到很好的排序結(jié)果，但是由于具有較高的計(jì)算復(fù)雜度，不能很好地應(yīng)用到大規(guī)模網(wǎng)絡(luò)中。

1.2 K-shell分解方法

由于度指標(biāo)僅考慮了節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的情況，所以是一種反映節(jié)點(diǎn)局部特征的方法，并且認(rèn)為如果兩個(gè)節(jié)點(diǎn)的度數(shù)相同，那么這兩個(gè)節(jié)點(diǎn)也具有相同的重要性[8]。然而，近些年有些研究發(fā)現(xiàn)，通過分析節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置，對(duì)于判斷節(jié)點(diǎn)的重要性也具有至關(guān)重要的作用。如果一個(gè)節(jié)點(diǎn)位于網(wǎng)絡(luò)的中心位置，那么即使這個(gè)節(jié)點(diǎn)的度數(shù)較小，該節(jié)點(diǎn)仍然具有較高的重要性；反之，如果一個(gè)節(jié)點(diǎn)處于網(wǎng)絡(luò)的邊緣位置，那么即使該節(jié)點(diǎn)具有較大的度數(shù)，這個(gè)節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)產(chǎn)生的影響也是有限的。Kitsak等人[9]基于這個(gè)思想，提出了K-shell分解方法，對(duì)節(jié)點(diǎn)的重要性進(jìn)行了一種較粗粒度的劃分。K-shell分解方法通過將網(wǎng)絡(luò)中的節(jié)點(diǎn)通過遞歸的剝離，將節(jié)點(diǎn)劃分為不同的層次，具體過程如下：首先，去掉網(wǎng)絡(luò)中度為1的節(jié)點(diǎn)及其連邊，剩下一個(gè)子圖，檢查子圖中是否存在度為1的節(jié)點(diǎn)，如果存在，則繼續(xù)進(jìn)行刪除操作。重復(fù)以上的操作，直到在子圖中找不到度數(shù)為1的節(jié)點(diǎn)為止。至此，這些被刪除的節(jié)點(diǎn)構(gòu)成Ks=1的殼。在剩下的網(wǎng)絡(luò)中，所有節(jié)點(diǎn)的度都不小于2，重復(fù)上面的操作，刪除網(wǎng)絡(luò)中度為2的節(jié)點(diǎn)，得到構(gòu)成Ks值為2的第二層。依次類推，直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都被劃分到某一個(gè)層次。

圖1為K-shell分解的示例[9]，圖中，節(jié)點(diǎn)6和節(jié)點(diǎn)12的擁有相同的度數(shù)，但是它們?cè)诰W(wǎng)絡(luò)中處于不同的層。由此可以發(fā)現(xiàn)，單純使用節(jié)點(diǎn)的度來對(duì)節(jié)點(diǎn)進(jìn)行排序，并不能十分準(zhǔn)確地將節(jié)點(diǎn)排到正確的位置。

圖1 K-shell分解示例網(wǎng)絡(luò)

K-shell方法具有較低的時(shí)間復(fù)雜度，僅為O(m)，非常適合用于對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行分析，但是K-shell方法存在著一定的缺陷，即排序的結(jié)果太過于粗?；?，導(dǎo)致節(jié)點(diǎn)之間的重要性區(qū)分度不大[8]。針對(duì)K-shell方法中存在的這個(gè)問題，本文利用K-shell方法分解過程中節(jié)點(diǎn)被刪除時(shí)迭代的層數(shù)并結(jié)合節(jié)點(diǎn)的半局部信息，對(duì)具有相同排序值的節(jié)點(diǎn)的進(jìn)行進(jìn)一步區(qū)分，從而提高排序結(jié)果的區(qū)分度。

2 結(jié)合半局部信息的改進(jìn)K-shell方法

對(duì)圖1的網(wǎng)絡(luò)進(jìn)行K-shell分解，整個(gè)K-shell分解過程如表1所示：

表1 K-shell分解過程

從表1的數(shù)據(jù)中可以發(fā)現(xiàn)，節(jié)點(diǎn)2與節(jié)點(diǎn)6具有相同的Ks值，但是通過對(duì)圖1的網(wǎng)絡(luò)進(jìn)行觀察可以發(fā)現(xiàn)，節(jié)點(diǎn)2與節(jié)點(diǎn)6對(duì)網(wǎng)絡(luò)產(chǎn)生的影響是不同的，這是由于K-shell方法的排序結(jié)果具有較低的分別率導(dǎo)致的。從表1的第一列中可以發(fā)現(xiàn)，節(jié)點(diǎn)2與節(jié)點(diǎn)6在不同的迭代層數(shù)中被刪除。因此將節(jié)點(diǎn)在刪除操作中的迭代層數(shù)融入到Ks值中，并結(jié)合節(jié)點(diǎn)的度，從而進(jìn)一步區(qū)分相同Ks值的節(jié)點(diǎn)的重要性。

定義1：給定一個(gè)網(wǎng)絡(luò)G=（V,E），網(wǎng)絡(luò)中節(jié)點(diǎn)i的度記為d，Ks值記為k，刪去節(jié)點(diǎn)i時(shí)的迭代層數(shù)記為n，則融合節(jié)點(diǎn)的度和迭代層數(shù)的Ks值表示為：

對(duì)于圖1示例的網(wǎng)絡(luò)中的節(jié)點(diǎn)6來說，其Ks=1，n=3，d=4，因此 Ksd（6）=1*3+4=7；對(duì)于節(jié)點(diǎn) 2 來說，其Ks=1，n=1，d=1，因此 Ksd（2）=1*1+1=2?？梢园l(fā)現(xiàn)，通過將節(jié)點(diǎn)的度及刪除該節(jié)點(diǎn)時(shí)的迭代層數(shù)相融合，能夠得到更加準(zhǔn)確的劃分結(jié)果。

Bae等人[10]同時(shí)考慮節(jié)點(diǎn)的度數(shù)與Ks值，認(rèn)為如果一個(gè)節(jié)點(diǎn)位于網(wǎng)絡(luò)的中心位置，并且同時(shí)擁有較多的鄰居，那么這個(gè)節(jié)點(diǎn)也就能對(duì)網(wǎng)絡(luò)產(chǎn)生較大的影響。本文通過將Ksd值與節(jié)點(diǎn)的半局部信息進(jìn)行結(jié)合，最終得到擴(kuò)展的EKsd值。

定義2：給定一個(gè)網(wǎng)絡(luò)G=（V,E），網(wǎng)絡(luò)中節(jié)點(diǎn)i的Ksd值記為Ksd(i)，i的鄰居集合記為N(i)，則擴(kuò)展的Eksd值表示為：

對(duì)圖1中的示例網(wǎng)絡(luò)分別使用不同的方法進(jìn)行節(jié)點(diǎn)排序，所得的結(jié)果如表2所示。通過對(duì)表2進(jìn)行觀察可以發(fā)現(xiàn)，單純的使用度指標(biāo)和Ks值得到的排序結(jié)果，都會(huì)出現(xiàn)許多節(jié)點(diǎn)擁有相同的排序值的情況，而通過使用結(jié)合半局部信息和Ksd值的方法對(duì)節(jié)點(diǎn)進(jìn)行排序，得到的結(jié)果則具有更高的區(qū)分度。使用EKsd值得到的排序結(jié)果之所以能夠得到更好的排序結(jié)果，是因?yàn)樵谠摲椒ㄖ型瑫r(shí)使用了表現(xiàn)節(jié)點(diǎn)全局特征的Ksd值和表現(xiàn)節(jié)點(diǎn)局部特征的半局部信息。

表2 不同度量指標(biāo)對(duì)示例網(wǎng)絡(luò)的排序結(jié)果

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

本文選取degree、Ks值、MDD三個(gè)指標(biāo)與EKsd值進(jìn)行比較，通過實(shí)驗(yàn)驗(yàn)證EKsd值方法對(duì)節(jié)點(diǎn)進(jìn)行排序的結(jié)果的效果。首先對(duì)EKsd值度量結(jié)果的分辨率進(jìn)行測(cè)試，即測(cè)試在排序結(jié)果中是否出現(xiàn)大量節(jié)點(diǎn)具有相同度量值的情況；接著對(duì)EKsd值度量結(jié)果的正確性進(jìn)行測(cè)試，將通過ESkd值度量排序的結(jié)果與通過SIR模型得到的結(jié)果相比較，如果所得結(jié)果與通過SIR模型得到的結(jié)果越相近，則說明排序結(jié)果的正確性越高。本文選取三個(gè)不同類型的現(xiàn)實(shí)網(wǎng)絡(luò)，通過進(jìn)行實(shí)驗(yàn)驗(yàn)證所提方法的有效性。數(shù)據(jù)集的具體數(shù)據(jù)如表3所示。

表3 實(shí)驗(yàn)數(shù)據(jù)集

其中，Netscience[11]網(wǎng)絡(luò)是科研合作網(wǎng)絡(luò)，該網(wǎng)絡(luò)中包含都是從事科學(xué)研究的人員及其相互關(guān)系；Email[12]網(wǎng)絡(luò)來源于是西班牙羅維拉維爾吉利大學(xué)的Email網(wǎng)絡(luò)；Blogs[13]網(wǎng)絡(luò)來源于MSN社交網(wǎng)絡(luò)，網(wǎng)絡(luò)中包含各節(jié)點(diǎn)之間的相互關(guān)系。

3.1 分辨率指標(biāo)

文獻(xiàn)[10]中提出了一種用來進(jìn)行評(píng)價(jià)不同方法排序所得結(jié)果的分辨率的指標(biāo)，即Monotonicity。在排序結(jié)果中，如果具有相同的排序值的節(jié)點(diǎn)的數(shù)量越少，那么排序結(jié)果的區(qū)分度和分辨率也就越高。Monotonicity指標(biāo)的定義如下：

其中，R通過排序算法得到的排序結(jié)果向量；nr表示在排序結(jié)果中具有相同排序值的節(jié)點(diǎn)的數(shù)目；n表示排序結(jié)果向量中所有元素的數(shù)量；M(R)表示的是在最終的排序結(jié)果中具有相同排序值的節(jié)點(diǎn)在總節(jié)點(diǎn)中所占的比例。如果M(R)的值為1，意味著排序結(jié)果中所有節(jié)點(diǎn)的排序值都不相同；如果M(R)的值為0，則說明所有節(jié)點(diǎn)具有相同的排序值。表4展示了degree、Ks值、MDD、EKsd四種度量方法的Monotonicity指標(biāo)值。

表4 不同度量方法的Monotonicity指標(biāo)值

通過對(duì)表4中的數(shù)據(jù)觀察可以發(fā)現(xiàn)，通過使用Ks值方法在3個(gè)網(wǎng)絡(luò)中進(jìn)行排序得到的結(jié)果分辨率最差，這是因?yàn)镵-shell方法得到的排序結(jié)果是一種粗粒度的劃分方法，導(dǎo)致最終結(jié)果中有大量的節(jié)點(diǎn)具有相同的排序值；degree指標(biāo)稍好于Ks值，但是degree指標(biāo)只考慮了節(jié)點(diǎn)的最局部信息，MDD方法的分辨率上有所提升，但是該方法存在參數(shù)的選擇的問題，不同的參數(shù)值對(duì)排序結(jié)果有較大的影響。EKsd值在不同的實(shí)驗(yàn)數(shù)據(jù)集上的排序結(jié)果都具有最高的分辨率。

3.2 正確性指標(biāo)

利用文獻(xiàn)[10]中介紹的τ指標(biāo)來對(duì)排序結(jié)果的正確性進(jìn)行驗(yàn)證。首先，使用經(jīng)典的SIR模型模擬網(wǎng)絡(luò)中的傳播過程，并按照節(jié)點(diǎn)的傳播效率對(duì)節(jié)點(diǎn)進(jìn)行排序，然后將不同排序方法得到的排序結(jié)果與SIR模型所得結(jié)果進(jìn)行對(duì)比，得到的不同排序結(jié)果之間的相關(guān)系數(shù)。排序相關(guān)系數(shù)τ的定義如下：

其中：r和σ分別表示通過不同的排序方法得到的排序結(jié)果；nc和nd分別表示通過不同排序方法得到的結(jié)果生成的所有的序列對(duì)(rn,σn)中，具有相同排列順序和不同排列順序的序列對(duì)的數(shù)量；n代表排序結(jié)果中元素的數(shù)量；τ表示的是通過不同的排序方法得到的排序結(jié)果之間的相似度。

分別將degree、Ks值、MDD和本文提出的EKsd值四種方法的排序結(jié)果與通過SIR模型得到的排序結(jié)果進(jìn)行比較，結(jié)果記錄在表5中。表中的第二行和第三行分別表示在SIR模型中進(jìn)行模擬時(shí)傳染概率的閾值和本文所選取的傳染概率，后面的各行分別是不同方法與SIR模型得到的傳染效率σ的排序相關(guān)系數(shù)值。

表5 不同度量方法的τ指標(biāo)值

從表5數(shù)據(jù)可以發(fā)現(xiàn)，根據(jù)EKsd值對(duì)節(jié)點(diǎn)進(jìn)行排序得到的排序結(jié)果與通過SIR模型得到的仿真結(jié)果更加接近，這是因?yàn)镋Ksd值不僅考慮了節(jié)點(diǎn)的全局特征，同時(shí)將節(jié)點(diǎn)的半局部信息融入進(jìn)來，從而提高了排序結(jié)果的正確性。

4 結(jié)語

針對(duì)傳統(tǒng)K-shell方法具有的缺陷，本文提出了一種新的節(jié)點(diǎn)重要性計(jì)算指標(biāo)EKsd，該指標(biāo)基于K-shell方法和節(jié)點(diǎn)的半局部信息，考慮了節(jié)點(diǎn)在K-shell分解過程中被刪除時(shí)的迭代層數(shù)，并綜合節(jié)點(diǎn)的半局部信息來對(duì)具有相同排序值的節(jié)點(diǎn)的重要性進(jìn)行進(jìn)一步的區(qū)分，從而獲得了具有更高的分辨率和準(zhǔn)確性的排序結(jié)果。最后，通過在三個(gè)真實(shí)的數(shù)據(jù)集上分別進(jìn)行分辨率和正確性的實(shí)驗(yàn)驗(yàn)證，驗(yàn)證了方法可以得到更好的排序結(jié)果。

本文綜合考慮了節(jié)點(diǎn)的全局特性和局部特性進(jìn)行節(jié)點(diǎn)重要性的排序，但是全局特性和局部特性在節(jié)點(diǎn)排序的結(jié)果分別具有何種程度的影響，目前尚沒有明確的結(jié)論，未來將從這方面出發(fā)進(jìn)行進(jìn)一步的研究。

參考文獻(xiàn)：

[1]劉建國(guó),任卓明,郭強(qiáng),等.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序的研究進(jìn)展[J].物理學(xué)報(bào),2013,62（17）:000001-10.

[2]李翔,劉宗華,汪秉宏.網(wǎng)絡(luò)傳播動(dòng)力學(xué)[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2010,07（2）:33-37.

[3]孫睿,羅萬伯.網(wǎng)絡(luò)輿論中節(jié)點(diǎn)重要性評(píng)估方法綜述[J].計(jì)算機(jī)應(yīng)用研究,2012,29（10）:3606-3608.

[4]Phillip Bonacich.Factoring andWeighting Approaches to Status Scores and Clique Identification[J].Journal of Mathematical Sociology,1972,2（1）:113-120.

[5]Freeman LC.Centrality in SocialNetworksConceptual Clarification[J].Social Networks,1978,1（3）:215-239.

[6]SabidussiG.The Centrality Index ofa Graph[J].Psychometrika,1966,31（4）:581-603.

[7]Katz L.ANew Status Index Derived from Sociometric Analysis[J].Psychometrika,1953,18（1）:39-43.

[8]任曉龍,呂琳媛.網(wǎng)絡(luò)重要節(jié)點(diǎn)排序方法綜述[J].科學(xué)通報(bào),2014（13）：1175-1197.

[9]Kitsak M,Gallos LK,Havlin S,etal.Identification of Influential Spreaders in Complex Networks[J].Nature Physics,2010,6（11）：888-893.

[10]Bae J,Kim S.Identifying and Ranking Influential Spreaders in Complex Networks by Neighborhood Coreness[J].Physica A Statistical Mechanics&Its Applications,2014,395（4）：549-559.

[11]Newman ME.Finding Community Structure in Networks Using the Eigenvectors of Matrices[J].Physical Review.E,Statistical,Nonlinear,and Soft Matter Physics,2006,74（3 Pt2）：036-104.

[12]Guimerà R,Danon L,Díaz-Guilera A,etal.Self-Similar Community Structure in a Network of Human Interactions[J].Physical Review EStatistical Nonlinear&Soft Matter Physics,2003,68（6Pt2）:065-103.

[13]Hu Q,Gao Y,Ma P,etal.A New Approach to Identify Influential Spreaders in Complex Networks[M].Web-Age Information Management.Springer Berlin Heidelberg,2013：99-104.