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

盧鵬麗, 周 庚

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

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

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

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

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

1.1 相關(guān)研究

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

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

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

DCi=di/(N-1)

(1)

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

(2)

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

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

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

EC(vi)=αmax(vi)

(3)

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

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

(4)

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

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

(5)

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

(6)

(7)

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

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

(8)

(9)

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

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

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

本文將節(jié)點vi的鄰居節(jié)點集進一步進行劃分，將鄰居節(jié)點集劃分成關(guān)聯(lián)鄰居節(jié)點集MR(節(jié)點vi的鄰居節(jié)點集中的節(jié)點vk彼此之間有邊的節(jié)點對組成的節(jié)點集稱之為關(guān)聯(lián)鄰居節(jié)點集)和無關(guān)聯(lián)鄰居節(jié)點集MUR(節(jié)點vi的鄰居節(jié)點集中的節(jié)點vj彼此之間沒有邊的節(jié)點對組成的節(jié)點集稱之為無關(guān)聯(lián)鄰居節(jié)點集)，受局部熵中心性(LE)和映射熵中心性(ME)的啟發(fā)，通過計算節(jié)點vi自身的DC和BC及其關(guān)聯(lián)鄰居節(jié)點集MR和無關(guān)聯(lián)鄰居節(jié)點集MUR中各節(jié)點的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é)點vi的度中心性;BCi為節(jié)點vi的介數(shù)中心性;MR為節(jié)點vi關(guān)聯(lián)鄰居節(jié)點集;NMR為節(jié)點vi關(guān)聯(lián)鄰居節(jié)點集的節(jié)點個數(shù);MUR為節(jié)點vi非關(guān)聯(lián)鄰居節(jié)點集;NMUR為節(jié)點vi非關(guān)聯(lián)鄰居節(jié)點集的節(jié)點個數(shù).

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

2 實驗及結(jié)果分析

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

2.1 實驗數(shù)據(jù)

本文通過一種人工網(wǎng)絡(luò)模型和五種實際網(wǎng)絡(luò)模型進行仿真實驗，來評估新中心性度量措施的有效性.其中人工網(wǎng)絡(luò)為BA 無標(biāo)度網(wǎng)絡(luò)，是由Pajek軟件生成，生成參數(shù)設(shè)置如下：節(jié)點總數(shù)N=2 000，初始頂點數(shù)N0=10，初始連邊概率α=0.25.五種實際網(wǎng)絡(luò)分別為Air美國航空網(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ù)見表1.

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

2.2 抗毀性測度

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

(16)

2.3 實驗流程

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

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

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

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

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

Step5：算法結(jié)束.

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

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

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

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

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

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

2) 在圖1b中，由于Authorship網(wǎng)絡(luò)的初始最大連通子圖相對大小是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無標(biāo)度網(wǎng)絡(luò)的生成過程中，新增節(jié)點優(yōu)先于度大的節(jié)點連接，因此，關(guān)聯(lián)鄰居節(jié)點集明顯小于非關(guān)聯(lián)鄰居節(jié)點集的大小，所以在動態(tài)攻擊的情況下URNC攻擊效果明顯優(yōu)于RNC.

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

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

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

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

從表3和圖2可以看出：

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

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

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

從表4可以看出：

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

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

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

3) 在BA無標(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 各算法性能對比

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

表5 各算法性能對比

3 結(jié)論

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

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