馬 瑩，陳志龍，劉 賀，趙銅星

(1.陸軍工程大學(xué) 國防工程學(xué)院，江蘇 南京 210007；2.海峽之聲廣播電臺，福建 福州 350000；3.解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院，江蘇 南京 210007)

0 引言

最短路徑問題是求解復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點的關(guān)鍵，是評價復(fù)雜網(wǎng)絡(luò)的一個重要特征，特別是大規(guī)模網(wǎng)絡(luò)的最短路徑問題一直是亟待解決的難題。如何對節(jié)點的重要性進(jìn)行有效評估并發(fā)現(xiàn)與實際情況相符的關(guān)鍵節(jié)點成為當(dāng)前研究的重點和熱點。張德全等人提出了不含負(fù)回路的網(wǎng)絡(luò)中 Floyd 加速算法及優(yōu)化方法，并構(gòu)造了求解最短路徑的序號矩陣[1]。王運明等人針對目前指揮控制網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法利用局部信息識別精度低、利用全局信息識別復(fù)雜度高的問題，提出了一種面向結(jié)構(gòu)洞的指揮控制網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法[2]。嚴(yán)棟等人根據(jù)主觀與客觀賦權(quán)的特點，把熵權(quán)法的思想運用到AHP 算法，建立了新的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法[3]。左秀峰等人針對最短路問題中存在多條等價最短路徑的問題，基于Floyd設(shè)計出新的搜索算法，在迭代更新距離矩陣與路徑矩陣的基礎(chǔ)上求出所有等價最短路徑[4]。HU P從節(jié)點的初始重要性以及相鄰節(jié)點和非相鄰節(jié)點之間的相互依賴強度所做的重要貢獻(xiàn)兩個角度提出了一種新的節(jié)點重要性評價方法，并將其應(yīng)用于電子郵件網(wǎng)絡(luò)[5]。周漩等人通過定義節(jié)點效率和節(jié)點重要度評價矩陣,提出了一種利用重要度評價矩陣來確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點的方法[6]。曾瑛等人利用電網(wǎng)影響因子,并結(jié)合所定義的聚合系數(shù)指標(biāo),分析電力通信網(wǎng)中重要節(jié)點的分布密集狀況,得到各節(jié)點在網(wǎng)絡(luò)拓?fù)渲械南鄬χ匾訹7]。張喜平等人引入m階鄰居節(jié)點的概念,提出了一種基于m階鄰居節(jié)點重要度貢獻(xiàn)的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度方法,并引入α和γ兩個參數(shù),用于調(diào)節(jié)節(jié)點重要度評估對節(jié)點自身特性及m階鄰居節(jié)點的依賴程度[8]。李鵬飛等針對傳統(tǒng)關(guān)鍵節(jié)點識別方法不能適應(yīng)Ad hoc網(wǎng)絡(luò)拓?fù)鋭討B(tài)性、計算復(fù)雜度高的問題,提出一種基于網(wǎng)絡(luò)連通性和節(jié)點刪除法相結(jié)合的關(guān)鍵節(jié)點識別方法[9]。

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

就目前研究現(xiàn)狀來看，對多層系統(tǒng)復(fù)雜網(wǎng)絡(luò)的研究僅限于概念層面，在建模方式上采用單一類型的網(wǎng)絡(luò)，各子網(wǎng)要么均是隨機網(wǎng)絡(luò)，要么均是無標(biāo)度網(wǎng)絡(luò)，沒有區(qū)分子網(wǎng)的不同類型，而在實際網(wǎng)絡(luò)中，尤其是多層系統(tǒng)網(wǎng)絡(luò)，由于其復(fù)雜性而不可能存在單一的網(wǎng)絡(luò)連接方式。

針對這一問題，基于多層現(xiàn)實系統(tǒng)本體，區(qū)分出不同類型的網(wǎng)絡(luò)節(jié)點形式，并由核心層節(jié)點出發(fā)按各類網(wǎng)絡(luò)形式進(jìn)行輻射式構(gòu)建。在各子網(wǎng)間采用確定性連接與隨機性連接共存的混合連接方式構(gòu)建多層復(fù)雜系統(tǒng)網(wǎng)絡(luò)。

在確定性連接中存在“擇優(yōu)”與“扶貧”兩種連接方式，新的節(jié)點可能加到核心節(jié)點比較強的節(jié)點之下，使“強者更強”；也可能補充到功能較弱或者已經(jīng)被嚴(yán)重削弱的節(jié)點之下，彌補某個功能的不足。

在隨機性連接中又存在ER隨機網(wǎng)絡(luò)連接[10]和BA無標(biāo)度網(wǎng)絡(luò)連接兩種方式[11]，連接方法如下。

