艦船通信網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜性實(shí)證分析?

梅 丹 王公寶 胡偉文 張建軍

（海軍工程大學(xué)應(yīng)用數(shù)學(xué)系 武漢 430033）

1 引言

艦船通信網(wǎng)絡(luò)是為保障作戰(zhàn)指揮、武器控制、協(xié)同動(dòng)作、后方勤務(wù)、警報(bào)和情報(bào)報(bào)知、裝備保障等信息的傳輸與交換而建立的網(wǎng)絡(luò)體系，是信息系統(tǒng)的重要組成部分［1］。艦船通信網(wǎng)絡(luò)日趨呈現(xiàn)復(fù)雜性的特點(diǎn)，對(duì)其進(jìn)行研究是否可以采取復(fù)雜網(wǎng)絡(luò)的研究思路呢？由此而生成的網(wǎng)絡(luò)結(jié)構(gòu)模型是否符合復(fù)雜網(wǎng)絡(luò)的基本特征？復(fù)雜性特征對(duì)現(xiàn)實(shí)艦船通信系統(tǒng)建設(shè)又有何幫助？本文針對(duì)上述問(wèn)題，從復(fù)雜網(wǎng)絡(luò)角度出發(fā)，用鄰接矩陣表示某艦船通信網(wǎng)絡(luò)拓?fù)淠Ｐ停⒎抡嬗?jì)算了該網(wǎng)絡(luò)的平均路徑長(zhǎng)度、聚類系數(shù)等統(tǒng)計(jì)特性指標(biāo)，驗(yàn)證了該通信網(wǎng)絡(luò)的小世界特性。該結(jié)論為將復(fù)雜網(wǎng)絡(luò)的研究成果運(yùn)用到未來(lái)軍事系統(tǒng)建設(shè)中提供了積極的理論啟示和參考價(jià)值。

2 復(fù)雜網(wǎng)絡(luò)理論

2.1 復(fù)雜系統(tǒng)網(wǎng)絡(luò)模型

現(xiàn)實(shí)世界中大多數(shù)復(fù)雜系統(tǒng)可以用網(wǎng)絡(luò)模型來(lái)描述，例如規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)［2］。規(guī)則網(wǎng)絡(luò)所能描述的系統(tǒng)范圍極其有限；隨機(jī)網(wǎng)絡(luò)的隨機(jī)性十分符合真實(shí)網(wǎng)絡(luò)中連接的某些特性，但是對(duì)動(dòng)態(tài)演化系統(tǒng)所表示出來(lái)的一些特性卻無(wú)法予以說(shuō)明。1998年，Watts和Strogatz通過(guò)以某個(gè)很小的概率p切斷規(guī)則網(wǎng)絡(luò)中原始的邊，并隨機(jī)選擇新的節(jié)點(diǎn)重新連接，構(gòu)造出一種介于規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的小世界網(wǎng)絡(luò)［3］。小世界網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)的一種重要模型。此外，復(fù)雜網(wǎng)絡(luò)模型還包括無(wú)標(biāo)度網(wǎng)絡(luò)、局部演化網(wǎng)絡(luò)等。關(guān)于復(fù)雜網(wǎng)絡(luò)更為詳細(xì)的描述參見文獻(xiàn)［4］。

2.2 復(fù)雜網(wǎng)絡(luò)的特征參數(shù)

對(duì)于一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)G＝（V，E），其中V表示節(jié)點(diǎn)的集合，E表示邊的集合。經(jīng)典復(fù)雜網(wǎng)絡(luò)理論中定義了以下四個(gè)重要參數(shù)［5］來(lái)描述網(wǎng)絡(luò)特性：

1）平均路徑長(zhǎng)度L

在一個(gè)網(wǎng)絡(luò)中，兩個(gè)節(jié)點(diǎn)i、j間的最短距離dij定義為連接這兩個(gè)節(jié)點(diǎn)的最短路徑上的邊數(shù)。對(duì)所有節(jié)點(diǎn)對(duì)的最短距離求平均值，就得到了該網(wǎng)絡(luò)的平均路徑長(zhǎng)度：

