盧鵬麗, 周 庚

(蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院, 甘肅 蘭州 730050)

近年來(lái)，復(fù)雜網(wǎng)絡(luò)的研究在航空線路、電網(wǎng)、社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)、生態(tài)網(wǎng)絡(luò)等領(lǐng)域受到了廣泛的關(guān)注[1-6].網(wǎng)絡(luò)的無(wú)標(biāo)度特性[7]和小世界特性[8]使得網(wǎng)絡(luò)中的一些重要節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)和功能有很大影響.當(dāng)這些節(jié)點(diǎn)在網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，它們的影響將迅速擴(kuò)散到整個(gè)網(wǎng)絡(luò).因此，如何準(zhǔn)確量化復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性，找出關(guān)鍵節(jié)點(diǎn)，具有重要的理論和現(xiàn)實(shí)意義[9].例如，控制疾病網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)能有效防止病毒的大規(guī)模傳播[10]；社交網(wǎng)絡(luò)中控制關(guān)鍵節(jié)點(diǎn)將有助于阻止謠言的擴(kuò)散[11]；準(zhǔn)確找到電力網(wǎng)絡(luò)的重要節(jié)點(diǎn)，對(duì)其加以重點(diǎn)監(jiān)管和保護(hù)，可使得電力傳輸順利進(jìn)行，有效防止大面積停電事故的發(fā)生[12]；識(shí)別和控制交通網(wǎng)絡(luò)中的重要節(jié)點(diǎn)能有效解決交通擁堵的問(wèn)題.針對(duì)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的評(píng)價(jià)，學(xué)者們提出了度中心性(DC)[14]、 接近中心性(CC)[15]、介數(shù)中心性(BC)[16]、特征向量中心性(EC)[17]、子圖中心性(SC)[18]、譜密度中心性[19]和K-core中心性(KC)[20]等方法.

在信息論里，熵被用于表示事物的不確定性，熵值越大，表示可以傳遞的信息量越大.圖的熵首先由mowshowitz和Trucco引入，并被廣泛地用于描述網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).近年來(lái)，圖論學(xué)者對(duì)不同的信息熵函數(shù)進(jìn)行研究，發(fā)現(xiàn)圖熵可用來(lái)表示復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的中心性.傳統(tǒng)上，香農(nóng)熵(Shannon entropy)、馮諾依曼熵(von Neumann entropy)可用來(lái)分析網(wǎng)絡(luò)的整體統(tǒng)計(jì)特性，當(dāng)刪除網(wǎng)絡(luò)中的一條邊，網(wǎng)絡(luò)的熵會(huì)隨之減小.因此可以考慮在網(wǎng)絡(luò)中用刪除部分節(jié)點(diǎn)和與它相連的邊對(duì)整個(gè)網(wǎng)絡(luò)的熵的影響來(lái)反映節(jié)點(diǎn)的重要性，或者可以考慮在網(wǎng)絡(luò)中指定節(jié)點(diǎn)上添加邊，使得節(jié)點(diǎn)的度最大化，從而體現(xiàn)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性[21].Simmons等[22]發(fā)現(xiàn)馮諾依曼熵可以用來(lái)約束圖的泰爾指數(shù)，并提出一種基于圖的泰爾指數(shù)和馮諾依曼指數(shù)的節(jié)點(diǎn)重要性度量措施.Massimo等[23]引入距離熵作為復(fù)雜網(wǎng)絡(luò)中給定節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)之間路徑長(zhǎng)度分布均勻性的度量措施，并將距離熵與接近中心性耦合，提出一種基于距離熵的節(jié)點(diǎn)中心性度量措施.聶廷遠(yuǎn)等[24]提出了映射熵(ME)和局部熵(LE)兩種攻擊策略來(lái)識(shí)別復(fù)雜網(wǎng)絡(luò)中的重要節(jié)點(diǎn).

