謝越

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

0 引言

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

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

1 相關(guān)工作

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

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

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

1.2 K-shell分解方法

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

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

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

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

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

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

表1 K-shell分解過程

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

表3 實驗數(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é)點之間的相互關(guān)系。

3.1 分辨率指標(biāo)

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

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

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

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

3.2 正確性指標(biāo)

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

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

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

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

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

4 結(jié)語

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

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

參考文獻(xiàn)：

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

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

[3]孫睿,羅萬伯.網(wǎng)絡(luò)輿論中節(jié)點重要性評估方法綜述[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é)點排序方法綜述[J].科學(xué)通報,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.