一種計(jì)算機(jī)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法

劉勇

（商洛學(xué)院，陜西 商洛 726000）

近幾年，計(jì)算機(jī)行業(yè)發(fā)展迅速，計(jì)算機(jī)用戶逐漸增多，計(jì)算機(jī)網(wǎng)絡(luò)日趨復(fù)雜，這給計(jì)算機(jī)網(wǎng)絡(luò)安全帶來(lái)了巨大壓力。準(zhǔn)確分析當(dāng)前計(jì)算機(jī)網(wǎng)絡(luò)結(jié)構(gòu)，已然成為計(jì)算機(jī)安全領(lǐng)域研究的熱點(diǎn)問(wèn)題。

隨著復(fù)雜性科學(xué)的快速發(fā)展，復(fù)雜網(wǎng)絡(luò)理論在各個(gè)領(lǐng)域都得到了廣泛應(yīng)用，利用復(fù)雜網(wǎng)絡(luò)理論對(duì)計(jì)算機(jī)網(wǎng)絡(luò)的研究也成為計(jì)算機(jī)領(lǐng)域關(guān)注的熱點(diǎn)。利用復(fù)雜網(wǎng)絡(luò)理論不僅可以很好地展現(xiàn)計(jì)算機(jī)網(wǎng)絡(luò)內(nèi)部微觀信息，同時(shí)也反映了其宏觀特點(diǎn)。利用復(fù)雜網(wǎng)絡(luò)理論可以探究計(jì)算機(jī)網(wǎng)絡(luò)的內(nèi)部拓?fù)浣Y(jié)構(gòu)，對(duì)熟悉和了解計(jì)算機(jī)網(wǎng)絡(luò)都有著重要意義。

在對(duì)復(fù)雜網(wǎng)絡(luò)研究的過(guò)程中，學(xué)者們發(fā)現(xiàn)網(wǎng)絡(luò)中的少數(shù)節(jié)點(diǎn)往往起到關(guān)鍵作用[1]，它們甚至能夠決定整個(gè)網(wǎng)絡(luò)的結(jié)構(gòu)和功能。例如，通過(guò)對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行完善，可以提高電網(wǎng)抗毀性[2]以及物聯(lián)網(wǎng)的穩(wěn)定性[3]，也可以蓄意攻擊關(guān)鍵節(jié)點(diǎn)來(lái)摧毀相應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)，防止傳播疾病等[4]。同樣，在計(jì)算機(jī)網(wǎng)絡(luò)中，發(fā)現(xiàn)相似性結(jié)構(gòu)[5]、識(shí)別少數(shù)關(guān)鍵節(jié)點(diǎn)狀態(tài)的變化，將對(duì)當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)造成巨大的影響，而如何對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行有效識(shí)別是該文要解決的核心問(wèn)題。

在復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別的研究中，目前主要的方法是根據(jù)某種評(píng)估指標(biāo)對(duì)網(wǎng)絡(luò)的節(jié)點(diǎn)進(jìn)行排序，例如度中心性[6]、接近中心性[7]等方法。但如果只使用某一種指標(biāo)就顯得較為單一，忽略了網(wǎng)絡(luò)的整體特性，評(píng)價(jià)結(jié)果不夠準(zhǔn)確。為使得評(píng)價(jià)結(jié)果更加客觀準(zhǔn)確，現(xiàn)在學(xué)者通常采用多指標(biāo)對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行識(shí)別。Wen選取網(wǎng)絡(luò)信息量等全局指標(biāo)，并結(jié)合最小二乘支持向量機(jī)（LS-SVM）給出航空網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)快速識(shí)別方法[8-9]。Ren基于信息熵理論，對(duì)影響航路運(yùn)行較大的節(jié)點(diǎn)（航路點(diǎn)）進(jìn)行識(shí)別[10]。

該文以計(jì)算機(jī)網(wǎng)絡(luò)中的個(gè)體為節(jié)點(diǎn)，個(gè)體之間能夠建立通信聯(lián)系，即為連邊，構(gòu)建計(jì)算機(jī)網(wǎng)絡(luò)，分析網(wǎng)絡(luò)中個(gè)體對(duì)整個(gè)網(wǎng)絡(luò)的影響。針對(duì)計(jì)算機(jī)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)進(jìn)行研究，并對(duì)其加以重點(diǎn)保護(hù)，可以有效遏制計(jì)算機(jī)網(wǎng)絡(luò)病毒的傳播和擴(kuò)散，優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)，使其具有更高的安全性和連通性。

1 計(jì)算機(jī)網(wǎng)絡(luò)建模

