一種基于鄰居節點和邊的復雜網絡節點排序方法——NL中心性算法

劉書磊，杜家樂，邵增珍,3*

(1.山東師范大學，山東 濟南 250014；2.濟南市歷城一中，山東 濟南 250115；3.山東女子學院，山東 濟南 250002)

根據節點的影響力對節點排序是當前研究熱點之一，可應用于多個領域，如在有影響力個體的協助下提高信息在社交網絡中的傳播速度[1-2]、查找重要節點以避免級聯故障[3]、控制流行病的傳播[4]等。衡量節點影響力的關鍵是如何評估節點的傳播能力。

國內外學者對節點傳播能力的評估進行了大量研究，目前常用的方法有度中心性[5]、介數中心性[6]、緊密度中心性[7]、局部中心性[8]和k-核分解法[9]等。度中心性是最簡單的一種評估方法，該方法認為節點的傳播能力與其它連接的節點個數有關，即節點的鄰居節點越多，其傳播能力越強。該方法雖然簡單直觀，但只考慮了節點的局部屬性，因此具有一定的局限性。介數中心性和緊密度中心性是一種全局屬性，因其時間復雜度較大，所以這兩種方法都不能應用到大型的復雜網絡中。考慮到局部屬性缺乏準確性，而全局屬性的計算時間又較長，Chen等[8]提出了一種折中策略——局部中心性，該方法使用多層鄰居節點的個數描述節點的重要性，同時考慮計算時間和節點周圍的局部屬性。Kitsak等[9]發現越處于網絡中心的節點，其傳播效率越高。基于這種思想，提出了k-核分解法，但是k-核分解法會給傳播能力不同的節點賦予相同的ks值，導致該方法對節點重要性的區別度太小。Zeng等[10]對k-核分解法進行了改進，提出了進一步區分節點度的MDD算法。Wang等[11-12]根據k-核分解法中節點的迭代次數進一步提高了節點的區分度。

雖然上述中心性方法從不同的角度對節點的重要性進行了計算，但這些方法都忽略了網絡中另一個基本的元素：邊。節點的重要性除了與本身的位置、鄰居節點有關外，還應與其相連的邊有關。Wang[13]等認為在網絡中將邊認為同等重要是不合理的，提出給邊賦權值的思想，但他仍然依據節點的度對邊進行區分，沒有考慮邊在網絡中的重要性。Liu[14]認為邊的重要性可以通過其連接能力和不可替代性來描述，并在此基礎上提出了基于節點的度和連邊重要性的DIL方法，該方法將邊的重要性聚焦于其本身，從脫離節點的角度重新定義了邊的權值，但是該方法在對節點進行排序時，只考慮了節點的度，而沒有考慮節點的全局拓撲屬性。

基于以上研究，本文對DIL方法進行了改進，提出了一種基于鄰居節點和邊重要性的節點排序方法——NL中心性算法，該方法從節點周圍的局部結構和與其相連的邊的重要性兩個方面衡量節點的影響力。節點的局部結構被定義為以節點為中心，向外擴展3層鄰居節點的子圖結構。使用節點的局部結構不僅降低了計算復雜度，且更廣泛地考慮了網絡的全局拓撲屬性。節點和邊是復雜網絡的兩個基本屬性，節點的影響力必然與其相連的邊存在一定的關系。因此，本文在對節點的重要性進行排序時還考慮到了邊對節點的影響。為了驗證排序結果的準確性，將所提方法和其他中心性方法計算得到的排序結果與SIR傳播模型得到的排序結果進行對比，結果表明無論是計算效率還是準確性，NL中心性算法都要優于其他中心性方法。

1 中心性方法簡述

本文中提到的復雜網絡均指無向并且邊沒有權值的復雜網絡。定義G=(V,E)為復雜網絡，其中V表示節點集合，n=|V|為節點個數，E為邊的集合，m=|E|為邊的條數。網絡G的鄰接矩陣定義為A={auv}∈Rn,n，若節點u和節點v直接相連，則auv=1，否則auv=0。

度中心性定義為一個節點的鄰居節點的個數。一個節點的度越大，則說明該節點能夠直接影響的鄰居節點也就越多。用CD(v)表示節點v的度中心性，CD(v)定義為：

(1)

式中，Г(v)表示節點v的鄰居節點集合，|Г(v)|表示集合Г(v)的大小。