它是以邊長(zhǎng)作為長(zhǎng)度單位進(jìn)行度量的拓?fù)渚嚯x。路徑長(zhǎng)度的分布是所有節(jié)點(diǎn)對(duì)之間最短路徑的統(tǒng)計(jì)分布特性。平均路徑長(zhǎng)度是網(wǎng)絡(luò)的特征尺度，可以表征網(wǎng)絡(luò)的連通性。

2）聚類系數(shù)C

復(fù)雜網(wǎng)絡(luò)具有高度的集團(tuán)性，網(wǎng)絡(luò)的聚類系數(shù)C是專門用來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)集聚程度的一個(gè)重要參數(shù)。在網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)的聚類系數(shù)可表示為

式中，ai為連接節(jié)點(diǎn)i的三角形的個(gè)數(shù)，bi為連接節(jié)點(diǎn)i的三元組的個(gè)數(shù)。比較直觀的定義方法為：假設(shè)節(jié)點(diǎn)i有ki個(gè)近鄰節(jié)點(diǎn)，則ki個(gè)近鄰節(jié)點(diǎn)之間至多存在ki（ki－1）／2條邊，而ki個(gè)近鄰節(jié)點(diǎn)之間實(shí)際存在ti條邊，則節(jié)點(diǎn)i的聚類系數(shù)為

聚類系數(shù)表征了近鄰節(jié)點(diǎn)聯(lián)系的緊密程度，進(jìn)一步對(duì)所有節(jié)點(diǎn)的聚類系數(shù)求均值就可以得到網(wǎng)絡(luò)的聚類系數(shù)：

3）度數(shù)及度分布

節(jié)點(diǎn)i的度定義為與該節(jié)點(diǎn)連接的其他節(jié)點(diǎn)的數(shù)目，即與節(jié)點(diǎn)i關(guān)聯(lián)的邊的數(shù)目，記為ki。

網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的平均值稱為網(wǎng)絡(luò)的平均度，記為〈k〉。對(duì)于一個(gè)邊數(shù)為M，節(jié)點(diǎn)數(shù)為N的網(wǎng)絡(luò)，其平均度數(shù)為〈k〉＝2 M／N。

分析度分布的傳統(tǒng)方法是直接畫出頂點(diǎn)度數(shù)的直方圖，這種方法的缺點(diǎn)是直方圖的寬度平滑，會(huì)使得落入同一直方內(nèi)的數(shù)據(jù)點(diǎn)的值間差異全部喪失。現(xiàn)在使用較多的考察復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)度分布的一個(gè)可行方法是采用累積分布函數(shù)法。這里，定義p（k）表示度數(shù)為k的節(jié)點(diǎn)個(gè)數(shù)n（k）占節(jié)點(diǎn)總數(shù)N的百分比，易知度數(shù)概率分布具有完備性：

其中，kmin和kmax分別表示網(wǎng)絡(luò)中節(jié)點(diǎn)度數(shù)的最小值和最大值。同時(shí)定義節(jié)點(diǎn)度數(shù)累積分布函數(shù)（Cumulative Degree Distribution Function）Pc（k），用P（k≥K）表示度不小于K的節(jié)點(diǎn)的概率分布，常數(shù)K∈［kmin，kmax］，則節(jié)點(diǎn)度數(shù)的累積概率就可以表示為

根據(jù)隨機(jī)網(wǎng)絡(luò)理論，復(fù)雜網(wǎng)絡(luò)的度分布服從二項(xiàng)分布或大N極限下的泊松分布，其特征是網(wǎng)絡(luò)中絕大多數(shù)節(jié)點(diǎn)的度值分布在均值附近，在此意義下，復(fù)雜網(wǎng)絡(luò)是均質(zhì)網(wǎng)絡(luò)。

4）介數(shù)及介數(shù)分布

Holme和Kim在研究網(wǎng)絡(luò)演化所導(dǎo)致的過(guò)負(fù)荷時(shí)，假設(shè)網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)之間信息或能量的交換都通過(guò)最短路徑進(jìn)行，選擇用介向中心性（Betweennes Centrality）來(lái)評(píng)估網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊的網(wǎng)絡(luò)流量［6～8］，其后介向中心性也被簡(jiǎn)單地稱為介數(shù)（betweenness）。節(jié)點(diǎn)v的介數(shù)B（v）和邊e的介數(shù)B（e）表達(dá)式類似，可分別定義為

