夏昱，滕克難，陳健

(海軍航空工程學(xué)院 a.研究生大隊;b.訓(xùn)練部，山東 煙臺 264001)

0 引言

研究表明[1-4]不同拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)對不同方式的攻擊具有不同的抗毀性，在隨機攻擊下無標(biāo)度網(wǎng)絡(luò)比隨機網(wǎng)絡(luò)具有更強的容錯性，但在選擇性攻擊下，無標(biāo)度網(wǎng)絡(luò)卻又顯得異常脆弱。因此，對復(fù)雜網(wǎng)絡(luò)中節(jié)點的重要度進行評估是非常有意義的。由節(jié)點重要度評估找出那些重要的“核心節(jié)點”，可以通過重點保護這些“核心節(jié)點”提高整個網(wǎng)絡(luò)的抗毀性和可靠性。

評估網(wǎng)絡(luò)中節(jié)點重要性的方法很多，本質(zhì)上都是源于圖論[5-8]，最簡單的方法是以節(jié)點的連接度(節(jié)點連接的邊數(shù))作為節(jié)點重要度的衡量標(biāo)準(zhǔn)，認(rèn)為與節(jié)點相連的邊越多則該節(jié)點越重要[9]。這種評估方法具有片面性，有些重要的“核心節(jié)點”并不一定具有較大的連接度，比如只有2條邊相連的“橋節(jié)點”[10]。文獻[11-12]中提出的介數(shù)(betweenness centrality)能很好地衡量節(jié)點的重要度，即經(jīng)過該節(jié)點的最短路徑越多，該節(jié)點越重要，但僅僅用節(jié)點的介數(shù)表示節(jié)點重要度顯然是不夠全面的。文獻[13]提出了一種基于生成樹數(shù)目的節(jié)點刪除法，定義最重要的節(jié)點為去掉該節(jié)點使得生成樹數(shù)目最小的節(jié)點。節(jié)點刪除法的問題是如果多個節(jié)點的刪除都使得網(wǎng)絡(luò)不連通，那么這些節(jié)點的重要度將是一致的，從而使得估計結(jié)果不精確。

本文首先定義了網(wǎng)絡(luò)節(jié)點接近度和關(guān)聯(lián)度，然后定義了節(jié)點的重要度。在此基礎(chǔ)上給出了節(jié)點重要度評估方法及其算法，該方法結(jié)合了節(jié)點在復(fù)雜網(wǎng)路中的重要性，通過艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)分析驗證了該方法的有效性。

1 評估模型

1.1 節(jié)點介數(shù)

節(jié)點介數(shù)衡量了網(wǎng)絡(luò)中所有的最短路徑中經(jīng)過該節(jié)點的數(shù)量比例，定義為

(1)

式中:σij(k)為節(jié)點i和j之間最短路徑經(jīng)過節(jié)點k的數(shù)目；σij為節(jié)點i和j之間最短路徑的總數(shù)；V為網(wǎng)絡(luò)節(jié)點集合。

節(jié)點介數(shù)體現(xiàn)的是網(wǎng)絡(luò)中某個節(jié)點在整個網(wǎng)絡(luò)傳遞信息過程中的重要程度，比如通信衛(wèi)星映射的節(jié)點往往具有較高的點介數(shù)。節(jié)點介數(shù)的計算非常復(fù)雜，不僅要計算各個節(jié)點對之間的最短路徑長度，還要記錄這些最短路徑的路線，為此利用Pajek軟件計算節(jié)點的介數(shù)，它可以快速有效地計算出每個節(jié)點的介數(shù)。

1.2 節(jié)點接近度

假設(shè)d(vi,vj)表示以節(jié)點vi為起點，節(jié)點vj為終點的最短路徑長度，則節(jié)點vi的節(jié)點接近度C(i)定義為

(2)

復(fù)雜網(wǎng)絡(luò)本質(zhì)上的非同質(zhì)拓?fù)浣Y(jié)構(gòu)，決定了網(wǎng)絡(luò)中每個節(jié)點的重要程度是不同的。節(jié)點在復(fù)雜網(wǎng)絡(luò)中的重要度首先取決于節(jié)點在網(wǎng)絡(luò)中的位置，根據(jù)式(2)可知，節(jié)點接近度C(i)越大，節(jié)點越居于網(wǎng)絡(luò)中心，節(jié)點在全局網(wǎng)絡(luò)中越重要。

1.3 節(jié)點關(guān)聯(lián)度