節點v的緊密度中心性CC(v)是節點v到其余所有節點最短路徑長度之和的倒數。節點的緊密度越大，則其與其他節點的連接越緊密，從而說明該節點在網絡中所在的位置越重要。CC(v)定義為：

(2)

式中，duv表示節點u和節點v的最短路徑長度，V/v表示除節點v之外其余節點集合。

局部中心性是介于度中心性和全局中心性的一種折中策略，不僅考慮了鄰居節點，還考慮了次鄰居節點，表示為CL(v)。若將節點v看做是第0層，局部中心性考慮了以節點v為中心，4層之內的所有節點的度。局部中心性越大，表示以節點v為中心的局部結構越龐大，從而節點v越重要。CL(v)定義如下：

(3)

式中，N(w)表示節點w鄰居節點和次鄰居節點的個數。

k-核分解法給每個節點標記一個整數或者說層數，表示節點的重要性程度。ks值越大說明節點越處于網絡的中心，也就越重要；ks值越小說明節點越處于網絡的邊緣。k-核分解法一開始先刪除網絡中所有度為1的節點，這些節點刪除后，若網絡中出現了新的度為1的節點，則繼續刪除這些節點，直到網絡中沒有度小于等于1的節點，所有刪除的這些節點的ks值為1。然后重復上述的步驟，直到網絡中所有的節點都被賦值。

2 考慮鄰居節點和邊重要性的NL中心性算法

2.1 DIL及其存在的問題

DIL是一種較為新穎的中心性方法。在計算節點的影響力時，該算法不僅考慮了節點的度還考慮了邊的重要性。首先定義邊euv的重要性度量指標Ieuv:

(4)

(5)

DIL中心性將邊的重要性加入到計算節點影響力的過程中，對節點的重要性具有較高的識別率，但DIL中心性在除去邊的貢獻值之外只考慮了節點的度，并未考慮全局拓撲屬性對節點重要性的影響。以圖1a、b兩個簡單網絡為例，說明DIL中心性的缺陷。

圖1 簡單網絡Fig.1 Simple network

使用DIL中心性計算圖1a中的節點重要性時，CDIL(v7)=CDIL(v11)=CDIL(v12)=CDIL(v13)=…=CDIL(v24)=CDIL(v27)=1，可以發現DIL中心性認為網絡中所有度為1的節點的重要性相同。造成這種情況的原因是所有與度為1的節點相連的邊不能和其他邊組成三角形，因此邊的重要性為0，從而使計算結果等于節點的度。也就是說，邊的重要性為0時，DIL還是只考慮了節點的度，這就會造成使用DIL中心性對網絡中節點進行排序時，所有度為1的節點的排序結果相等。從圖1a中可以看出，v4節點連接了左右兩個子圖，那么與v4相連的節點v25也就比較重要，但是DIL中心性認為v25和其他度為1的節點同等重要，這顯然是不合理的。

使用DIL中心性計算圖1b中的節點重要性時，CDIL(v7)=7.4，CDIL(v10)=7.4，CDIL(v7)=CDIL(v10)，說明節點v7和v10同等重要。但是從圖1b的結構中可以看出，刪除節點v7后，圖1b被分割成3個子圖：和節點v6相連的子圖、和節點v9相連的子圖和節點v8。刪除節點v10后，圖1b被分割成2個子圖：節點v11和剩余節點組成的子圖。刪除節點v6后對圖的連通性的破壞比刪除節點v10后對圖的連通性的破壞要大，說明節點v6比節點v10重要，這與DIL算法得到的結論相悖。綜上所述，DIL中心性有兩個缺陷：對網絡中所有度為1的節點的排序結果相同，忽略了網絡的全局拓撲屬性，從而導致邊對節點的貢獻值相等時，排序結果完全依賴于節點的度。

2.2 NL中心性算法

針對以上問題，本文對DIL中心性進行了改進，提出一種基于鄰居節點和邊重要性(Neighbor nodes and importance of Lines)的計算方法——NL中心性(CNL(v))。CNL(v)具體定義如下：

(6)

