基于交叉熵的節(jié)點(diǎn)重要性排序算法

龔志豪，蔣 沅，代冀陽，楊智翔

(南昌航空大學(xué)信息工程學(xué)院 南昌 330063)

隨著網(wǎng)絡(luò)科學(xué)的發(fā)展與進(jìn)步，復(fù)雜系統(tǒng)已深入人類社會(huì)的各個(gè)領(lǐng)域，復(fù)雜網(wǎng)絡(luò)作為刻畫復(fù)雜系統(tǒng)的工具，在生態(tài)、社會(huì)、經(jīng)濟(jì)、交通等諸多系統(tǒng)中有著重要影響[1-2]。關(guān)鍵節(jié)點(diǎn)影響著網(wǎng)絡(luò)的結(jié)構(gòu)和信息傳遞功能，評(píng)估關(guān)鍵節(jié)點(diǎn)是復(fù)雜網(wǎng)絡(luò)的研究熱點(diǎn)[3-4]。一方面，快速準(zhǔn)確地識(shí)別出關(guān)鍵節(jié)點(diǎn)并提供保護(hù)機(jī)制可提升網(wǎng)絡(luò)的抗毀性[5]。另一方面，基于關(guān)鍵節(jié)點(diǎn)也可以提出更高效的攻擊策略[6-7]。因此，設(shè)計(jì)高效的關(guān)鍵節(jié)點(diǎn)評(píng)估算法具有重要的理論和實(shí)踐意義。

近年來，研究人員關(guān)于識(shí)別關(guān)鍵節(jié)點(diǎn)已有許多研究成果，經(jīng)典的評(píng)估算法有基于節(jié)點(diǎn)鄰近信息的度中心性[8]、基于最短路徑數(shù)目的介數(shù)中心性[9]、基于平均距離的接近中心性[10]以及基于網(wǎng)絡(luò)位置的K-殼分解法[11]等。其中度中心性雖然簡(jiǎn)單直接，但對(duì)鄰居節(jié)點(diǎn)的重要性區(qū)分度較低，并且考慮的鄰近信息有限，因此評(píng)估的精確性不高。介數(shù)和接近中心性僅考慮信息在最短路徑上傳播，而實(shí)際上傳播可能基于其他可達(dá)路徑，此外基于路徑的算法時(shí)間復(fù)雜度較高，不適用于大型網(wǎng)絡(luò)。而具有較低時(shí)間復(fù)雜度的K-殼分解法認(rèn)為節(jié)點(diǎn)重要性取決于所處網(wǎng)絡(luò)的位置，內(nèi)核層節(jié)點(diǎn)的重要性高于邊緣的節(jié)點(diǎn)，但對(duì)同一殼層的節(jié)點(diǎn)卻無法進(jìn)一步區(qū)分其重要性差異，并且節(jié)點(diǎn)在剝離時(shí)會(huì)對(duì)網(wǎng)絡(luò)的整體結(jié)構(gòu)信息造成破壞[12]。為彌補(bǔ)經(jīng)典算法評(píng)估的局限性，文獻(xiàn)[13]考慮節(jié)點(diǎn)與其相鄰節(jié)點(diǎn)之間的相關(guān)性，提出了映射熵來評(píng)估網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。文獻(xiàn)[14]通過衡量節(jié)點(diǎn)的局部拓?fù)渲睾隙葋砜坍嫻?jié)點(diǎn)間的相似性，提出了鄰域相似度算法用于評(píng)估節(jié)點(diǎn)的重要性。文獻(xiàn)[15]結(jié)合節(jié)點(diǎn)的K-殼以及信息熵，根據(jù)其分層大小依次進(jìn)行迭代，可區(qū)分內(nèi)層殼與外層殼中的節(jié)點(diǎn)重要性。文獻(xiàn)[16]受引力公式啟發(fā)，將節(jié)點(diǎn)的度值作為質(zhì)量，并將最短路徑長(zhǎng)度作為距離，考慮了節(jié)點(diǎn)的近鄰以及路徑信息，提出了引力模型算法。文獻(xiàn)[17]考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置，提出了一種基于K-殼分解法的改進(jìn)引力模型算法。