灰色關(guān)聯(lián)分析對系統(tǒng)數(shù)據(jù)序列幾何關(guān)系和曲線幾何形狀的相似程度進行比較，以曲線間相似程度大小作為關(guān)聯(lián)程度的衡量尺度。一組幾何曲線形狀越相似，則相應(yīng)序列之間的關(guān)聯(lián)度越大，反之則越小。由此為所考察的復(fù)雜系統(tǒng)綜合決策提供信息。

節(jié)點關(guān)聯(lián)度分析的基本思想是：首先確定復(fù)雜網(wǎng)絡(luò)的“核心節(jié)點”，即認(rèn)為與網(wǎng)絡(luò)中所有節(jié)點均有邊相連接的節(jié)點為最重要的“核心節(jié)點”，如星形網(wǎng)中的中心節(jié)點顯然是網(wǎng)絡(luò)中最重要的核心節(jié)點，可以通過重點保護這些“核心節(jié)點”提高整個網(wǎng)絡(luò)的可靠性，也可以通過攻擊這些“薄弱環(huán)節(jié)”，達(dá)到摧毀整個網(wǎng)絡(luò)的目的。以此為基準(zhǔn)，利用灰關(guān)聯(lián)分析理論，用灰色關(guān)聯(lián)度評價網(wǎng)絡(luò)中各節(jié)點與理想節(jié)點的關(guān)聯(lián)程度，通過對關(guān)聯(lián)度進行排序，從而確定網(wǎng)絡(luò)中的“核心節(jié)點”。

1.3.1 虛擬理想“核心節(jié)點”的確定

在復(fù)雜網(wǎng)絡(luò)中，最理想的“核心節(jié)點”是與網(wǎng)絡(luò)中每個節(jié)點都有邊相連的節(jié)點，設(shè)其與每個節(jié)點的連接關(guān)系所構(gòu)成的序列X0={X0(k)|k=1,2,…,n}(n為網(wǎng)絡(luò)中的節(jié)點數(shù))作為參考序列，比較序列為網(wǎng)絡(luò)中每個節(jié)點與其余節(jié)點的連接關(guān)系所構(gòu)成的序列：

Xi={Xi(k)|k=1,2,…,n}，i=1,2,…,n,

1.3.2 關(guān)聯(lián)系數(shù)的計算

關(guān)聯(lián)系數(shù)是灰色關(guān)聯(lián)分析中用于表示待評序列與參考序列接近程度的數(shù)值，值越大，表示接近程度越高，即越接近虛擬的理想“核心節(jié)點”，這樣的節(jié)點即為網(wǎng)絡(luò)中重要的“核心節(jié)點”。

比較序列Xi對于參考序列X0在k點的關(guān)聯(lián)系數(shù)為

ξi(k)=

(3)

式中：ρ∈(0,+∞)為分辨系數(shù)。ρ越小，分辨能力越強，ρ∈(0,1) ，一般取ρ=0.5。

1.3.3 關(guān)聯(lián)度計算

由于關(guān)聯(lián)系數(shù)計算得到的是各比較序列與參考序列在各點的關(guān)聯(lián)系數(shù)值，結(jié)果較多，信息過于分散，不便于比較，因此，須將每一比較序列各個時刻的關(guān)聯(lián)系數(shù)集中體現(xiàn)在一個數(shù)值上，即關(guān)聯(lián)度。通常關(guān)聯(lián)度的計算方法采用平均值法：

(4)

式中：ξi(k)(i=1,2,…,n)為灰關(guān)聯(lián)序列。

1.4 節(jié)點的重要度

1.4.1 節(jié)點重要度定義

為全面評價網(wǎng)絡(luò)中節(jié)點的重要度，綜合考慮節(jié)點的介數(shù)、接近度和關(guān)聯(lián)度的影響，將節(jié)點vi的重要度定義為

(5)

K(i)越大，節(jié)點在網(wǎng)絡(luò)中越重要。

1.4.2 節(jié)點重要度算法步驟

復(fù)雜網(wǎng)絡(luò)中節(jié)點重要度評估的算法流程如下：

(1) 利用Pajek軟件計算節(jié)點vi的介數(shù)B(i)。

(2) 計算節(jié)點vi的接近度C(i)。

1) 利用Matlab編程計算任意節(jié)點之間的最短路徑長度；

2) 計算得到節(jié)點vi的平均最短路徑長度；

3) 根據(jù)式(2)計算節(jié)點vi的接近度C(i)。

(3) 計算節(jié)點vi關(guān)聯(lián)度A(i)

1) 選取參考序列X0={X0(k)=1|k=1,2,…,n,n為網(wǎng)絡(luò)中的節(jié)點數(shù)}；