計(jì)算機(jī)網(wǎng)絡(luò)就是計(jì)算機(jī)通過(guò)互聯(lián)網(wǎng)或者其他相應(yīng)的媒介聯(lián)接起來(lái)的網(wǎng)絡(luò)結(jié)構(gòu)G=(V,E)。節(jié)點(diǎn)V代表網(wǎng)絡(luò)中的個(gè)體，而連邊E則為聯(lián)接個(gè)體之間的媒介，如圖1所示。

圖1 網(wǎng)絡(luò)結(jié)構(gòu)圖

利用Matlab軟件隨機(jī)生成的一個(gè)模擬計(jì)算機(jī)網(wǎng)絡(luò)G=(V,E)，該網(wǎng)絡(luò)中包含24個(gè)節(jié)點(diǎn)，如圖2所示。

圖2 模擬計(jì)算機(jī)網(wǎng)絡(luò)

對(duì)該網(wǎng)絡(luò)的相關(guān)復(fù)雜網(wǎng)絡(luò)指標(biāo)的分析如下。各節(jié)點(diǎn)的節(jié)點(diǎn)度、點(diǎn)強(qiáng)、聚類系數(shù)、節(jié)點(diǎn)介數(shù)4類指標(biāo)的得分情況如圖3所示。

圖3 各節(jié)點(diǎn)評(píng)價(jià)指標(biāo)值

各指標(biāo)從不同角度反映了節(jié)點(diǎn)的重要程度，但是上述指標(biāo)主要從節(jié)點(diǎn)自身以及鄰居節(jié)點(diǎn)屬性進(jìn)行分析，缺乏對(duì)網(wǎng)絡(luò)整體性能的思考。

節(jié)點(diǎn)刪除方法[11]是一種最典型的系統(tǒng)分析方法，它將節(jié)點(diǎn)從網(wǎng)絡(luò)中刪除后所造成的破壞程度定義為重要性，通過(guò)逆向思維避免了網(wǎng)絡(luò)分析中由于屬性和指標(biāo)選擇不合理而產(chǎn)生的一些問(wèn)題。當(dāng)一個(gè)節(jié)點(diǎn)被從網(wǎng)絡(luò)中移除時(shí)，需要對(duì)網(wǎng)絡(luò)性能進(jìn)行評(píng)估，以便計(jì)算它造成的破壞程度[12-13]。網(wǎng)絡(luò)整體性能的評(píng)估需要客觀且全面，根據(jù)復(fù)雜網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的現(xiàn)有識(shí)別方法和計(jì)算機(jī)網(wǎng)絡(luò)的基本特征，選取網(wǎng)絡(luò)效率、連接密度、最大連通子圖和網(wǎng)絡(luò)結(jié)構(gòu)熵4個(gè)典型的整體性能指標(biāo)作為評(píng)價(jià)指標(biāo)體系。

1）網(wǎng)絡(luò)效率（Network Efficient,NE）

網(wǎng)絡(luò)效率是Latora提出的一個(gè)衡量網(wǎng)絡(luò)信息交換性能的指標(biāo)，假設(shè)網(wǎng)絡(luò)內(nèi)部信息傳遞的效率取決于節(jié)點(diǎn)對(duì)之間的最短路徑長(zhǎng)度[14]。網(wǎng)絡(luò)效率是所有節(jié)點(diǎn)之間的最短路徑倒數(shù)和取平均值得到的，根據(jù)以上定義，網(wǎng)絡(luò)效率可以用公式表示為：

其中，n是當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)的總數(shù)，dij為圖測(cè)地線距離。它是由節(jié)點(diǎn)間路徑距離的倒數(shù)來(lái)計(jì)算的，因此避免了非連通圖中無(wú)意義的情況。此外，當(dāng)考慮網(wǎng)絡(luò)中的所有節(jié)點(diǎn)時(shí)，為全局效率；當(dāng)取子圖的效率值的平均值時(shí)，為局部效率。式中兩個(gè)節(jié)點(diǎn)之間的距離是兩節(jié)點(diǎn)之間的最少連邊數(shù)，這也被稱為測(cè)地線距離。網(wǎng)絡(luò)效率可以反映網(wǎng)絡(luò)信息交換的效率，NE越大，節(jié)點(diǎn)對(duì)之間的距離越近，計(jì)算機(jī)網(wǎng)絡(luò)穩(wěn)定性越高。

2）連接密度（Connection Density,CD）

在未加權(quán)網(wǎng)絡(luò)中，連接密度是指網(wǎng)絡(luò)中現(xiàn)有連邊與可能存在的連邊之間的比率。對(duì)于計(jì)算機(jī)網(wǎng)絡(luò)，該文定義了加權(quán)連接密度，如式（2）：