熵[18]可用于定量描述信息量的大小，當(dāng)使用熵理論刻畫復(fù)雜網(wǎng)絡(luò)時(shí)，信息熵可表征節(jié)點(diǎn)的局部重要性，因此，可考慮用子網(wǎng)絡(luò)的熵來表征網(wǎng)絡(luò)整體結(jié)構(gòu)的特性。如文獻(xiàn)[19]提出了信息熵來評(píng)估復(fù)雜系統(tǒng)的結(jié)構(gòu)特征，取得了較好的成效。文獻(xiàn)[20]改進(jìn)了K-殼值對(duì)信息熵的計(jì)算，提出了一種結(jié)合節(jié)點(diǎn)信息熵與迭代因子的算法。文獻(xiàn)[21]基于非廣延統(tǒng)計(jì)力學(xué)，提出了一種局部結(jié)構(gòu)熵來量化復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。文獻(xiàn)[22]結(jié)合網(wǎng)格約束系數(shù)以及節(jié)點(diǎn)的K-殼中心性，基于Tsallis 熵提出了一種節(jié)點(diǎn)重要性識(shí)別方法。

受上述研究啟發(fā)，本文提出了一種基于交叉熵的節(jié)點(diǎn)重要性識(shí)別算法CE+（cross entropy），該方法充分考慮了節(jié)點(diǎn)自身以及其周圍節(jié)點(diǎn)信息的整體重要性，CE+的值反映了節(jié)點(diǎn)與其近鄰節(jié)點(diǎn)之間的差異性，并且該算法時(shí)間復(fù)雜度僅為O(n)，適用于大型網(wǎng)絡(luò)。通過在8 個(gè)不同領(lǐng)域的真實(shí)網(wǎng)絡(luò)上進(jìn)行蓄意攻擊實(shí)驗(yàn)，并選用7 種不同的節(jié)點(diǎn)重要性排序算法作為對(duì)比，采用單調(diào)性指標(biāo)[23]、極大連通系數(shù)[24]、網(wǎng)絡(luò)效率[25-26]以及SIR 模型[27]等指標(biāo)驗(yàn)證了本文所提出CE+算法的有效性和適用性。

1 理論基礎(chǔ)

假設(shè)無向未加權(quán)的網(wǎng)絡(luò)G=(V,E)， 其中V是網(wǎng)絡(luò)G的節(jié)點(diǎn)集合， |V|=n，E是網(wǎng)絡(luò)的邊集合，|E|=m。A=(ai j)n×n通常表示網(wǎng)絡(luò)的鄰接矩陣，若節(jié)點(diǎn)i與 節(jié)點(diǎn)j相連，則ai j=1， 否則ai j=0。

1.1 度中心性

度中心性[9]是度量重要節(jié)點(diǎn)性能最基礎(chǔ)的指標(biāo)，節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)越多，則自身的影響力越大，其定義為：

1.2 介數(shù)中心性

當(dāng)網(wǎng)絡(luò)中某一節(jié)點(diǎn)i存在于其他節(jié)點(diǎn)之間的最短路徑上并且次數(shù)越多時(shí)，則說明節(jié)點(diǎn)i的關(guān)鍵程度越高，其定義為：

1.3 映射熵

文獻(xiàn)[13]考慮節(jié)點(diǎn)中所有鄰域相關(guān)的局部信息，提出了映射熵來評(píng)估復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)中心性，定義為：

式中，M是節(jié)點(diǎn)i的 鄰居集； D Cj是其相鄰節(jié)點(diǎn)之一的度中心性。

1.4 鄰域相似度