(1)ER隨機網(wǎng)絡(luò)連接：每次都從N1個核心網(wǎng)絡(luò)節(jié)點中隨機選擇一個節(jié)點與新加入的子網(wǎng)節(jié)點連接，直到所有的隨機連接節(jié)點全部連接到網(wǎng)絡(luò)中。

(2)BA無標(biāo)度網(wǎng)絡(luò)連接：新加入的節(jié)點與一個已經(jīng)存在的核心網(wǎng)絡(luò)節(jié)點i以概率Pi連接:

(1)

從而，本文定義了反映網(wǎng)絡(luò)形式的三個比率：

其中t為總連接數(shù)；d為確定性連接數(shù)；r為隨機性連接數(shù)；s為確定性擇優(yōu)連接數(shù)；h為確定性扶貧連接數(shù)；b為BA無標(biāo)度網(wǎng)絡(luò)連接數(shù)；e為ER隨機網(wǎng)絡(luò)連接數(shù)；它們存在的關(guān)系為：t=d+r，d=s+h，r=b+e。

當(dāng)dt=br=0,sd無限制時，退化為ER隨機網(wǎng)絡(luò)連接；

當(dāng)dt=0,br=1,sd無限制時，退化為BA無標(biāo)度網(wǎng)絡(luò)連接；

當(dāng)dr=1,sd=1,br無限制時，為完全確定性擇優(yōu)連接；

當(dāng)dr=1,sd=0,br無限制時，為完全確定性扶貧連接。

用這三個比率可以靈活控制網(wǎng)絡(luò)的連接規(guī)律，從而生成不同的網(wǎng)絡(luò)模型。因此，混合連接多層網(wǎng)絡(luò)模型構(gòu)建方法如下：

步驟1 核心層節(jié)點標(biāo)號, 確定3個混合比率(dtf,sdf,brf)；

步驟2 對每個新加入子網(wǎng)，生成m以內(nèi)的隨機數(shù)，代表該點的連邊數(shù)；

步驟3 生成d=Nn×dt個節(jié)點進(jìn)行確定性連接；

步驟4 按照核心節(jié)點的度值大小從大到小排序，將s=d×sd個新子網(wǎng)節(jié)點連接到前s個核心節(jié)點，將h=d×(1-sd)個新子網(wǎng)節(jié)點連接到后h個核心節(jié)點；

步驟5 生成r=Nn×(1-dt)個節(jié)點進(jìn)行隨機性連接；

步驟6 將b=r×brf個節(jié)點按照BA無標(biāo)度網(wǎng)絡(luò)規(guī)則連接到核心節(jié)點上；將g=r×(1-brf)個節(jié)點按照ER隨機網(wǎng)絡(luò)規(guī)則連接到核心節(jié)點上；

步驟7 新子網(wǎng)節(jié)點按概率Sh進(jìn)行ER隨機連接。

基于Netlogo仿真平臺構(gòu)建出的多層系統(tǒng)網(wǎng)絡(luò)模型有15個參數(shù)，具有很強的適用性，不同參數(shù)靈活組合可有成千上萬種變化，可以生成各種類型的目標(biāo)體系網(wǎng)絡(luò)模型。由于系統(tǒng)網(wǎng)絡(luò)模型的建模過程是基于核心層級輻射式建立的，因此該模型不僅能夠研究整個系統(tǒng)網(wǎng)絡(luò)的特征，也可以單獨研究其中某個子網(wǎng)絡(luò)的特征。

2 最短路徑算法研究

傳統(tǒng)的求解最短路徑的算法主要有Dijkstra算法和Floyd算法，其中Dijkstra算法是計算網(wǎng)絡(luò)中一個節(jié)點到其他所有節(jié)點的最短路徑的高效算法，而Floyd算法是計算網(wǎng)絡(luò)中所有節(jié)點之間最短路徑的經(jīng)典算法。

因此，本文針對無向無權(quán)的復(fù)雜網(wǎng)絡(luò)，從這三點出發(fā)進(jìn)行優(yōu)化，提出了改進(jìn)的級聯(lián)失效算法，從而極大地提高計算效率。算法的優(yōu)化思路如下：

(1)無向無權(quán)網(wǎng)絡(luò)的距離矩陣D為對稱矩陣，所以有dij=dji，求得dij后直接賦值給dji即可，不需要再計算dji，即在算法的最內(nèi)層循環(huán)中，j不需要從1開始計算，而是從i+1開始計算，這樣j的平均計算次數(shù)減少為(n-1)/2，而且剔除了i=j的情況。

