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

劉書(shū)磊，杜家樂(lè)，邵增珍,3*

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

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

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

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

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

1 中心性方法簡(jiǎn)述

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

2.1 DIL及其存在的問(wèn)題

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

(4)

(5)

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

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

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

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

2.2 NL中心性算法

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

(6)

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

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

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

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

3 實(shí)驗(yàn)

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

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

3.2 傳播模型

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

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

3.3 評(píng)價(jià)指標(biāo)

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

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

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

(7)

式中，nc表示和諧對(duì)的個(gè)數(shù)，nd表示不和諧對(duì)的個(gè)數(shù)。使用肯德?tīng)栂禂?shù)計(jì)算傳播過(guò)程得到的排序結(jié)果和中心性計(jì)算得到的排序結(jié)果的相關(guān)性可以評(píng)價(jià)排序結(jié)果的準(zhǔn)確性。

3.4 結(jié)果分析

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

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

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

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

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

4 結(jié)語(yǔ)

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