文獻(xiàn)[14]綜合考慮了節(jié)點(diǎn)的度值和鄰居節(jié)點(diǎn)的拓?fù)渲睾隙龋岢隽艘环N基于鄰域相似度的評(píng)估算法，定義為：

式中，n(i)為 節(jié)點(diǎn)i的 鄰居節(jié)點(diǎn)；若節(jié)點(diǎn)b與c無連邊，則s im(b,c)=|n(b)∩n(c)|/|n(b)∪n(c)|； 若節(jié)點(diǎn)b與c有連邊，則s im(b,c)=1。

1.5 改進(jìn)的K-殼分解法

文獻(xiàn)[15]結(jié)合K-殼分解法以及節(jié)點(diǎn)的信息熵，根據(jù)K-殼的分層大小依次進(jìn)行迭代，每層中選擇節(jié)點(diǎn)信息熵最高的節(jié)點(diǎn)，直到所有節(jié)點(diǎn)均被選中為止，定義為：

式中， τ(i)表 示節(jié)點(diǎn)i的 鄰居集；

1.6 引力模型

文獻(xiàn)[16]綜合考慮了節(jié)點(diǎn)的鄰居信息和節(jié)點(diǎn)間的路徑信息，分別將節(jié)點(diǎn)的度值和最短路徑長(zhǎng)度類比為物體的質(zhì)量和距離，提出了引力模型算法，計(jì)算公式如下：

式中，R表示截?cái)喟霃剑ǔ槠骄疃叹嚯x的一半。由于僅考慮了截?cái)喟霃絻?nèi)的引力，該算法也被稱為局部引力模型。

1.7 KSGC 算法模型

文獻(xiàn)[17]認(rèn)為節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的位置是一個(gè)重要屬性，因此，在K-殼分解法的基礎(chǔ)上對(duì)引力模型進(jìn)行了改進(jìn)，提出了KSGC 算法用于評(píng)估節(jié)點(diǎn)的影響力，計(jì)算公式如下：

1.8 交叉熵

交叉熵[28]廣泛應(yīng)用于邏輯回歸模型分析中，其定義為隨機(jī)分布p和q之間的自信息差異，可用來量化兩個(gè)變量之間的相似度，通常交叉熵值越大，則兩個(gè)變量之間的差異性越大，其計(jì)算公式如下：

式中，x表示事件包含的信息量。對(duì)式(8)同時(shí)增減可得：

將式(9)中的前兩項(xiàng)對(duì)數(shù)函數(shù)合并可得：

則式(10)可被定義為：

式中，H(p)為 信息熵，表示隨機(jī)分布p的平均信息量；DKL(p‖q)為 相對(duì)熵，同樣反映隨機(jī)分布p和q之間的差異程度。因此，交叉熵作為信息熵與相對(duì)熵之和，對(duì)于隨機(jī)變量的信息量及其差異性刻畫更加直觀。

2 基于交叉熵的節(jié)點(diǎn)重要性排序算法

2.1 算法構(gòu)造

交叉熵可衡量隨機(jī)變量所包含信息量的差異，類似地，復(fù)雜網(wǎng)絡(luò)中不同節(jié)點(diǎn)之間的拓?fù)湫畔⒁泊嬖诓町悾虼丝紤]引入交叉熵衡量復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的統(tǒng)計(jì)特征。

基于交叉熵的節(jié)點(diǎn)重要性排序算法的原理是綜合考察節(jié)點(diǎn)自身以及其周圍節(jié)點(diǎn)信息的整體重要性，結(jié)合這兩種拓?fù)湫畔ⅲ衫媒徊骒刂祦砹炕?jié)點(diǎn)分布之間的差異，若交叉熵值越大，則節(jié)點(diǎn)之間分布差異性越大，說明該節(jié)點(diǎn)代表性越高，重要性更顯著。因此本文提出了基于交叉熵的算法CE+，其定義如下：