雖然已有的中心性準(zhǔn)則得到了廣泛的應(yīng)用，但也存在不足.度中心性DC和介數(shù)中心性BC都只考慮了節(jié)點(diǎn)vi的所有鄰居節(jié)點(diǎn)對(duì)節(jié)點(diǎn)自身的重要性的影響，并沒(méi)有考慮哪一部分鄰居節(jié)點(diǎn)集對(duì)節(jié)點(diǎn)vi自身的重要性影響更大.本文將節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集劃分成關(guān)聯(lián)鄰居節(jié)點(diǎn)集MR和非關(guān)聯(lián)鄰居節(jié)點(diǎn)集MUR，在此基礎(chǔ)上提出了關(guān)聯(lián)鄰居中心性RNC和非關(guān)聯(lián)鄰居中心性URNC.采用動(dòng)態(tài)攻擊的方式[25],通過(guò)在一種人工網(wǎng)絡(luò)和五種實(shí)際網(wǎng)絡(luò)上進(jìn)行仿真實(shí)驗(yàn).結(jié)果表明，與傳統(tǒng)的中心性準(zhǔn)則相比，新的中心性指標(biāo)RNC 能夠得到更準(zhǔn)確、更全面的結(jié)果.

1 相關(guān)研究和本文算法

1.1 相關(guān)研究

傳統(tǒng)的節(jié)點(diǎn)中心性問(wèn)題主要分為基于鄰居信息的節(jié)點(diǎn)中心性研究、基于經(jīng)過(guò)節(jié)點(diǎn)最短路徑數(shù)目的節(jié)點(diǎn)中心性研究和基于節(jié)點(diǎn)移除以及收縮的節(jié)點(diǎn)中心性研究[27].基于鄰接信息節(jié)點(diǎn)中心性研究主要關(guān)注的是網(wǎng)絡(luò)節(jié)點(diǎn)本身的信息及其鄰居節(jié)點(diǎn)的信息；基于經(jīng)過(guò)節(jié)點(diǎn)的最短路徑數(shù)目的節(jié)點(diǎn)中心性研究主要是考慮信息流在網(wǎng)絡(luò)中的傳播；基于節(jié)點(diǎn)的移除和收縮的節(jié)點(diǎn)中心性研究側(cè)重于研究節(jié)點(diǎn)刪除和收縮過(guò)程中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生的變化.

設(shè)網(wǎng)絡(luò)G=(V,E)，其中V={v1,v2,…,vN}為其節(jié)點(diǎn)集，E={e1,e2,…,eL}為其邊集，節(jié)點(diǎn)數(shù)為N，邊數(shù)為L(zhǎng)，di為節(jié)點(diǎn)vi的度.

1) 度中心性.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度中心性表示的是一個(gè)節(jié)點(diǎn)鄰居的個(gè)數(shù)占總節(jié)點(diǎn)數(shù)的比例，最直觀地認(rèn)為鄰居越多，節(jié)點(diǎn)就越重要.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度中心性定義為

DCi=di/(N-1)

(1)

2) 介數(shù)中心性.節(jié)點(diǎn)的介數(shù)中心性是指網(wǎng)絡(luò)中經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑的數(shù)目占該網(wǎng)絡(luò)中最短路徑總數(shù)的比例.節(jié)點(diǎn)v的介數(shù)中心性定義為

(2)

其中:δst(v)表示網(wǎng)絡(luò)中從任意節(jié)點(diǎn)s到節(jié)點(diǎn)t且經(jīng)過(guò)節(jié)點(diǎn)v的最短路徑的條數(shù);δst表示網(wǎng)絡(luò)中從任意節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑的條數(shù).