公式(6)和公式(5)相比，NL中心性將DIL算法中節點的度替換為節點的局部結構，節點的局部結構是介于度中心性和全局中心性的一種折中策略，是以節點為中心向外擴展3層的子圖結構。NL中心性認為，節點的重要性不僅與其相連的節點的個數有關，還應該與周圍的拓撲結構有關，因此使用節點周圍的子圖表示節點的拓撲屬性。使用節點的局部結構代替全局屬性，不需要知道整個網絡的結構，在減小時間復雜度的同時保證算法的準確性。

以圖1b為例，計算v7節點和v10節點的重要性時，DIL中心性只考慮了節點的度，因為CD(v7)=CD(v10)，v7節點和v10節點的邊的重要性又恰巧相同，所以CDIL(v7)=CDIL(v10)。雖然節點v7和節點v10的度相同，但是與v7相連的v6相比于與v10相連的v12連接了更大的子圖，所以v7節點更加重要。在使用NL中心性計算v7節點和v10節點的重要性時，因為考慮了以v7為中心的3層子圖結構，所以節點v6的鄰居節點和次鄰居節點個數也在計算范圍之內，從而對節點v7和節點v10的重要性做了進一步區分。具體計算結果為CNL(v7)=18.4，CNL(v10)=17.4，CNL(v7)>CNL(v10)，與分析結果一致。再以圖1a中節點v26和節點v27為例，CDIL(v26)=CDIL(v27)=1，CNL(v26)=18>CDIL(v27)=10，從而說明相比于DIL中心性，NL中心性能對節點重要性做出更加精確地區分。

使用DIL中心性計算節點重要性時，只考慮了節點的度和邊的重要性，所以時間復雜度為O(n)。NL中心性在計算時，考慮了3層子圖的節點的度，相比于DIL中心性，計算步驟只是成倍數增加而不是成指數增加，所以NL中心性的時間復雜度與DIL中心性的時間復雜度相等，仍為O(n)。

為了驗證NL中心性的準確度，本文實驗將NL中心性和其他已有中心性計算得到的排序結果和傳播模型得到的排序結果進行比較，使用肯德爾相關系數描述排序結果的擬合程度，進一步比較所提方法的準確率。

3 實驗

3.1 數據集

為了評價本文所提方法的準確性，把NL中心性應用到2個真實的復雜網絡中。這2個真實的網絡分別為：(1)海豚關系網絡[15]。這是在新西蘭神奇灣觀察到的62只海豚的社團關系圖。(2)單詞鄰接網絡[16]。這是由19世紀英國作家查爾斯·狄更斯創作的小說《大衛·科波菲爾》中的普通名詞和形容詞鄰接的無向網絡，節點代表名詞或形容詞，邊出現在相鄰位置的兩個單詞。在實驗過程中，以上2個真實網絡均看作無向網絡。

3.2 傳播模型

在傳染病動力學中，主要沿用由Kermack與McKendrick在1927年用動力學方法建立的SIR傳染病模型[17]。在某一時刻，所有節點只能處于易感者(susceptibles)-染病者(infectives)-恢復者(recovered)3種狀態之一。在SIR模型中，網絡初始狀態時只有一個節點處于染病者狀態(I)，其余所有節點處于易感者狀態(S)。在傳播過程中，一個病人能傳染的易感者數目與此環境內易感者總數成正比，比例系數β也稱為傳播系數；從染病者中移出的人數與染病者數量成正比，比例系數為γ，論文中設置γ=1。單位時間內，易感者以概率β變為染病者，染病者以概率γ變為恢復者。一個節點的傳播能力即為該節點在傳播過程中可以感染的節點數。本文實驗取100次傳播過程的平均值作為節點的傳播能力。

本文實驗將SIR傳播模型得到的排序結果與各中心性計算得到的排序結果進行比較，中心性方法計算得到的結果越接近于SIR傳播模型得到的排序結果，說明該中心性方法的準確性越高。

3.3 評價指標

肯德爾相關系數[18]是一個用來測量兩個隨機變量相關性的統計值，并經常用希臘字母τ表示其值。肯德爾相關系數的取值范圍在-1到1之間，當τ為1時，表示2個隨機變量擁有一致的等級相關性；當τ為-1時，表示2個隨機變量擁有完全相反的等級相關性；當τ為0時，表示2個隨機變量是相互獨立的。