式中，j∈Γ(i)表 示節(jié)點(diǎn)j是節(jié)點(diǎn)i的 鄰居節(jié)點(diǎn)；Ii表示節(jié)點(diǎn)i的異構(gòu)性。考慮到度中心性可在時(shí)間復(fù)雜度較低的同時(shí)較好地反映節(jié)點(diǎn)及其近鄰節(jié)點(diǎn)所構(gòu)成子網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，因此將Ii定義為：

由此，節(jié)點(diǎn)之間的異構(gòu)性可得以良好的表征。在基于交叉熵的節(jié)點(diǎn)重要性計(jì)算方法中，通過融合中心節(jié)點(diǎn)與其局部節(jié)點(diǎn)的信息結(jié)構(gòu)并相互交叉考慮，使得節(jié)點(diǎn)影響力的差異刻畫更為準(zhǔn)確。該算法的偽代碼如下。

表1 列出了8 種不同評(píng)估算法的時(shí)間復(fù)雜度，分別包括局部、全局以及混合3 個(gè)類型的網(wǎng)絡(luò)信息。其中CE+算法的時(shí)間復(fù)雜度與DC、LLS、ME 以及IKS 算法同為最低。

表1 不同評(píng)估算法的時(shí)間復(fù)雜度

2.2 示例分析

為初步驗(yàn)證CE+算法的量化分辨率與精確性，構(gòu)建示例網(wǎng)絡(luò)如圖1 所示。

圖1 示例網(wǎng)絡(luò)

在示例網(wǎng)絡(luò)中，以節(jié)點(diǎn)24 為例，其交叉熵計(jì)算過程如下：

節(jié)點(diǎn)24 的度值為1，其鄰居節(jié)點(diǎn)23 的度值為3，而節(jié)點(diǎn)23 的其余鄰居節(jié)點(diǎn)3、25 的度值分別為4、2，故計(jì)算節(jié)點(diǎn)24 的交叉熵值為0.282 4。同理，可以計(jì)算示例網(wǎng)絡(luò)中其他節(jié)點(diǎn)的交叉熵值，其計(jì)算結(jié)果如表2 所示。

表2 各節(jié)點(diǎn)的交叉熵值

表3 記錄了不同評(píng)估算法對(duì)示例網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行排序的結(jié)果，可以看出，KSGC 和GM 算法與本文所提出的CE+算法具有相同的排名廣度，但其對(duì)首要節(jié)點(diǎn)的排序結(jié)果略有不同，分別移除節(jié)點(diǎn)4、5 和14，得出非連通子圖的數(shù)量分別為2、2 和6，顯然移除節(jié)點(diǎn)14 對(duì)網(wǎng)絡(luò)破壞性更大。此外其余算法對(duì)網(wǎng)絡(luò)外圍節(jié)點(diǎn)的量化區(qū)分度較低，過于粗粒化。因此CE+算法對(duì)重要節(jié)點(diǎn)排序的精確性得到了初步驗(yàn)證。

表3 不同評(píng)估算法排序結(jié)果

3 實(shí)驗(yàn)數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

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

實(shí)驗(yàn)選用了8 個(gè)不同領(lǐng)域的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，分別是：維基語錄編輯網(wǎng)絡(luò)Wikiquote[29]、金融網(wǎng)絡(luò)Economic[30]、約束優(yōu)化模型網(wǎng)絡(luò)BP[31]、犯罪案件人物關(guān)系網(wǎng)絡(luò)Crime[32]、大學(xué)生電子郵件網(wǎng)絡(luò)Email[33]、空中交通管制網(wǎng)絡(luò)Traffic[34]、智人細(xì)胞中的蛋白質(zhì)網(wǎng)絡(luò)Proteins[35]以及青少年朋友關(guān)系網(wǎng)絡(luò)Adolescent[36]。表4 列出了各網(wǎng)絡(luò)的拓?fù)浣y(tǒng)計(jì)參數(shù)，其中N和E分別為網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)和連邊總數(shù)，D表示網(wǎng)絡(luò)的密度，kmax表示網(wǎng)絡(luò)節(jié)點(diǎn)的最大度值，和