3) K-core中心性.節(jié)點(diǎn)的K-core中心性是根據(jù)節(jié)點(diǎn)的位置度量節(jié)點(diǎn)影響力.K-core分解算法通過(guò)迭代刪除節(jié)點(diǎn)，給網(wǎng)絡(luò)中所有節(jié)點(diǎn)賦予K-core值.算法思想如下：首先，從圖中刪除所有度為1的節(jié)點(diǎn)以及相關(guān)的連邊，若剩下的節(jié)點(diǎn)里，仍有度值為1的節(jié)點(diǎn)，則重復(fù)上述操作，直到圖中所有節(jié)點(diǎn)的度值都大于1，然后將所有刪除的節(jié)點(diǎn)的K-core值記為1,即這些節(jié)點(diǎn)均處于K-core值為1的層;其次,刪除度為2的節(jié)點(diǎn)，直到?jīng)]有度為2的節(jié)點(diǎn),然后將所有刪除的節(jié)點(diǎn)的K-core值記為2，這個(gè)過(guò)程一直持續(xù)到所有節(jié)點(diǎn)都刪除為止，即每個(gè)節(jié)點(diǎn)獨(dú)有對(duì)應(yīng)的K-core值.顯然，K-core值越大的節(jié)點(diǎn)越接近網(wǎng)絡(luò)的中心位置，節(jié)點(diǎn)影響力也就越大.

4) 特征向量中心性.節(jié)點(diǎn)vi的特征向量中心性是節(jié)點(diǎn)在網(wǎng)絡(luò)對(duì)應(yīng)的鄰接矩陣中主特征向量的第i個(gè)分量的值.特征向量中心性(eigenvector centrality,EC)被定義為

EC(vi)=αmax(vi)

(3)

其中:αmax是對(duì)應(yīng)于鄰接矩陣A的最大特征值的特征向量；αmax(vi)是特征向量對(duì)應(yīng)的第i個(gè)分量.

5) 基于熵的節(jié)點(diǎn)中心性.在復(fù)雜網(wǎng)絡(luò)中，為了便于計(jì)算，節(jié)點(diǎn)的重要性定義為

(4)

其中:ki代表一個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中的一些不變量，例如節(jié)點(diǎn)的度、節(jié)點(diǎn)的介數(shù)等，且0

圖(網(wǎng)絡(luò))的熵定義為

(5)

圖熵反映圖的整體特性，為了研究節(jié)點(diǎn)的特性，基于圖熵，學(xué)者們針對(duì)節(jié)點(diǎn)及鄰居節(jié)點(diǎn)構(gòu)成的子圖提出了局部熵和交叉熵，這為后來(lái)熵中心性指標(biāo)的研究奠定了堅(jiān)實(shí)的基礎(chǔ).局部熵(localEnt)和交叉熵(crosEnt)的節(jié)點(diǎn)重要性定義如下[28]：

(6)

(7)

其中:M表示節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集的大小;Ii是節(jié)點(diǎn)vi的重要性;Ij是節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)的重要性;局部熵localEnti是節(jié)點(diǎn)vi所有鄰接點(diǎn)的信息熵，即一個(gè)節(jié)點(diǎn)的重要性由其鄰居節(jié)點(diǎn)的信息反映；交叉熵crosEnti由節(jié)點(diǎn)vi及其鄰居節(jié)點(diǎn)的信息共同反映.

基于以上的研究基礎(chǔ)，Nie[24]提出了基于度中心性的局部熵(LE)和映射熵(ME)中心性：

(8)

(9)

其中:DCi為節(jié)點(diǎn)vi的度中心性;M為節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)集的大小;DCj為節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集M中的節(jié)點(diǎn)vj的度中心性.

1.2 基于鄰介熵和鄰度熵的復(fù)雜網(wǎng)絡(luò)中心性算法

復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度中心性表示的是一個(gè)節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)占節(jié)點(diǎn)總數(shù)的比例，相鄰節(jié)點(diǎn)越多，節(jié)點(diǎn)就越重要.節(jié)點(diǎn)vi的介數(shù)中心性是指網(wǎng)絡(luò)中經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑的數(shù)目占該網(wǎng)絡(luò)中最短路徑總數(shù)的比例，經(jīng)過(guò)節(jié)點(diǎn)vi的最短路徑一定經(jīng)過(guò)其鄰居節(jié)點(diǎn).然而度中心性和介數(shù)中心性都只考慮了節(jié)點(diǎn)vi的所有鄰居節(jié)點(diǎn)對(duì)其重要性的影響，并沒(méi)有考慮那一部分鄰居節(jié)點(diǎn)集對(duì)節(jié)點(diǎn)vi自身的重要性影響更大.

