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

劉勇

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

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

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

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

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

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

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

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

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

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

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

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

圖3 各節(jié)點評價指標值

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

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

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

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

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

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

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

當節(jié)點i和節(jié)點j之間有聯(lián)接時，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é)點對之間有一條或多條路徑。如果圖是非連通的，它可以被分成兩個或多個子圖。在這些子圖中，節(jié)點數(shù)最多的子圖是最大連通子圖S：

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

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

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

網(wǎng)絡(luò)結(jié)構(gòu)熵則用來衡量節(jié)點對計算機網(wǎng)絡(luò)的影響程度是否均勻，是描述網(wǎng)絡(luò)結(jié)構(gòu)的宏觀指標。

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

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

圖4 關(guān)鍵節(jié)點識別

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

利用AHP方法，求得評價指標權(quán)重為：

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

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

其中，cij為第i個節(jié)點的第j個指標的值。

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

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

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

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

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

圖5 算法流程

3 仿真分析

3.1 關(guān)鍵節(jié)點識別

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

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

圖8 魯棒性分析

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

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

4 結(jié) 論

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