表4 8 個(gè)真實(shí)網(wǎng)絡(luò)的拓?fù)浣y(tǒng)計(jì)特征及傳播率

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

為驗(yàn)證CE+算法的性能，本文基于網(wǎng)絡(luò)節(jié)點(diǎn)的單調(diào)關(guān)系、魯棒性以及SIR 傳播動(dòng)力學(xué)模型對(duì)節(jié)點(diǎn)重要性進(jìn)行研究。首先采用單調(diào)性指標(biāo)定量分析不同算法的分辨率，其次選取極大連通系數(shù)以及網(wǎng)絡(luò)效率指標(biāo)來評(píng)估攻擊節(jié)點(diǎn)前后網(wǎng)絡(luò)結(jié)構(gòu)和功能的變化，最后在SIR 模型上再進(jìn)行傳播仿真實(shí)驗(yàn)分析。

單調(diào)性指標(biāo)[23]是通過計(jì)算節(jié)點(diǎn)重要性排序中具有相同排名索引的節(jié)點(diǎn)比例來度量節(jié)點(diǎn)的評(píng)估效果，定義為：

式中，R為經(jīng)由節(jié)點(diǎn)重要性排序算法所得到的排名索引；nr表示具有相同排名索引的節(jié)點(diǎn)數(shù)量；M(R)∈[0,1]， 若M(R)=1，則該算法完全單調(diào)，所有節(jié)點(diǎn)都具有不同的排名索引值。若M(R)=0，則該算法無法區(qū)分，每個(gè)節(jié)點(diǎn)的排名索引值相同。

極大連通系數(shù)[24]常用于評(píng)價(jià)移除網(wǎng)絡(luò)中的節(jié)點(diǎn)后對(duì)極大連通子集的影響，表示為：

網(wǎng)絡(luò)效率[25-26]常用于度量網(wǎng)絡(luò)連通性的強(qiáng)弱，計(jì)算公式為：

攻擊網(wǎng)絡(luò)中一定比例的節(jié)點(diǎn)，若網(wǎng)絡(luò)效率下降趨勢(shì)越明顯，則該算法的排序準(zhǔn)確性越高。

SIR 模型[27]常用于驗(yàn)證節(jié)點(diǎn)傳播信息與病毒的能力，在SIR 模型中，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)具有3 種狀態(tài)，分別是易感狀態(tài)S、感染狀態(tài)I 以及免疫狀態(tài)R。病毒傳播初始時(shí)，除少數(shù)節(jié)點(diǎn)處于感染狀態(tài)外，其他節(jié)點(diǎn)均處于易感狀態(tài)。每個(gè)時(shí)間步長(zhǎng)里，感染節(jié)點(diǎn)以β 的概率嘗試感染易感的鄰居節(jié)點(diǎn)，此外，感染節(jié)點(diǎn)還以μ 的概率嘗試恢復(fù)為免疫節(jié)點(diǎn)，為不失一般性，本文設(shè)定恢復(fù)率μ =1。需要注意的是，免疫節(jié)點(diǎn)不會(huì)被再次感染，同樣也不具有感染能力。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定時(shí)，傳播過程結(jié)束，此時(shí)免疫節(jié)點(diǎn)的數(shù)量可用于量化初始感染節(jié)點(diǎn)的傳播能力。

4 實(shí)驗(yàn)分析

本文選取了度中心性（DC）、介數(shù)中心性（BC）等經(jīng)典算法作為對(duì)比方法，還選取了鄰域相似度（LLS）、引力模型（GM）、改進(jìn)的引力模型（KSGC）、映射熵（ME）以及改進(jìn)的K-殼分解法（IKS）等近期提出的性能顯著的排序算法進(jìn)行比較，記錄8 種排序算法在8 個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)上各評(píng)估指標(biāo)的實(shí)驗(yàn)結(jié)果。