(2)當(dāng)k=i或k=j時，節(jié)點通過自身到達(dá)另一節(jié)點，長度沒有變化，不需要計算，i和j直接遞增。

(4)因為網(wǎng)絡(luò)直徑R在運算結(jié)束前為未知數(shù)，所以設(shè)定一個變量C來表示還未找到最短路徑的節(jié)點對數(shù)量，當(dāng)dij改變時，變量C減2，當(dāng)C=0時，所有節(jié)點之間的最短路徑已經(jīng)找到，算法終止。

因此，假定網(wǎng)絡(luò)中的節(jié)點數(shù)為n，關(guān)鍵節(jié)點評價算法的實現(xiàn)步驟如下：

令C為不相鄰的節(jié)點對總數(shù)。

步驟3：若C=0，則迭代結(jié)束；否則r=r+1，返回步驟2。

3 算法復(fù)雜性分析

改進(jìn)的Floyd加速算法共有四層循環(huán)，其中最外層r的循環(huán)次數(shù)為R-1，第二層k的循環(huán)次數(shù)為n，第三層i的平均循環(huán)次數(shù)為2L/n，其中L為邊數(shù)，第四層j的平均循環(huán)次數(shù)為(n-1)/2，算法總的復(fù)雜度為O((R-1)n(2L/n)(n-1)/2)=O((R-1)L(n-1))≈O(RLn)。通過分析可以看出，改進(jìn)的Floyd加速算法的計算復(fù)雜度與網(wǎng)絡(luò)直徑R和邊數(shù)L有關(guān)，當(dāng)R<

當(dāng)網(wǎng)絡(luò)的節(jié)點數(shù)n固定時，要使網(wǎng)絡(luò)連通，邊數(shù)L至少為n-1，此時網(wǎng)絡(luò)的直徑R=n-1， Floyd加速算法的計算復(fù)雜度為O((n-1)(n-1)n)≈O(n3)；當(dāng)網(wǎng)絡(luò)為完全連接網(wǎng)絡(luò)時L=n(n-1)/2，網(wǎng)絡(luò)直徑R=1，此時的計算復(fù)雜度為O(n2(n-1)/2)≈O(n3/2)。而該算法的最優(yōu)計算復(fù)雜度約為O(n2)，所以隨著網(wǎng)絡(luò)連接邊數(shù)的增加，該算法的計算復(fù)雜度先減小后增大。

4 算法優(yōu)越性驗證

在Netlogo中生成節(jié)點數(shù)為10的某地域通信網(wǎng)干線節(jié)點拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)模型如圖1所示，下面計算所有節(jié)點間的最短路徑長度。

圖1 某地域通信網(wǎng)干線節(jié)點拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)圖

解：由圖1得到初始距離矩陣：

不相鄰的節(jié)點對數(shù)C=50

當(dāng)r=1，k=1時：

i=3，j=6，d36=1<2不變，j=7，d37=1<2不變，j=8，d38=>2，d38=d83=2；i=6，j=7，d67=>2，d67=d76=2，j=8，d68=>2，d68=d86=2；i=7，j=8，d78=>2，d78=d87=2；

當(dāng)r=1，k=2時：

i=4，j=6，d46=>2 ，d46=d64=2，j=8，d48=1<2不變，j=9，d49=>2，d49=d94=2；i=6，j=8，d68=2不變，j=9，d69=>2，d69=d96=2；i=8，j=9，d89=>2，d89=d98=2；

當(dāng)r=1，k=3時：

i=1，j=4，d14=>2 ，d14=d41=2，j=5，d15=>2，d14=d41=2，j=6，d16=1<2不變，j=7，d17=1<2不變，j=9，d19=>2，d19=d91=2；i=4，j=6，d46=2不變，j=7，d47=>2，d47=d74=2，j=9，d49=>2，d49=d94=2；i=5，j=6，d56=>2，d56=d65=2，j=7，d57=1<2不變，j=9，d59=>2，d59=d95=2；i=6，j=9，d69=>2，d69=d96=2；i=7，j=9，d79=1<2不變； ……

得到r=1時的距離矩陣：

當(dāng)r=2，k=1時：

i=3，j=4，d34=1<3不變，j=5，d35=1<3不變，j=9，d39=1<3不變，j=10，d3,10=2<3不變；i=6，j=9，d69=2<3不變，j=10，d6,10=1<3不變；i=7，j=9，d19=1<3不變，j=10，d7,10=>3，d7,10=d10,7=3；……

得到r=2時的距離矩陣:

此時，所有節(jié)點對之間的最短距離都已經(jīng)找到，該網(wǎng)絡(luò)直徑為3，邊數(shù)為20，總的計算次數(shù)T=(3-1)×20×(10-1)=360，而經(jīng)典Floyd算法的計算次數(shù)為1 000，可以看出本文算法極大地降低了計算量。

文獻(xiàn)[12]中的Floyd加速算法的改進(jìn)方法是目前最新、適用性較廣且獲得結(jié)果較好的一種計算節(jié)點間最短路徑長度的方法，為驗證本文算法的優(yōu)越性，分別用Floyd算法、文獻(xiàn)[12]改進(jìn)方法及本文算法求解隨機網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)的平均最短路徑長度來進(jìn)行對比驗證，結(jié)果如表1～3所示。通過比較可以看出，針對最常用的三種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)模型，本文提出的改進(jìn)算法在計算節(jié)點間的最短路徑長度時，其計算復(fù)雜度較之經(jīng)典的Floyd算法和文獻(xiàn)[12]提出的改進(jìn)算法有明顯的降低，而且節(jié)點數(shù)量最大，優(yōu)勢越明顯。將本文提出的改進(jìn)的Floyd加速算法應(yīng)用到實際系統(tǒng)網(wǎng)絡(luò)評價之中，將會極大地提高算法的計算效率，從而提高算法的應(yīng)用價值。

5 結(jié)論

復(fù)雜網(wǎng)絡(luò)作為很多真實網(wǎng)絡(luò)的抽象，為描述和解決實際問題提供了一種途徑。針對多層系統(tǒng)網(wǎng)絡(luò)的研究，本文提出了一種新的輻射式建模方法并用新的改進(jìn)的Floyd加速算法評價了網(wǎng)絡(luò)節(jié)點的重要性。本文所做的工作有以下幾點：首先，分析不同類型的節(jié)點連接方式，提出了混合類型連接方法。其次，以核心網(wǎng)為基礎(chǔ)，輻射式逐層生成系統(tǒng)網(wǎng)絡(luò)模型，提出了一種新的建模方式。最后，使用新提出的改進(jìn)的Floyd加速算法評價了網(wǎng)絡(luò)中節(jié)點的重要性。通過仿真結(jié)果與已有研究結(jié)果進(jìn)行對比，該方法不僅有很好的可靠性，還使得仿真時間縮短，達(dá)到了較好的仿真效果。 本文算法為多層網(wǎng)絡(luò)系統(tǒng)模型的建立和評估提出了一種新的思路，有著很好的理論價值和現(xiàn)實意義。

表1 隨機網(wǎng)絡(luò)模型三種算法復(fù)雜度對比

表2 小世界網(wǎng)絡(luò)模型(重連概率0.2)三種算法復(fù)雜度對比

表5 無標(biāo)度網(wǎng)絡(luò)模型三種算法復(fù)雜度對比

[1] 張德全,吳果林,劉登峰.最短路問題Floyd加速算法與優(yōu)化[J].計算機工程與應(yīng)用,2009,45(17):41-44.

[2] 王運明,王青野,潘成勝,等.面向結(jié)構(gòu)洞的指揮控制網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法[J].火力與指揮控制,2017,42(3):59-63.

[3] 嚴(yán)棟,張世斌,宗康,等.基于AHP-熵權(quán)法的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別方法[J].廣西大學(xué)學(xué)報,2016,41(6):1933-1939.

[4] 左秀峰,沈萬杰.基于Floyd算法的多重最短路問題的改進(jìn)算法[J].計算機科學(xué),2017,44(5):232-234,267.

[5] HU P, FAN W, MEI S. Identifying node importance in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2015, 429: 169-176.

[6] 周漩,張鳳鳴,李克武,等. 利用重要度評價矩陣確定復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點[J].物理學(xué)報，2012,61(5):1-7.

[7] 曾瑛,朱文紅,鄧博仁,等. 基于電網(wǎng)影響因子的電力通信網(wǎng)關(guān)鍵節(jié)點識別[J]. 電力系統(tǒng)保護(hù)與控制,2016,44(2):102-108.

[8] 張喜平,李永樹,劉剛,等. 節(jié)點重要度貢獻(xiàn)的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度評估方法[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2014,11(3):26-32

[9] 李鵬飛,雷迎科. 動態(tài)Ad hoc網(wǎng)絡(luò)關(guān)鍵節(jié)點識別[J].計算機應(yīng)用研究，2017,34(5)：1473-1475.

[10] INSOO S. Small-world and scale-free network models for IoT systems[J]. Mobile Information Systems, 2017(61): 1-9.

[12] 左秀峰,沈萬杰.基于Floyd算法的多重最短路問題的改進(jìn)算法[J].計算機科學(xué),2017,44(5):232-234,267.