艦艇編隊協同反導網絡節點重要度評估*

夏昱，滕克難，陳健

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

0 引言

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

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

本文首先定義了網絡節點接近度和關聯度，然后定義了節點的重要度。在此基礎上給出了節點重要度評估方法及其算法，該方法結合了節點在復雜網路中的重要性，通過艦艇編隊協同反導網絡分析驗證了該方法的有效性。

1 評估模型

1.1 節點介數

節點介數衡量了網絡中所有的最短路徑中經過該節點的數量比例，定義為

(1)

式中:σij(k)為節點i和j之間最短路徑經過節點k的數目；σij為節點i和j之間最短路徑的總數；V為網絡節點集合。

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

1.2 節點接近度

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

(2)

復雜網絡本質上的非同質拓撲結構，決定了網絡中每個節點的重要程度是不同的。節點在復雜網絡中的重要度首先取決于節點在網絡中的位置，根據式(2)可知，節點接近度C(i)越大，節點越居于網絡中心，節點在全局網絡中越重要。

1.3 節點關聯度

灰色關聯分析對系統數據序列幾何關系和曲線幾何形狀的相似程度進行比較，以曲線間相似程度大小作為關聯程度的衡量尺度。一組幾何曲線形狀越相似，則相應序列之間的關聯度越大，反之則越小。由此為所考察的復雜系統綜合決策提供信息。

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

1.3.1 虛擬理想“核心節點”的確定

在復雜網絡中，最理想的“核心節點”是與網絡中每個節點都有邊相連的節點，設其與每個節點的連接關系所構成的序列X0={X0(k)|k=1,2,…,n}(n為網絡中的節點數)作為參考序列，比較序列為網絡中每個節點與其余節點的連接關系所構成的序列：

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

1.3.2 關聯系數的計算

關聯系數是灰色關聯分析中用于表示待評序列與參考序列接近程度的數值，值越大，表示接近程度越高，即越接近虛擬的理想“核心節點”，這樣的節點即為網絡中重要的“核心節點”。

比較序列Xi對于參考序列X0在k點的關聯系數為

ξi(k)=

(3)

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

1.3.3 關聯度計算

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

(4)

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

1.4 節點的重要度

1.4.1 節點重要度定義

為全面評價網絡中節點的重要度，綜合考慮節點的介數、接近度和關聯度的影響，將節點vi的重要度定義為

(5)

K(i)越大，節點在網絡中越重要。

1.4.2 節點重要度算法步驟

復雜網絡中節點重要度評估的算法流程如下：

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

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

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

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

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

(3) 計算節點vi關聯度A(i)

1) 選取參考序列X0={X0(k)=1|k=1,2,…,n,n為網絡中的節點數}；

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

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

3) 根據式(3)計算比較序列Xi對于參考序列X0在k點的關聯系數ξi(k)；

4) 根據式(4)計算節點vi的關聯度A(i)。

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

2 艦艇編隊協同反導網絡模型

2.1 模型仿真算例

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

這樣整個艦艇編隊協同反導作戰網絡的拓撲結構如圖1所示。

圖1 傳感器之間和影響器之間采用NW小世界網絡連接且決策器之間BA無標度網絡連接的艦艇編隊協同反導網絡拓撲結構圖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 模型參數分析

傳感器之間和影響器之間采用NW小世界網絡連接,決策器之間采用BA無標度網絡連接構建的艦艇編隊反導作戰網絡，利用Pajek軟件得到該網絡模型的特征參數如表1所示。模型各節點的度分布如圖2所示，其中節點1～5為目標節點，節點6～25為傳感器節點，節點26～35為決策器節點，節點36～55為影響器節點。

圖2 艦艇編隊協同反導網絡的度分布圖Fig.2 Degree distribution of fleet cooperation antimissile network

3 艦艇編隊協同反導網絡節點重要度評估

根據1.4.2節中網絡節點重要度評估的算法流程，計算艦艇編隊協同反導網絡中所有55個節點的重要度。表2給出了所有節點的重要度評估結果。

表1 艦艇編隊協同反導網絡模型參數Table 1 Model parameters of fleet cooperation antimissile network

表2 艦艇編隊協同反導網絡重要度評估結果

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

4 結束語

本文中針對有向網絡提出了基于節點接近度及關聯度評估節點在復雜網絡中的重要度方法，定義了節點的接近度、關聯度及重要度，全面綜合地描述了節點在復雜網絡中的重要性，針對艦艇編隊協同反導網絡中節點的重要度，證明了該方法的有效性。

參考文獻：

[1] 丁琳, 譚敏生, 肖煒. 復雜網絡抗毀性研究綜述[J]. 網絡通訊及安全, 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] 譚躍進, 吳俊, 鄧宏鐘, 等. 復雜網絡抗毀性研究綜述[J]. 系統工程, 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] 潘麗君，范銳，王精業.基于作戰仿真的軍用通信網絡戰時抗毀性研究[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] 張琨，談革新，莊克琛.復雜網絡抗毀性測度研究綜述[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] 譚躍進, 吳俊, 鄧宏鐘.復雜網絡中節點重要度評估的節點收縮方法[J].系統工程理論與實踐, 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] 張翼，劉玉華，許凱華，等.一種基于互信息的復雜網絡節點重要性評估方法[J].計算機科學，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] 邱原，邢煥革.基于復雜理論的作戰網絡關鍵邊評估方法[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] 陳靜, 孫林夫.復雜網絡中節點重要度評估[J]. 西南交通大學學報, 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] 陳勇,胡愛群,胡俊，等. 通信網絡中最重要節點確定方法[J]. 高技術通訊, 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.