本文將節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集進(jìn)一步進(jìn)行劃分，將鄰居節(jié)點(diǎn)集劃分成關(guān)聯(lián)鄰居節(jié)點(diǎn)集MR(節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集中的節(jié)點(diǎn)vk彼此之間有邊的節(jié)點(diǎn)對(duì)組成的節(jié)點(diǎn)集稱之為關(guān)聯(lián)鄰居節(jié)點(diǎn)集)和無(wú)關(guān)聯(lián)鄰居節(jié)點(diǎn)集MUR(節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集中的節(jié)點(diǎn)vj彼此之間沒(méi)有邊的節(jié)點(diǎn)對(duì)組成的節(jié)點(diǎn)集稱之為無(wú)關(guān)聯(lián)鄰居節(jié)點(diǎn)集)，受局部熵中心性(LE)和映射熵中心性(ME)的啟發(fā)，通過(guò)計(jì)算節(jié)點(diǎn)vi自身的DC和BC及其關(guān)聯(lián)鄰居節(jié)點(diǎn)集MR和無(wú)關(guān)聯(lián)鄰居節(jié)點(diǎn)集MUR中各節(jié)點(diǎn)的DC和BC之和，提出了關(guān)聯(lián)鄰介熵NBER、非關(guān)聯(lián)鄰介熵NBEUR、關(guān)聯(lián)鄰度熵NDER和非關(guān)聯(lián)鄰度熵NDEUR.結(jié)合關(guān)聯(lián)鄰介熵NBCR和關(guān)聯(lián)鄰度熵NDCR提出了關(guān)聯(lián)鄰居中心性RNC.結(jié)合非關(guān)聯(lián)鄰介熵NBCUR和非關(guān)聯(lián)鄰度熵NDCUR提出了非關(guān)聯(lián)鄰居中心性URNC.關(guān)聯(lián)鄰介熵NBER、非關(guān)聯(lián)鄰介熵NBEUR、關(guān)聯(lián)鄰度熵NDER和非關(guān)聯(lián)鄰度熵NDEUR定義如下：

(10)

(11)

(12)

(13)

其中:DCi為節(jié)點(diǎn)vi的度中心性;BCi為節(jié)點(diǎn)vi的介數(shù)中心性;MR為節(jié)點(diǎn)vi關(guān)聯(lián)鄰居節(jié)點(diǎn)集;NMR為節(jié)點(diǎn)vi關(guān)聯(lián)鄰居節(jié)點(diǎn)集的節(jié)點(diǎn)個(gè)數(shù);MUR為節(jié)點(diǎn)vi非關(guān)聯(lián)鄰居節(jié)點(diǎn)集;NMUR為節(jié)點(diǎn)vi非關(guān)聯(lián)鄰居節(jié)點(diǎn)集的節(jié)點(diǎn)個(gè)數(shù).

關(guān)聯(lián)鄰居中心性RNC和非關(guān)聯(lián)鄰居中心性URNC定義如下：

2 實(shí)驗(yàn)及結(jié)果分析

本實(shí)驗(yàn)的實(shí)驗(yàn)平臺(tái)為聯(lián)想G500個(gè)人筆記本電腦，處理器為Corei5-3230，運(yùn)行內(nèi)存為8 G；軟件開(kāi)發(fā)平臺(tái)為MATLAB R2014 a.

2.1 實(shí)驗(yàn)數(shù)據(jù)