4.1 單調(diào)性指標(biāo)

表5 記錄了本文所提出的CE+算法與其他評(píng)估算法的單調(diào)性指標(biāo)，加粗?jǐn)?shù)值為最優(yōu)值，可以看出，CE+算法在大部分網(wǎng)絡(luò)中均表現(xiàn)出較好的分辨率，并在一些網(wǎng)絡(luò)（如BP、Adolescent）中達(dá)到了1，這說明CE+算法是完全單調(diào)的，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都具有不同的排名索引值。此外，KSGC和GM 算法也表現(xiàn)出良好的區(qū)分度。

表5 不同評(píng)估算法的單調(diào)性指標(biāo)

4.2 極大連通系數(shù)

圖2 呈現(xiàn)了不同評(píng)估算法模擬蓄意攻擊網(wǎng)絡(luò)所造成極大連通系數(shù)變化的趨勢(shì)，其中橫坐標(biāo)為各評(píng)估算法排序下依次移除節(jié)點(diǎn)占節(jié)點(diǎn)總數(shù)的比例，縱坐標(biāo)為極大連通系數(shù)，可以看出在8 個(gè)真實(shí)網(wǎng)絡(luò)中，本文提出的CE+算法均表現(xiàn)出更好的攻擊效果。在BP 和Adolescent 網(wǎng)絡(luò)中，各算法的前期破壞效果出現(xiàn)了高度重合，這是因?yàn)榫W(wǎng)絡(luò)的連邊總數(shù)遠(yuǎn)高于節(jié)點(diǎn)總數(shù)，導(dǎo)致節(jié)點(diǎn)間緊密連接，而當(dāng)攻擊節(jié)點(diǎn)數(shù)達(dá)到一定比例時(shí)，CE+算法表現(xiàn)出了較其他算法更為明顯的攻擊效果。因此，CE+算法度量節(jié)點(diǎn)重要性的準(zhǔn)確性得到了驗(yàn)證。

圖2 8 個(gè)網(wǎng)絡(luò)在各類評(píng)估算法攻擊下極大連通系數(shù)變化

4.3 網(wǎng)絡(luò)效率

圖3 展現(xiàn)了利用不同的評(píng)估算法排序依次移除節(jié)點(diǎn)后，對(duì)網(wǎng)絡(luò)效率所造成的變化趨勢(shì)。可以看出，在Wikiquote 網(wǎng)絡(luò)、Economic 網(wǎng)絡(luò)和Adolescent網(wǎng)絡(luò)中，CE+算法相較于其他算法對(duì)網(wǎng)絡(luò)的蓄意攻擊效果更為明顯，而在Crime 網(wǎng)絡(luò)與Traffic 網(wǎng)絡(luò)中，KSGC 和IKS 算法的攻擊效果基本一致，ME 和DC 算法分別在移除節(jié)點(diǎn)比例達(dá)到16%以及18%時(shí)，破壞效果最明顯。此外，當(dāng)攻擊節(jié)點(diǎn)比例相同時(shí)，CE+算法的破壞曲線整體下降最快，這說明此時(shí)的網(wǎng)絡(luò)連通性最差。因此，CE+算法度量節(jié)點(diǎn)重要性的準(zhǔn)確性得到了進(jìn)一步驗(yàn)證。

圖3 8 個(gè)網(wǎng)絡(luò)在各類評(píng)估算法攻擊下網(wǎng)絡(luò)效率的變化

4.4 SIR 模型傳播

為從不同角度評(píng)價(jià)CE+算法的有效性和適用性，在SIR 模型中再進(jìn)行傳播實(shí)驗(yàn)分析，利用各種評(píng)估算法排序前10%的節(jié)點(diǎn)作為初始感染節(jié)點(diǎn)，傳播率閾值設(shè)定為βth=/。其中為平均度，為二階平均度。實(shí)際傳播率基于閾值四舍五入并精確到百分位，具體取值如表5 所示。為減小迭代過程隨機(jī)的影響，本文選擇對(duì)于N<1 000 的網(wǎng)絡(luò)模擬迭代1 000 次，對(duì)于N＞1 000 的網(wǎng)絡(luò)模擬迭代100 次。