式中，對(duì)于w≠w′且w，w′≠v的所有節(jié)點(diǎn)對(duì)，σww′為節(jié)點(diǎn)w、w′之間的最短路徑數(shù)目，σww′（v）為 w、w′之間經(jīng)過(guò)v的最短路徑數(shù)目；σvw（e）為節(jié)點(diǎn)v、w之間包含邊e的最短路徑數(shù)目，σvw為節(jié)點(diǎn)v、w之間的最短路徑數(shù)目。

定義節(jié)點(diǎn)（邊）介數(shù)累積分布函數(shù)（Cumulative Betweenness Distribution Function）為 Pc（B），用P（B≥B′）表示介數(shù)不小于B′的節(jié)點(diǎn)（邊）的概率分布，Bmax表示網(wǎng)絡(luò)中節(jié)點(diǎn)（邊）介數(shù)的最大值，常數(shù)B′∈［Bmin，Bmax］，節(jié)點(diǎn)（邊）介數(shù)的累積概率就可表示為

3 艦船通信網(wǎng)絡(luò)結(jié)構(gòu)及其拓?fù)淠Ｐ?/h2>

采用復(fù)雜網(wǎng)絡(luò)理論研究艦船通信系統(tǒng)特性，要將通信網(wǎng)絡(luò)簡(jiǎn)化為拓?fù)淠Ｐ汀Ｔ谶@里，各個(gè)通信實(shí)體簡(jiǎn)化為節(jié)點(diǎn)；由于通信實(shí)體之間存在信息的傳輸與交換，連線代表兩個(gè)通信實(shí)體之間有直接的通信聯(lián)系。圖1為某艦船通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，出于保密要求，該圖為經(jīng)過(guò)適當(dāng)處理后的部分拓?fù)浣Y(jié)構(gòu)圖。

為了方便計(jì)算機(jī)進(jìn)行處理，用鄰接矩陣A對(duì)網(wǎng)絡(luò)拓?fù)淠Ｐ瓦M(jìn)行表示，A中元素aij規(guī)定為：aij＝1，當(dāng)節(jié)點(diǎn)i與j相鄰；aij＝0，當(dāng)節(jié)點(diǎn)i與j不相鄰。

圖1 某艦船通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖（部分）

4 艦船通信網(wǎng)絡(luò)復(fù)雜性分析

在Watts和Strogatz關(guān)于復(fù)雜網(wǎng)絡(luò)的小世界現(xiàn)象的研究，以及Barabasi和Albert關(guān)于復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度特性的工作之后，人們對(duì)不同領(lǐng)域的大量實(shí)際網(wǎng)絡(luò)的拓?fù)涮匦赃M(jìn)行了廣泛的實(shí)證性研究，得到了各個(gè)領(lǐng)域、各種實(shí)際網(wǎng)絡(luò)的各項(xiàng)基本統(tǒng)計(jì)數(shù)據(jù)［9］。如社會(huì)領(lǐng)域中電子郵件網(wǎng)絡(luò)的平均路徑長(zhǎng)度L＝2.0，聚類系數(shù)C＝0.16；信息領(lǐng)域 WWW（nd.edu）網(wǎng)絡(luò)的平均路徑長(zhǎng)度L＝2.4，聚類系數(shù)C＝0.29。這兩種網(wǎng)絡(luò)具有類似于規(guī)則網(wǎng)絡(luò)的較高聚類系數(shù)和類似于隨機(jī)網(wǎng)絡(luò)的較小平均路徑長(zhǎng)度，即小世界特性。

由式（1）和式（2）可以計(jì)算出某艦船通信網(wǎng)絡(luò)的平均路徑長(zhǎng)度L＝2.4318和聚類系數(shù)C＝0.1934。通過(guò)與電子郵件網(wǎng)絡(luò)和信息領(lǐng)域網(wǎng)絡(luò)的平均路徑長(zhǎng)度值和聚類系數(shù)值進(jìn)行比較，發(fā)現(xiàn)某艦船信息化網(wǎng)絡(luò)的統(tǒng)計(jì)數(shù)據(jù)與上述兩種網(wǎng)絡(luò)的數(shù)據(jù)接近。進(jìn)一步驗(yàn)證了某艦船通信網(wǎng)絡(luò)也具有小世界特性。可以看到，某艦船通信網(wǎng)絡(luò)具有較短的平均路徑長(zhǎng)度，說(shuō)明網(wǎng)絡(luò)中信息的流動(dòng)比較順利。這也使得軍事網(wǎng)絡(luò)為各作戰(zhàn)單元提供迅速、準(zhǔn)確、有效的通信支撐。