本文通過(guò)一種人工網(wǎng)絡(luò)模型和五種實(shí)際網(wǎng)絡(luò)模型進(jìn)行仿真實(shí)驗(yàn)，來(lái)評(píng)估新中心性度量措施的有效性.其中人工網(wǎng)絡(luò)為BA 無(wú)標(biāo)度網(wǎng)絡(luò)，是由Pajek軟件生成，生成參數(shù)設(shè)置如下：節(jié)點(diǎn)總數(shù)N=2 000，初始頂點(diǎn)數(shù)N0=10，初始連邊概率α=0.25.五種實(shí)際網(wǎng)絡(luò)分別為Air美國(guó)航空網(wǎng)絡(luò)、Authorship科學(xué)家協(xié)作網(wǎng)絡(luò)、Email 網(wǎng)絡(luò)、Stelzl 網(wǎng)絡(luò)和西部電網(wǎng)網(wǎng)絡(luò)[26]，網(wǎng)絡(luò)的部分參數(shù)見(jiàn)表1.

表1 六種網(wǎng)絡(luò)的部分參數(shù)特性

2.2 抗毀性測(cè)度

本文使用最大連通子圖的相對(duì)大小作為節(jié)點(diǎn)重要性評(píng)價(jià)標(biāo)準(zhǔn).連通子圖指的是存在于網(wǎng)絡(luò)的一個(gè)子圖，在這個(gè)子圖內(nèi)，任意兩個(gè)節(jié)點(diǎn)之間都至少存在一條簡(jiǎn)單路徑.對(duì)于非連通的圖，可以將其分解成兩個(gè)或者兩個(gè)以上的聯(lián)通分支.其中各連通分支中包含節(jié)點(diǎn)最多的分支稱為最大連通分支，也稱為最大連通子圖.網(wǎng)絡(luò)會(huì)隨著中心節(jié)點(diǎn)的移除而分裂成若干個(gè)不連通的子圖，其中最大連通子圖的節(jié)點(diǎn)個(gè)數(shù)和網(wǎng)絡(luò)的整體結(jié)構(gòu)密切相關(guān)，最大連通子圖的節(jié)點(diǎn)個(gè)數(shù)越少，就代表網(wǎng)絡(luò)被損毀得越嚴(yán)重.最大連通子圖相對(duì)大小被定義為

(16)

2.3 實(shí)驗(yàn)流程

本文以網(wǎng)絡(luò)最大連通子圖的相對(duì)大小作為復(fù)雜網(wǎng)絡(luò)抗毀性評(píng)價(jià)標(biāo)準(zhǔn)，全面地分析了新中心性度量措施排序效果.

Step1：使用Pajek軟件通過(guò)設(shè)置特定生成參數(shù)生成BA無(wú)標(biāo)度網(wǎng)絡(luò).net文件，并把BA無(wú)標(biāo)度網(wǎng)絡(luò)和其余五種實(shí)際網(wǎng)絡(luò)的.net文件在Matlab中進(jìn)行處理，生成對(duì)應(yīng)的鄰接矩陣.

Step2：計(jì)算六種實(shí)驗(yàn)網(wǎng)絡(luò)下各節(jié)點(diǎn)對(duì)應(yīng)的關(guān)聯(lián)鄰居中心性RNC(i)和非關(guān)聯(lián)鄰居中心性URNC(i)的值,并按照從大到小的順序依次排序.

Step3：根據(jù)上述排序結(jié)果每次刪除前20個(gè)節(jié)點(diǎn)，然后計(jì)算一次網(wǎng)絡(luò)的最大連通子圖的相對(duì)大小，重復(fù)上述操作，直到將網(wǎng)絡(luò)中所有節(jié)點(diǎn)都被刪除(當(dāng)網(wǎng)絡(luò)中剩余節(jié)點(diǎn)不足20 個(gè)時(shí)按照20個(gè)計(jì)算，并進(jìn)行一次刪除操作).最終將生成的最大連通子圖相對(duì)大小的序列進(jìn)行曲線擬合來(lái)反映各指標(biāo)的攻擊效果，并對(duì)比各網(wǎng)絡(luò)下關(guān)聯(lián)鄰居中心性RNC 和非關(guān)聯(lián)鄰居中心性URNC二者的效果，選出二者中攻擊效果最佳的攻擊方式用于后續(xù)的新中心性度量措施與傳統(tǒng)中心性度量措施對(duì)比實(shí)驗(yàn).