圖4 反映了各評(píng)估算法中重要性排名前10%的節(jié)點(diǎn)作為感染節(jié)點(diǎn)N隨時(shí)間步長(zhǎng)t的變化趨勢(shì)，可以看出當(dāng)時(shí)間步長(zhǎng)達(dá)到15 時(shí)，大部分網(wǎng)絡(luò)趨于穩(wěn)定，其中CE+算法的傳播曲線具有處于穩(wěn)定狀態(tài)時(shí)的最高高度以及最大斜率，這說明本文所提出的算法具有最廣泛的傳播范圍以及最快傳播速率。而在BP 網(wǎng)絡(luò)中，CE+算法的傳播效果與其他算法的差異較小，是因?yàn)樵摼W(wǎng)絡(luò)的節(jié)點(diǎn)間分布密集，關(guān)聯(lián)程度較高，信息具有易傳播、易擴(kuò)散的特點(diǎn)。整體來看，CE+算法相較于其他算法更能準(zhǔn)確快速地挖掘出網(wǎng)絡(luò)中影響能力較強(qiáng)的節(jié)點(diǎn)。

圖4 8 個(gè)網(wǎng)絡(luò)在各類評(píng)估算法下感染節(jié)點(diǎn)的變化

為比較不同比例的初始節(jié)點(diǎn)在傳播達(dá)到穩(wěn)態(tài)時(shí)的規(guī)模，本文分別選取模擬迭代1 000 次的Crime網(wǎng)絡(luò)以及模擬迭代次數(shù)100 次的Traffic 網(wǎng)絡(luò)，并分別選取各種算法排名前5%、15%以及20%的節(jié)點(diǎn)作為感染節(jié)點(diǎn)進(jìn)行傳播驗(yàn)證實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果分別如圖5 和圖6 所示。結(jié)合圖5 中Crime 和Traffic網(wǎng)絡(luò)圖可知，BC 算法曲線趨于穩(wěn)態(tài)的高度僅在初始感染節(jié)點(diǎn)為5%時(shí)較高，IKS 算法曲線也僅在初始感染節(jié)點(diǎn)比例為20%時(shí)具有較大的斜率，而CE+算法在各種比例初始感染節(jié)點(diǎn)下均具有顯著的傳播范圍以及感染速率，可知CE+算法在這兩方面優(yōu)于其他算法，由此驗(yàn)證了CE+算法的有效性以及適用性。

圖5 不同比例初始節(jié)點(diǎn)在Crime 網(wǎng)絡(luò)上感染節(jié)點(diǎn)的變化

5 結(jié) 束 語

在網(wǎng)絡(luò)科學(xué)研究中，識(shí)別復(fù)雜網(wǎng)絡(luò)中的核心關(guān)鍵節(jié)點(diǎn)有助于提高網(wǎng)絡(luò)的魯棒性和抗毀性。本文基于交叉熵提出了一種新的節(jié)點(diǎn)性能評(píng)價(jià)排序算法，算法只需獲取中心節(jié)點(diǎn)與其近鄰節(jié)點(diǎn)的信息就可反映節(jié)點(diǎn)之間的差異性，并且時(shí)間復(fù)雜度僅為O(n)，適用于刻畫大規(guī)模復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的重要性。通過在8 個(gè)不同領(lǐng)域的真實(shí)網(wǎng)絡(luò)上進(jìn)行單調(diào)關(guān)系、極大連通系數(shù)、網(wǎng)絡(luò)效率以及SIR 模型傳播實(shí)驗(yàn)，結(jié)果表明，本文所提的CE+算法對(duì)比DC、BC、LLS、KSGC、GM、ME 和IKS 算法具有更高效的性能。