一種基于K-shell和半局部信息的節點重要性排序方法

謝越

（四川大學計算機學院，成都610065）

0 引言

隨著信息技術的快速發展，人類的社會活動在越來越多的方面表現出網絡化的特征。目前，我們的生活中已經充滿了各種各樣的網絡[1]，例如生物信息網絡、交通運輸網絡、電力系統網絡以及在最近幾年迅猛發展的在線社交網絡等。研究者們通過對各種不同類型的網絡進行統計分析，對這些網絡在傳播動力學等方面表現出來的特性有了更進一步的了解[2]。

近些年，網絡科學在信息技術的幫助下取得了快速發展，對網絡中的節點按重要性進行排序成為研究者們日益關注的問題。孫睿等[3]對在網絡輿論中對節點的重要性進行排序的研究現狀進行了介紹，并分別對基于網絡拓撲結構和基于節點屬性進行節點重要性排序的方法進行了總結。但是，近幾年有越來越多的研究者開始從更多新的角度對節點排序問題進行研究，例如Kitsak等人[4]于2010年首次提出了K-shell分解方法，并且通過該方法得到了比度指標、介數中心性等方法更為準確的排序結果，該方法的主要思想是認為節點的重要性取決于節點在網絡中所處的位置。這個方法提出后，受到了研究者們的廣泛關注，因此有必要對該方法進行更加深入和廣泛的研究。

1 相關工作

1.1 網絡的表示方法

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

多年以來，針對網絡中的節點排序問題，已經提出了許多的方法，如度中心性[4]、介數中心性[5]、接近中心性[6]和基于特征向量的中心性[7]方法。度中心性方法是一種簡單有效的局部性方法，忽略了網絡的全局結構；介數中心性和接近中心性方法能夠得到很好的排序結果，但是由于具有較高的計算復雜度，不能很好地應用到大規模網絡中。

1.2 K-shell分解方法

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

圖1為K-shell分解的示例[9]，圖中，節點6和節點12的擁有相同的度數，但是它們在網絡中處于不同的層。由此可以發現，單純使用節點的度來對節點進行排序，并不能十分準確地將節點排到正確的位置。

圖1 K-shell分解示例網絡

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

2 結合半局部信息的改進K-shell方法

對圖1的網絡進行K-shell分解，整個K-shell分解過程如表1所示：

表1 K-shell分解過程

從表1的數據中可以發現，節點2與節點6具有相同的Ks值，但是通過對圖1的網絡進行觀察可以發現，節點2與節點6對網絡產生的影響是不同的，這是由于K-shell方法的排序結果具有較低的分別率導致的。從表1的第一列中可以發現，節點2與節點6在不同的迭代層數中被刪除。因此將節點在刪除操作中的迭代層數融入到Ks值中，并結合節點的度，從而進一步區分相同Ks值的節點的重要性。

定義1：給定一個網絡G=（V,E），網絡中節點i的度記為d，Ks值記為k，刪去節點i時的迭代層數記為n，則融合節點的度和迭代層數的Ks值表示為：

對于圖1示例的網絡中的節點6來說，其Ks=1，n=3，d=4，因此 Ksd（6）=1*3+4=7；對于節點 2 來說，其Ks=1，n=1，d=1，因此 Ksd（2）=1*1+1=2?？梢园l現，通過將節點的度及刪除該節點時的迭代層數相融合，能夠得到更加準確的劃分結果。

Bae等人[10]同時考慮節點的度數與Ks值，認為如果一個節點位于網絡的中心位置，并且同時擁有較多的鄰居，那么這個節點也就能對網絡產生較大的影響。本文通過將Ksd值與節點的半局部信息進行結合，最終得到擴展的EKsd值。

定義2：給定一個網絡G=（V,E），網絡中節點i的Ksd值記為Ksd(i)，i的鄰居集合記為N(i)，則擴展的Eksd值表示為：