當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有聯(lián)接時(shí)，aij=1，否則aij=0。可以看出，CD越大，整體異構(gòu)性越高，網(wǎng)絡(luò)流量越大，網(wǎng)絡(luò)結(jié)構(gòu)越復(fù)雜。

3）最大連通子圖（Largest Component,LC）

子圖是網(wǎng)絡(luò)的一部分，其中所有節(jié)點(diǎn)對(duì)之間有一條或多條路徑。如果圖是非連通的，它可以被分成兩個(gè)或多個(gè)子圖。在這些子圖中，節(jié)點(diǎn)數(shù)最多的子圖是最大連通子圖S：

|S|是最大連通子圖的大小。一般來(lái)說(shuō)，最大連通子圖中的節(jié)點(diǎn)越多，計(jì)算機(jī)網(wǎng)絡(luò)的通聯(lián)程度越高，網(wǎng)絡(luò)整體性能越好。

4）網(wǎng)絡(luò)結(jié)構(gòu)熵（Network Structure Entropy,NS）

通常，節(jié)點(diǎn)重要度被表示為該節(jié)點(diǎn)的度與所有節(jié)點(diǎn)度之和的比值，如式（4）所示：

網(wǎng)絡(luò)結(jié)構(gòu)熵則用來(lái)衡量節(jié)點(diǎn)對(duì)計(jì)算機(jī)網(wǎng)絡(luò)的影響程度是否均勻，是描述網(wǎng)絡(luò)結(jié)構(gòu)的宏觀指標(biāo)。

2 關(guān)鍵節(jié)點(diǎn)識(shí)別方法

不同的評(píng)價(jià)指標(biāo)從不同角度提取節(jié)點(diǎn)重要度，該文將在現(xiàn)有的研究基礎(chǔ)上，基于復(fù)雜網(wǎng)絡(luò)理論，針對(duì)計(jì)算機(jī)網(wǎng)絡(luò)特征，參考現(xiàn)有的節(jié)點(diǎn)重要度評(píng)價(jià)方法，綜合考慮節(jié)點(diǎn)的各項(xiàng)性能指標(biāo)，利用層析分析法（AHP）確定指標(biāo)權(quán)重，并通過(guò)多屬性決策的方法確定節(jié)點(diǎn)重要度，對(duì)計(jì)算機(jī)網(wǎng)絡(luò)節(jié)點(diǎn)重要度進(jìn)行排序，從中找出對(duì)網(wǎng)絡(luò)結(jié)構(gòu)影響較大的關(guān)鍵沖突點(diǎn)，為保護(hù)計(jì)算機(jī)網(wǎng)絡(luò)安全提供對(duì)策，如圖4所示。

圖4 關(guān)鍵節(jié)點(diǎn)識(shí)別

根據(jù)各指標(biāo)對(duì)網(wǎng)絡(luò)整體性能的解釋程度，可以給出判斷矩陣：

利用AHP方法，求得評(píng)價(jià)指標(biāo)權(quán)重為：

不同節(jié)點(diǎn)摧毀前后網(wǎng)絡(luò)性能的變化顯然是一個(gè)多屬性決策問(wèn)題，可由TOPSIS方法解決。

首先構(gòu)造初始決策矩陣：

其中，cij為第i個(gè)節(jié)點(diǎn)的第j個(gè)指標(biāo)的值。

由式（7）可知，第j個(gè)指標(biāo)的權(quán)重為Hj(j=1,2,…,m)，∑Hj=1，因此加權(quán)矩陣:

基于TOPSIS方法，根據(jù)矩陣Y確定正理想方案A。A中的元素是Y中各列的最大值，按照A方案刪除后，網(wǎng)絡(luò)性能值下降最大：

然后計(jì)算各方案Ai到正理想方案A的距離：

Di越大，方案Ai與正理想方案A之間的距離越大，也就說(shuō)明刪除該節(jié)點(diǎn)后網(wǎng)絡(luò)綜合性能的變化越大，即對(duì)應(yīng)的節(jié)點(diǎn)vi越重要。

計(jì)算機(jī)網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別算法流程如圖5所示，該文將節(jié)點(diǎn)的重要程度視為節(jié)點(diǎn)刪除前后對(duì)網(wǎng)絡(luò)的破壞程度，類似于計(jì)算機(jī)網(wǎng)絡(luò)中節(jié)點(diǎn)破壞后對(duì)網(wǎng)絡(luò)的影響程度。

圖5 算法流程

3 仿真分析

3.1 關(guān)鍵節(jié)點(diǎn)識(shí)別

為驗(yàn)證方法的有效性，對(duì)模擬計(jì)算機(jī)網(wǎng)絡(luò)進(jìn)行分析。由第2節(jié)中的方法可得模擬計(jì)算機(jī)網(wǎng)絡(luò)各節(jié)點(diǎn)的重要度值，并進(jìn)行排序，如表1所示。