Step4：計(jì)算六種實(shí)驗(yàn)網(wǎng)絡(luò)下各節(jié)點(diǎn)對(duì)應(yīng)的介數(shù)中心性BC(i)、度中心性DC(i)、K-core中心性KC(i)、特征向量EC(i)的值，并按照從大到小順序依次排序.按照步驟Step3中刪除節(jié)點(diǎn)的方式生成對(duì)應(yīng)的最大連通子圖相對(duì)大小的序列，將Step3中篩選出的攻擊效果最佳的新指標(biāo)與上述五種傳統(tǒng)中心性指標(biāo)進(jìn)行對(duì)比實(shí)驗(yàn)，分析各指標(biāo)的攻擊效果.

Step5：算法結(jié)束.

2.4 關(guān)聯(lián)鄰居中心性RNC和非關(guān)聯(lián)鄰居中心性URNC對(duì)比實(shí)驗(yàn)結(jié)果分析

在這組實(shí)驗(yàn)中，將節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集劃分成關(guān)聯(lián)鄰居節(jié)點(diǎn)集和無(wú)關(guān)聯(lián)鄰居節(jié)點(diǎn)集，通過(guò)對(duì)比六種網(wǎng)絡(luò)模型在關(guān)聯(lián)鄰居中心性RNC和非關(guān)聯(lián)鄰居中心性URNC兩種指標(biāo)的攻擊效果(如圖1和表2所示)，分析新的攻擊策略對(duì)網(wǎng)絡(luò)的破壞性.

表2 利用RNC和URNC動(dòng)態(tài)攻擊時(shí)各網(wǎng)絡(luò)最先達(dá)到特定最大連通子圖相對(duì)大小的指標(biāo)

圖1表示的是關(guān)聯(lián)鄰居中心性RNC和非關(guān)聯(lián)鄰居中心性URNC動(dòng)態(tài)攻擊下的對(duì)比實(shí)驗(yàn).所謂的攻擊效果好就是在刪除同樣比例的節(jié)點(diǎn)后，剩余網(wǎng)絡(luò)的最大連通子圖的相對(duì)大小越小越好.

1) 從圖1a可看出，整個(gè)過(guò)程中關(guān)聯(lián)鄰居中心性RNC均比非關(guān)聯(lián)鄰居中心性URNC攻擊效果好.

圖1 RNC和URNC動(dòng)態(tài)攻擊效果對(duì)比Fig.1 RNC and URNC dynamic attack effect comparison

2) 在圖1b中，由于Authorship網(wǎng)絡(luò)的初始最大連通子圖相對(duì)大小是0.25，所以縱坐標(biāo)最高值為0.25.當(dāng)0.2

3) 從圖1c可以看出,非關(guān)聯(lián)鄰居中心性URNC明顯優(yōu)于關(guān)聯(lián)鄰居中心性RNC，由于BA無(wú)標(biāo)度網(wǎng)絡(luò)的生成過(guò)程中，新增節(jié)點(diǎn)優(yōu)先于度大的節(jié)點(diǎn)連接，因此，關(guān)聯(lián)鄰居節(jié)點(diǎn)集明顯小于非關(guān)聯(lián)鄰居節(jié)點(diǎn)集的大小，所以在動(dòng)態(tài)攻擊的情況下URNC攻擊效果明顯優(yōu)于RNC.

4) 從圖1d和圖1f中可以看出，當(dāng)0.8

5) 從圖1e可以看出，當(dāng)0.7

