一種基于鄰居節(jié)點和邊的復(fù)雜網(wǎng)絡(luò)節(jié)點排序方法——NL中心性算法

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

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

根據(jù)節(jié)點的影響力對節(jié)點排序是當(dāng)前研究熱點之一，可應(yīng)用于多個領(lǐng)域，如在有影響力個體的協(xié)助下提高信息在社交網(wǎng)絡(luò)中的傳播速度[1-2]、查找重要節(jié)點以避免級聯(lián)故障[3]、控制流行病的傳播[4]等。衡量節(jié)點影響力的關(guān)鍵是如何評估節(jié)點的傳播能力。

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

雖然上述中心性方法從不同的角度對節(jié)點的重要性進(jìn)行了計算，但這些方法都忽略了網(wǎng)絡(luò)中另一個基本的元素：邊。節(jié)點的重要性除了與本身的位置、鄰居節(jié)點有關(guān)外，還應(yīng)與其相連的邊有關(guān)。Wang[13]等認(rèn)為在網(wǎng)絡(luò)中將邊認(rèn)為同等重要是不合理的，提出給邊賦權(quán)值的思想，但他仍然依據(jù)節(jié)點的度對邊進(jìn)行區(qū)分，沒有考慮邊在網(wǎng)絡(luò)中的重要性。Liu[14]認(rèn)為邊的重要性可以通過其連接能力和不可替代性來描述，并在此基礎(chǔ)上提出了基于節(jié)點的度和連邊重要性的DIL方法，該方法將邊的重要性聚焦于其本身，從脫離節(jié)點的角度重新定義了邊的權(quán)值，但是該方法在對節(jié)點進(jìn)行排序時，只考慮了節(jié)點的度，而沒有考慮節(jié)點的全局拓?fù)鋵傩浴?/p>

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

1 中心性方法簡述

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

2.1 DIL及其存在的問題

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

(4)

(5)

DIL中心性將邊的重要性加入到計算節(jié)點影響力的過程中，對節(jié)點的重要性具有較高的識別率，但DIL中心性在除去邊的貢獻(xiàn)值之外只考慮了節(jié)點的度，并未考慮全局拓?fù)鋵傩詫?jié)點重要性的影響。以圖1a、b兩個簡單網(wǎng)絡(luò)為例，說明DIL中心性的缺陷。

圖1 簡單網(wǎng)絡(luò)Fig.1 Simple network

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

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

2.2 NL中心性算法

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

(6)

公式(6)和公式(5)相比，NL中心性將DIL算法中節(jié)點的度替換為節(jié)點的局部結(jié)構(gòu)，節(jié)點的局部結(jié)構(gòu)是介于度中心性和全局中心性的一種折中策略，是以節(jié)點為中心向外擴(kuò)展3層的子圖結(jié)構(gòu)。NL中心性認(rèn)為，節(jié)點的重要性不僅與其相連的節(jié)點的個數(shù)有關(guān)，還應(yīng)該與周圍的拓?fù)浣Y(jié)構(gòu)有關(guān)，因此使用節(jié)點周圍的子圖表示節(jié)點的拓?fù)鋵傩?。使用?jié)點的局部結(jié)構(gòu)代替全局屬性，不需要知道整個網(wǎng)絡(luò)的結(jié)構(gòu)，在減小時間復(fù)雜度的同時保證算法的準(zhǔn)確性。

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

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

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

3 實驗

3.1 數(shù)據(jù)集

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

3.2 傳播模型

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

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

3.3 評價指標(biāo)

肯德爾相關(guān)系數(shù)[18]是一個用來測量兩個隨機(jī)變量相關(guān)性的統(tǒng)計值，并經(jīng)常用希臘字母τ表示其值?？系聽栂嚓P(guān)系數(shù)的取值范圍在-1到1之間，當(dāng)τ為1時，表示2個隨機(jī)變量擁有一致的等級相關(guān)性；當(dāng)τ為-1時，表示2個隨機(jī)變量擁有完全相反的等級相關(guān)性；當(dāng)τ為0時，表示2個隨機(jī)變量是相互獨立的。

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

肯德爾相關(guān)系數(shù)用于評價2個排序結(jié)果的相關(guān)程度，2個排序結(jié)果一個是通過SIR模型計算得到的結(jié)果，一個是通過中心性計算得到的排序結(jié)果?？系聽栂嚓P(guān)系數(shù)越大說明中心性計算得到的排序結(jié)果越接近于傳播模型得到的排序結(jié)果，從而說明中心性方法越準(zhǔn)確?？系聽栂嚓P(guān)系數(shù)定義如下：

(7)

式中，nc表示和諧對的個數(shù)，nd表示不和諧對的個數(shù)。使用肯德爾系數(shù)計算傳播過程得到的排序結(jié)果和中心性計算得到的排序結(jié)果的相關(guān)性可以評價排序結(jié)果的準(zhǔn)確性。

3.4 結(jié)果分析

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

圖2 排序結(jié)果相關(guān)性比較Fig.2 The correlation comparison of ranking results

圖2a是將各中心性方法和傳播模型應(yīng)用到海豚關(guān)系網(wǎng)絡(luò)中得到肯德爾相關(guān)系數(shù)，圖2b是將各中心性方法和傳播模型應(yīng)用到單詞鄰接網(wǎng)絡(luò)中得到的肯德爾相關(guān)系數(shù)，橫坐標(biāo)β表示傳播系數(shù)，縱坐標(biāo)τ表示肯德爾相關(guān)系數(shù)。

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

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

4 結(jié)語

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