假設2個集合分別為X、Y，其元素個數均為N。2個集合取的第i(1≤i≤N)個值分別用xi、yi表示。X與Y中的對應元素組成一個元素對集合XY，其包含的元素為(xi,yi)。當集合XY中任意2個元素(xi,yi)與(xj,yj)的排行相同時(當xi>xj時yi>yj，或者當xixj時yiyj，這2個元素被認為是不和諧對。當出現xi=xj或者yi=yj時，這2個元素既不是和諧對的也不是不和諧對。

肯德爾相關系數用于評價2個排序結果的相關程度，2個排序結果一個是通過SIR模型計算得到的結果，一個是通過中心性計算得到的排序結果。肯德爾相關系數越大說明中心性計算得到的排序結果越接近于傳播模型得到的排序結果，從而說明中心性方法越準確。肯德爾相關系數定義如下：

(7)

式中，nc表示和諧對的個數，nd表示不和諧對的個數。使用肯德爾系數計算傳播過程得到的排序結果和中心性計算得到的排序結果的相關性可以評價排序結果的準確性。

3.4 結果分析

在實驗過程中使用CD表示度中心性，Ck表示k-核分解法，CC表示緊密度中心性，CL表示局部中心性，CDIL表示DIL中心性，CNL表示NL中心性算法。為了從減少傳播系數對實驗結果的影響， SIR傳播模型中傳播系數的取值設置為從0.01到0.2。將中心性計算得到的結果和通過傳播模型得到的結果進行相關性比較，并計算肯德爾相關系數，實驗結果如圖2所示。

圖2 排序結果相關性比較Fig.2 The correlation comparison of ranking results

圖2a是將各中心性方法和傳播模型應用到海豚關系網絡中得到肯德爾相關系數，圖2b是將各中心性方法和傳播模型應用到單詞鄰接網絡中得到的肯德爾相關系數，橫坐標β表示傳播系數，縱坐標τ表示肯德爾相關系數。

在圖2a中可以看出，當傳播系數小于0.07時，度中心性具有最高的準確性；當傳播系數大于0.07時，NL中心性具有較高的準確性。造成這種情況的原因是當傳播系數較小時，每個感染者節點只能以較小的概率感染易感染者，從而整個網絡的傳播效率較低，網絡中被感染的節點數很少。度越大的節點越有更多的機會造成大的影響范圍，因此當傳播系數較小時，節點的影響力取決于其鄰居節點的個數，也就是節點的度。因為DIL中心性在計算節點的重要性時也考慮了節點的度，所以在圖2a中，傳播系數小于0.05時，DIL中心性的排序結果要好于NL中心性；但是當傳播系數大于0.05時，NL中心性的排序結果要好于DIL中心性。從圖2a中也可以看出，當傳播系數小于0.04時，度中心性具有最高的準確性；當傳播系數小于0.03時，DIL中心性的排序結果要好于NL中心性。

圖2a中，當傳播系數大于0.07時，NL中心性的肯德爾相關系數最大。圖2b中，當傳播系數大于0.04時，NL中心性的肯德爾相關系數最大，說明相比于其他中心性方法，NL中心性能夠更準確地對節點進行排序。同時，在圖2的2個圖中也可以看出，k-核分解法的肯德爾相關系數最小，說明k-核分解法對節點重要程度的識別度最低。這是因為k-核分解法給很多節點賦予了相同的ks值，從而不能對這些節點的重要性做進一步的區分。

4 結語

本文提出了一種基于鄰居節點和邊重要性的多屬性節點排序方法——NL中心性算法，該方法從節點周圍的子圖結構和與其相連的邊的重要性這兩個方面衡量節點的影響力，在控制時間復雜度的同時還考慮了節點的全局拓撲屬性。為了驗證所提方法的準確性，將其應用到兩個真實的復雜網絡中，并且使用SIR傳播模型模擬傳播過程，然后使用肯德爾相關系數描述中心性算法計算得到的排序結果和傳播模型得到的排序結果的擬合程度，最后通過比較結果發現，在兩個真實網絡中，本文所提方法的準確率都要高于DIL中心性算法，從而說明NL中心性算法可以更準確地找出影響能力大的節點，相比于其他方法可以得到更加精確的排序結果。但是NL中心性算法認為鄰居節點和連邊對節點重要性的貢獻是一樣的，沒有進一步區分二者的權值。如何給這兩個屬性賦予合適的權值，是我們下一步的研究方向。