2) 根據(jù)網(wǎng)絡(luò)圖得到比較序列，即圖的鄰接矩陣X=(Xi)n×n，Xi={Xi(k)|k=1,2,…,n}，

i=1,2,…,n，k=1,2,…,n，

3) 根據(jù)式(3)計算比較序列Xi對于參考序列X0在k點的關(guān)聯(lián)系數(shù)ξi(k)；

4) 根據(jù)式(4)計算節(jié)點vi的關(guān)聯(lián)度A(i)。

(4) 按照式(4)計算節(jié)點的重要度K(i)，并將K(i)按從大到小排序，從而確定網(wǎng)絡(luò)中每個節(jié)點的重要程度。

2 艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)模型

2.1 模型仿真算例

假設(shè)有一個由10艘艦艇組成的艦艇編隊，每艘艦艇的指控中心看成1個決策器D；艦艇上的導(dǎo)彈系統(tǒng)、前后主炮、深彈、火箭彈等武器裝備及作戰(zhàn)飛機、潛艇上的作戰(zhàn)武器可以抽象為20個影響器I；艦艇上的雷達(dá)、聲吶、光電傳感器、參與作戰(zhàn)的預(yù)警機、岸基觀通站雷達(dá)和天基偵察衛(wèi)星等抽象為20個傳感器S；敵方發(fā)射5枚飛航式反艦導(dǎo)彈抽象為5個目標(biāo)T。假設(shè)T，S，D，I4類節(jié)點的數(shù)目分別為NT，NS，ND，NI。這樣，整個編隊就能抽象為NT=5，NS=20，ND=10，NI=20的一個作戰(zhàn)網(wǎng)絡(luò)；各節(jié)點間連接概率為：PST=0.3，PDI=0.8，傳感器S之間及影響器I之間的NW小世界網(wǎng)絡(luò)中，加邊概率PSS和PII分別取0.4和0.4，決策器D之間采用BA無標(biāo)度網(wǎng)絡(luò)進行連接。

這樣整個艦艇編隊協(xié)同反導(dǎo)作戰(zhàn)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示。

圖1 傳感器之間和影響器之間采用NW小世界網(wǎng)絡(luò)連接且決策器之間BA無標(biāo)度網(wǎng)絡(luò)連接的艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖Fig.1 Formation of antimissile network of which sensors and influencers use NW small-world and decision-making uses BA free-scale network

2.2 模型參數(shù)分析

傳感器之間和影響器之間采用NW小世界網(wǎng)絡(luò)連接,決策器之間采用BA無標(biāo)度網(wǎng)絡(luò)連接構(gòu)建的艦艇編隊反導(dǎo)作戰(zhàn)網(wǎng)絡(luò)，利用Pajek軟件得到該網(wǎng)絡(luò)模型的特征參數(shù)如表1所示。模型各節(jié)點的度分布如圖2所示，其中節(jié)點1～5為目標(biāo)節(jié)點，節(jié)點6～25為傳感器節(jié)點，節(jié)點26～35為決策器節(jié)點，節(jié)點36～55為影響器節(jié)點。

圖2 艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)的度分布圖Fig.2 Degree distribution of fleet cooperation antimissile network

3 艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)節(jié)點重要度評估

根據(jù)1.4.2節(jié)中網(wǎng)絡(luò)節(jié)點重要度評估的算法流程，計算艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)中所有55個節(jié)點的重要度。表2給出了所有節(jié)點的重要度評估結(jié)果。

表1 艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)模型參數(shù)Table 1 Model parameters of fleet cooperation antimissile network

表2 艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)重要度評估結(jié)果

通過表2艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)重要度評估結(jié)果，可以看出，決策器D是網(wǎng)絡(luò)中最重要的節(jié)點，這正與其在艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)中的作用相匹配；其次重要的節(jié)點為影響器I，由于影響器I與決策器D、目標(biāo)T及I之間的互連，使得影響器I的度增加，因而其重要性增加；雖然傳感器S與影響器I的網(wǎng)絡(luò)都采用了小世界網(wǎng)絡(luò)互連，但由于艦艇編隊反導(dǎo)網(wǎng)絡(luò)為有向邊網(wǎng)絡(luò)，存在從目標(biāo)T到傳感器S和從影響器I到目標(biāo)T的連接，因此，影響器節(jié)點的出度要大于傳感器節(jié)點的出度，因而具更大的重要度。

4 結(jié)束語

本文中針對有向網(wǎng)絡(luò)提出了基于節(jié)點接近度及關(guān)聯(lián)度評估節(jié)點在復(fù)雜網(wǎng)絡(luò)中的重要度方法，定義了節(jié)點的接近度、關(guān)聯(lián)度及重要度，全面綜合地描述了節(jié)點在復(fù)雜網(wǎng)絡(luò)中的重要性，針對艦艇編隊協(xié)同反導(dǎo)網(wǎng)絡(luò)中節(jié)點的重要度，證明了該方法的有效性。