通過(guò)計(jì)算，上述某艦船通信網(wǎng)絡(luò)節(jié)點(diǎn)的度分布如圖2所示。在這里，節(jié)點(diǎn)的度即為通信實(shí)體直接進(jìn)行信息交換的通信實(shí)體數(shù)目。

由圖2可見，第14號(hào)節(jié)點(diǎn)的度為4，在整個(gè)網(wǎng)絡(luò)中最大。這意味著該節(jié)點(diǎn)與其他節(jié)點(diǎn)的聯(lián)系比較緊密，十分重要。也就是說(shuō)該節(jié)點(diǎn)受到攻擊或者損害會(huì)造成網(wǎng)絡(luò)的級(jí)聯(lián)故障，甚至造成整個(gè)網(wǎng)絡(luò)的癱瘓［10］。通信節(jié)點(diǎn)的重要性還可以從介數(shù)指標(biāo)上得到驗(yàn)證。如圖3所示，14號(hào)節(jié)點(diǎn)的介數(shù)最大。節(jié)點(diǎn)的介數(shù)值越高，說(shuō)明該節(jié)點(diǎn)的影響力越大，地位也越重要。

圖2 某艦船通信網(wǎng)絡(luò)節(jié)點(diǎn)度分布

圖3 某艦船通信網(wǎng)絡(luò)節(jié)點(diǎn)介數(shù)

5 結(jié)語(yǔ)

本文首先介紹了復(fù)雜網(wǎng)絡(luò)理論，重點(diǎn)闡述了復(fù)雜網(wǎng)絡(luò)的四個(gè)度量參數(shù)：平均路徑長(zhǎng)度、聚類系數(shù)、度數(shù)、介數(shù)；然后將某艦船通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行了抽象表示，并用鄰接矩陣表示了各通信實(shí)體之間的通信聯(lián)絡(luò)關(guān)系；最后通過(guò)仿真計(jì)算了該通信網(wǎng)的各項(xiàng)基本參數(shù)。計(jì)算結(jié)果表明，某艦船通信網(wǎng)絡(luò)具有復(fù)雜網(wǎng)絡(luò)的小世界特性。復(fù)雜網(wǎng)絡(luò)提供了一種全新的視角，幫助我們從整體上把握軍事通信網(wǎng)絡(luò)的復(fù)雜性，更好地認(rèn)識(shí)其拓?fù)浣Y(jié)構(gòu)及相應(yīng)的動(dòng)力學(xué)特征。

［1］李德毅，王新政，胡剛鋒.網(wǎng)絡(luò)化戰(zhàn)爭(zhēng)與復(fù)雜網(wǎng)絡(luò)［J］.中國(guó)軍事科學(xué)，2006，19（3）：111－119.

［2］Erdos P，Renyi A L.On the evolution of random graphs.Publ［J］.Math.Inst.Hung.Acad.Sci.，1960，5：17－60.

［3］Watts D J，Strogatz S H.Collective dynamics of‘small－world’networks［J］.Nature，1998，393（6684）：440－442.

［4］Albert R，Barabasi A L.Statistical mechanics of complex networks［J］.Review of Modern Physics，2002，74（1）：47－97.

［5］汪小帆.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，2006.

［6］Holme P.Edge overload breakdown in evolving networks［J］.Physical Review E，2002，66（2）：036119.

［7］Holme P，Kim B J.Vertex breakdown in evolving networks［J］.Physical Review E，2002，65（1）：066109.

［8］Holme P，Kim B J，et al.Attack vulnerability of complex networks［J］.Physical Review E，2002，65（1）：056109.

［9］Newman M E J.The structure and Function of Com－plex Networks［J］.SIAM Review，2003（45）：167－256.

［10］Crucitti P，Latora V，Marchiori M.Model for cascading failures in complex networks［J］.Physics Review E，2004（69）：045104.