實(shí)驗(yàn)結(jié)果表明，在六個(gè)網(wǎng)絡(luò)中，關(guān)聯(lián)鄰居中心性RNC明顯優(yōu)于非關(guān)聯(lián)鄰居中心性URNC.

2.5 新組合中心性度量措施與傳統(tǒng)中心性度量措施對(duì)比實(shí)驗(yàn)結(jié)果分析

從表3和圖2可以看出：

表3 動(dòng)態(tài)攻擊下各網(wǎng)絡(luò)最先達(dá)到特定最大連通子圖相對(duì)大小的指標(biāo)

圖2 動(dòng)態(tài)攻擊下各網(wǎng)絡(luò)最先達(dá)到特定最大連通子圖相對(duì)大小的指標(biāo)

6) 在西部電網(wǎng)網(wǎng)絡(luò)中，RNC明顯優(yōu)于其他四種攻擊方式.

從表4可以看出：

表4 動(dòng)態(tài)攻擊下刪除一定比例節(jié)點(diǎn)后網(wǎng)絡(luò)的

1) 在Air網(wǎng)絡(luò)中，當(dāng)0.1

2) 在Authorship中，當(dāng)0.02

3) 在BA無(wú)標(biāo)度網(wǎng)絡(luò)中，當(dāng)0.3

4) 在Email網(wǎng)絡(luò)中，當(dāng)0.3

5) 在Stelzl網(wǎng)絡(luò)中，0.1

6) 當(dāng)0.1

2.6 各算法性能對(duì)比

從表5可以看出，相比于其他四種中心性算法，RNC和URNC的時(shí)間復(fù)雜度相對(duì)較高.從刻畫(huà)節(jié)點(diǎn)重要性的范圍以及適用的網(wǎng)絡(luò)范圍來(lái)看，RNC和URNC相比其他四種算法，能得到較全面、較精確的結(jié)果，且適用范圍更廣泛.

表5 各算法性能對(duì)比

3 結(jié)論

本文將節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集進(jìn)一步進(jìn)行劃分，將鄰居節(jié)點(diǎn)集劃分成關(guān)聯(lián)鄰居節(jié)點(diǎn)集和無(wú)關(guān)聯(lián)鄰居節(jié)點(diǎn)集，并基于圖熵的特性提出了新的節(jié)點(diǎn)中心性度量措施，即基于鄰介熵(NBE)和鄰度熵(NDE)的關(guān)聯(lián)鄰居中心性RNC和非關(guān)聯(lián)鄰居中心性URNC.實(shí)驗(yàn)結(jié)果表明，當(dāng)在動(dòng)態(tài)攻擊的方式下，新的中心性RNC度量措施在除BA無(wú)標(biāo)度網(wǎng)絡(luò)外的其他五種網(wǎng)絡(luò)上，明顯優(yōu)于其他傳統(tǒng)的節(jié)點(diǎn)中心性度量措施，而在BA無(wú)標(biāo)度網(wǎng)絡(luò)上，新的中心性URNC度量措施明顯優(yōu)于其他傳統(tǒng)的節(jié)點(diǎn)中心性度量措施.

總體而言，美國(guó)航空網(wǎng)絡(luò)、作家協(xié)作網(wǎng)、Email網(wǎng)絡(luò)、Stelzl網(wǎng)絡(luò)、美國(guó)西部電網(wǎng)網(wǎng)絡(luò)比演化網(wǎng)絡(luò)BA無(wú)標(biāo)度網(wǎng)絡(luò)模型更脆弱.關(guān)聯(lián)鄰居中心性RNC新的組合從節(jié)點(diǎn)鄰居和全局兩個(gè)方面考慮節(jié)點(diǎn)的中心性，在六個(gè)網(wǎng)絡(luò)中表現(xiàn)良好，相較于其他傳統(tǒng)節(jié)點(diǎn)中心性，新節(jié)點(diǎn)中心性指標(biāo)對(duì)節(jié)點(diǎn)重要性的刻畫(huà)更全面、更精確.