參考文獻：

[1] 丁琳, 譚敏生, 肖煒. 復(fù)雜網(wǎng)絡(luò)抗毀性研究綜述[J]. 網(wǎng)絡(luò)通訊及安全, 2009, 5(1): 51-61.

DING Lin, TAN Min-sheng, XIAO Wei. Reaserch Summarize About Anti-Destroying of Complex Network[J].Network Communication an Safe,2009,5(1):51-61.

[2] 譚躍進, 吳俊, 鄧宏鐘, 等. 復(fù)雜網(wǎng)絡(luò)抗毀性研究綜述[J]. 系統(tǒng)工程, 2006, 24(10): 1-5.

TAN Yue-jing, WU Jun, DENG Hong-zhong,et al. Reaserch Summarize About Anti-Destroying of Complex Network[J]. System Engineering，2006, 24(10): 1-5.

[3] 潘麗君，范銳，王精業(yè).基于作戰(zhàn)仿真的軍用通信網(wǎng)絡(luò)戰(zhàn)時抗毀性研究[J].計算機工程，2010，6(5)：4-7.

PAN Li-jun,FAN Rui,WANG Jing-ye. Wartime Anti-Destroying Ability Based on Combat Simulation of Military Communication Network Research[J]. Computer Engineering，2010，6(5)：4-7.

[4] 張琨，談革新，莊克琛.復(fù)雜網(wǎng)絡(luò)抗毀性測度研究綜述[J]. 計算機時代，2006，32(22)：111-113.

ZHANG Kun，TAN Ge-xin，ZHUANG Ke-chen.Reaserch Summarize Network About Anti-Destroying of Complex Network[J].Computer Time,2006,32(22):111-113.

[5] 譚躍進, 吳俊, 鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點重要度評估的節(jié)點收縮方法[J].系統(tǒng)工程理論與實踐, 2006,11(11):79-83.

TAN Yue-jin，WU Jun,DENG Hong-zhong. Shrinkage Method for Node Important Degree Evaluation of Complex Network[J]. Systems Engineering Theory and Practice, 2006, 11(11):79-83.

[6] 張翼，劉玉華，許凱華，等.一種基于互信息的復(fù)雜網(wǎng)絡(luò)節(jié)點重要性評估方法[J].計算機科學(xué)，2011，38(6)：88-89.

ZHANG Yi,LIU Yu-hua,XU Kai-hua,et al.A Kind of Complex Network Node Importance Evaluation Method Based on Mutual Information[J]. Computer Science,2011, 38(6)：88-89.

[7] ENRICO N, GUIDO P, PETER W Finding the Most Vital Node of a Shortest Path [J].The Oretical Computer Science,2003,29(6):278-287.

[8] 邱原，邢煥革.基于復(fù)雜理論的作戰(zhàn)網(wǎng)絡(luò)關(guān)鍵邊評估方法[J].兵工自動化，2011，30(8)：22-26.

QIU Yuan,XIN Huan-Ge. Operational Key-Edge Network Evaluation Method Based on the Theory of the Complex[J]. Weapons Industry and Automation, 2011，30(8)：22-26.

[9] WEST D B. Introduction to Graph Theory[M].Englewood Cliffs: Prentice Hall, 2001.

[10] CALLAWAYDS, NEWMANMEJ, STROGATEZSH, et al. Network Robustness and Fragility: Percolation on Random Graphs[J] . Phys. Rev. Lett., 2000, 85(25): 5468-5471.

[11] 陳靜, 孫林夫.復(fù)雜網(wǎng)絡(luò)中節(jié)點重要度評估[J]. 西南交通大學(xué)學(xué)報, 2009, 44(3): 426-429.

CHEN Jing，SUN Lin-fu. The Evluation of Important Degree about Nodes in Complex Network[J]. Journal of Southwest Jiaotong University, 2009, 44(3): 426-429.

[12] FREEMAN L C. A set of Measures of Centrality Based upon Betweenness[J]. Sociometry, 1977, 40(1): 35-41.

[13] 陳勇,胡愛群,胡俊，等. 通信網(wǎng)絡(luò)中最重要節(jié)點確定方法[J]. 高技術(shù)通訊, 2004(1): 573-575.

CHEN Yong,HU Ai-qun,HU Jun， et al. The Determine Method of the Most Important Node in Communication Network[J].High Technology Commution, 2004(1): 573-575.