同時(shí)給出用度中心性、接近中心性和節(jié)點(diǎn)放縮法的節(jié)點(diǎn)重要度排序。此外，對(duì)表1中的關(guān)鍵節(jié)點(diǎn)（刪除排名靠前的5個(gè)節(jié)點(diǎn)）進(jìn)行攻擊，攻擊前后的網(wǎng)絡(luò)結(jié)構(gòu)對(duì)比如圖6（a）和6（b）所示。

表1 關(guān)鍵節(jié)點(diǎn)排序

圖6 關(guān)鍵節(jié)點(diǎn)刪除前后網(wǎng)絡(luò)結(jié)構(gòu)對(duì)比

可以明顯看出，當(dāng)對(duì)關(guān)鍵節(jié)點(diǎn)進(jìn)行攻擊后，該網(wǎng)絡(luò)幾乎演變?yōu)閮蓚€(gè)獨(dú)立的子網(wǎng)絡(luò)。

3.2 結(jié)果分析

當(dāng)根據(jù)節(jié)點(diǎn)刪除方法、節(jié)點(diǎn)放縮法、接近中心性方法和度中心性方法的節(jié)點(diǎn)重要性排序從計(jì)算機(jī)網(wǎng)絡(luò)中進(jìn)行調(diào)配時(shí)，各評(píng)估指標(biāo)的變化趨勢(shì)如圖7所示。

從圖7中可以看出，隨著關(guān)鍵節(jié)點(diǎn)在網(wǎng)絡(luò)中逐一攻擊的過(guò)程，模擬計(jì)算機(jī)網(wǎng)絡(luò)的效率、連接密度、最大連通子圖和網(wǎng)絡(luò)結(jié)構(gòu)熵持續(xù)下降。節(jié)點(diǎn)刪除方法的曲線大部分都位于其他方法之下，即當(dāng)攻擊相同節(jié)點(diǎn)數(shù)時(shí)，節(jié)點(diǎn)刪除方法對(duì)網(wǎng)絡(luò)造成的影響更大。

圖7 網(wǎng)絡(luò)指標(biāo)變化

為了進(jìn)一步驗(yàn)證提出的關(guān)鍵節(jié)點(diǎn)識(shí)別方法的有效性，記錄不同方法對(duì)原網(wǎng)絡(luò)刪除節(jié)點(diǎn)過(guò)程中的網(wǎng)絡(luò)魯棒性變化，如圖8所示。

圖8 魯棒性分析

網(wǎng)絡(luò)魯棒性用于測(cè)量在移除任何節(jié)點(diǎn)之后保持網(wǎng)絡(luò)中剩余節(jié)點(diǎn)之間的連通性能力的平均影響[15-16]。即刪除任何節(jié)點(diǎn)后，網(wǎng)絡(luò)中仍可聯(lián)接的節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)之比的平均值。假設(shè)刪除一個(gè)節(jié)點(diǎn)后，網(wǎng)絡(luò)中剩余的節(jié)點(diǎn)集為Gk，網(wǎng)絡(luò)魯棒性NR的計(jì)算公式為：

從仿真結(jié)果可以看出，隨著調(diào)配節(jié)點(diǎn)數(shù)量的增加，每種方法的整體網(wǎng)絡(luò)性能穩(wěn)步下降。然而，當(dāng)根據(jù)節(jié)點(diǎn)刪除方法進(jìn)行調(diào)配時(shí)，整體性能明顯下降得更快。因此，該方法能夠準(zhǔn)確識(shí)別計(jì)算機(jī)網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。

4 結(jié) 論

基于復(fù)雜計(jì)算機(jī)網(wǎng)絡(luò)模型，提出了一種節(jié)點(diǎn)刪除方法來(lái)識(shí)別對(duì)網(wǎng)絡(luò)結(jié)構(gòu)影響較大的關(guān)鍵節(jié)點(diǎn)。為了驗(yàn)證該方法對(duì)關(guān)鍵節(jié)點(diǎn)的識(shí)別效果，將識(shí)別結(jié)果與其他方法進(jìn)行比較，結(jié)果顯示，提出的方法能夠準(zhǔn)確識(shí)別計(jì)算機(jī)網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。而識(shí)別構(gòu)成計(jì)算機(jī)網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)有助于計(jì)算機(jī)網(wǎng)絡(luò)安全保護(hù)，此外，在應(yīng)急管理中，可以幫助管理人員有重點(diǎn)、有針對(duì)性地完成應(yīng)急資源的分配，使計(jì)算機(jī)網(wǎng)絡(luò)安全工作有條不紊地進(jìn)行。