對圖1中的示例網絡分別使用不同的方法進行節點排序，所得的結果如表2所示。通過對表2進行觀察可以發現，單純的使用度指標和Ks值得到的排序結果，都會出現許多節點擁有相同的排序值的情況，而通過使用結合半局部信息和Ksd值的方法對節點進行排序，得到的結果則具有更高的區分度。使用EKsd值得到的排序結果之所以能夠得到更好的排序結果，是因為在該方法中同時使用了表現節點全局特征的Ksd值和表現節點局部特征的半局部信息。

表2 不同度量指標對示例網絡的排序結果

3 實驗結果與分析

本文選取degree、Ks值、MDD三個指標與EKsd值進行比較，通過實驗驗證EKsd值方法對節點進行排序的結果的效果。首先對EKsd值度量結果的分辨率進行測試，即測試在排序結果中是否出現大量節點具有相同度量值的情況；接著對EKsd值度量結果的正確性進行測試，將通過ESkd值度量排序的結果與通過SIR模型得到的結果相比較，如果所得結果與通過SIR模型得到的結果越相近，則說明排序結果的正確性越高。本文選取三個不同類型的現實網絡，通過進行實驗驗證所提方法的有效性。數據集的具體數據如表3所示。

表3 實驗數據集

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

3.1 分辨率指標

文獻[10]中提出了一種用來進行評價不同方法排序所得結果的分辨率的指標，即Monotonicity。在排序結果中，如果具有相同的排序值的節點的數量越少，那么排序結果的區分度和分辨率也就越高。Monotonicity指標的定義如下：

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

表4 不同度量方法的Monotonicity指標值

通過對表4中的數據觀察可以發現，通過使用Ks值方法在3個網絡中進行排序得到的結果分辨率最差，這是因為K-shell方法得到的排序結果是一種粗粒度的劃分方法，導致最終結果中有大量的節點具有相同的排序值；degree指標稍好于Ks值，但是degree指標只考慮了節點的最局部信息，MDD方法的分辨率上有所提升，但是該方法存在參數的選擇的問題，不同的參數值對排序結果有較大的影響。EKsd值在不同的實驗數據集上的排序結果都具有最高的分辨率。

3.2 正確性指標

利用文獻[10]中介紹的τ指標來對排序結果的正確性進行驗證。首先，使用經典的SIR模型模擬網絡中的傳播過程，并按照節點的傳播效率對節點進行排序，然后將不同排序方法得到的排序結果與SIR模型所得結果進行對比，得到的不同排序結果之間的相關系數。排序相關系數τ的定義如下：

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

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

表5 不同度量方法的τ指標值

從表5數據可以發現，根據EKsd值對節點進行排序得到的排序結果與通過SIR模型得到的仿真結果更加接近，這是因為EKsd值不僅考慮了節點的全局特征，同時將節點的半局部信息融入進來，從而提高了排序結果的正確性。

4 結語

針對傳統K-shell方法具有的缺陷，本文提出了一種新的節點重要性計算指標EKsd，該指標基于K-shell方法和節點的半局部信息，考慮了節點在K-shell分解過程中被刪除時的迭代層數，并綜合節點的半局部信息來對具有相同排序值的節點的重要性進行進一步的區分，從而獲得了具有更高的分辨率和準確性的排序結果。最后，通過在三個真實的數據集上分別進行分辨率和正確性的實驗驗證，驗證了方法可以得到更好的排序結果。

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

參考文獻：

[1]劉建國,任卓明,郭強,等.復雜網絡中節點重要性排序的研究進展[J].物理學報,2013,62（17）:000001-10.

[2]李翔,劉宗華,汪秉宏.網絡傳播動力學[J].復雜系統與復雜性科學,2010,07（2）:33-37.

[3]孫睿,羅萬伯.網絡輿論中節點重要性評估方法綜述[J].計算機應用研究,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]任曉龍,呂琳媛.網絡重要節點排序方法綜述[J].科學通報,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.