基于度值標(biāo)準(zhǔn)差的復(fù)雜網(wǎng)絡(luò)可靠性

李 鍇，何永鋒

(1.裝甲兵工程學(xué)院 技術(shù)保障工程系，北京 100072；2.裝甲兵工程學(xué)院 基礎(chǔ)部，北京 100072)

0 引 言

現(xiàn)階段主要復(fù)雜網(wǎng)絡(luò)模型[1,2]有隨機(jī)網(wǎng)絡(luò)模型、小世界網(wǎng)絡(luò)模型和無標(biāo)度網(wǎng)絡(luò)模型。復(fù)雜網(wǎng)絡(luò)通常作為復(fù)雜系統(tǒng)的抽象模型，包含大量網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)之間具備錯(cuò)綜復(fù)雜的連接關(guān)系。復(fù)雜網(wǎng)絡(luò)的可靠性和抗毀性問題一直受到廣泛關(guān)注[3-5]，研究復(fù)雜網(wǎng)絡(luò)可靠性主要通過移除網(wǎng)絡(luò)節(jié)點(diǎn)和連接邊對網(wǎng)絡(luò)效率及連通度的影響來體現(xiàn)，主要的理論判據(jù)有網(wǎng)絡(luò)熵值和自然連通度[6-8]。本文基于復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)度值的標(biāo)準(zhǔn)差，提出網(wǎng)絡(luò)可靠性函數(shù)的定義，證明網(wǎng)絡(luò)可靠性函數(shù)的收斂性及單調(diào)性，研究隨機(jī)網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)在兩種失效模式下的可靠性變化規(guī)律，驗(yàn)證網(wǎng)絡(luò)可靠性函數(shù)的合理性及有效性。

1 復(fù)雜網(wǎng)絡(luò)模型

復(fù)雜網(wǎng)絡(luò)模型主要經(jīng)歷4個(gè)模型階段：規(guī)則網(wǎng)絡(luò)(regular network)、隨機(jī)網(wǎng)絡(luò)(random network)、小世界網(wǎng)絡(luò)(small-world network)和無標(biāo)度網(wǎng)絡(luò)(scale-free network)。為研究復(fù)雜網(wǎng)絡(luò)模型的拓?fù)浣Y(jié)構(gòu)，專家學(xué)者定義許多特征量，主要有度與度分布、平均距離，聚類系數(shù)、點(diǎn)(邊)介數(shù)，譜半徑、連通性、密度、網(wǎng)絡(luò)效率和網(wǎng)絡(luò)熵等[9]。例如度及度分布按照拓?fù)浣Y(jié)構(gòu)對網(wǎng)絡(luò)進(jìn)行分類，網(wǎng)絡(luò)的熵描述了網(wǎng)絡(luò)的隨機(jī)程度。隨機(jī)網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)是兩種典型網(wǎng)絡(luò)模型，對于隨機(jī)網(wǎng)絡(luò)本身而言，節(jié)點(diǎn)對之間是否存在連接邊是完全隨機(jī)的，網(wǎng)絡(luò)整體體現(xiàn)均勻的特性；無標(biāo)度網(wǎng)絡(luò)認(rèn)為網(wǎng)絡(luò)本身不是靜態(tài)的，并且連接邊的存在并非完全隨機(jī)化，而是滿足一定的演化規(guī)則，現(xiàn)在許多關(guān)鍵基礎(chǔ)設(shè)施網(wǎng)絡(luò)(如互聯(lián)網(wǎng)、電力和鐵路網(wǎng)絡(luò))均滿足無標(biāo)度特性[10]。

1.1 ER隨機(jī)網(wǎng)絡(luò)

隨機(jī)網(wǎng)絡(luò)模型是與規(guī)則網(wǎng)絡(luò)模型完全對立的模型，Erd?s和Rényi利用在節(jié)點(diǎn)對之間隨機(jī)添加一定數(shù)量連接邊的方式構(gòu)造ER隨機(jī)網(wǎng)絡(luò)[1]，該網(wǎng)絡(luò)模型可以通過解析方法進(jìn)行精確研究分析，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)N→+∞時(shí)，網(wǎng)絡(luò)中節(jié)點(diǎn)的度值都集中在某個(gè)固定值附近，不會出現(xiàn)度值極大或極小的節(jié)點(diǎn)，網(wǎng)絡(luò)整體表現(xiàn)出均勻性，ER隨機(jī)網(wǎng)絡(luò)模型的節(jié)點(diǎn)度分布服從泊松(poisson)分布

(1)

其中，λ為ER隨機(jī)網(wǎng)絡(luò)的平均度。

ER網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其度分布的直方圖(N=50,p=0.2),如圖1所示。

1.2 BA無標(biāo)度網(wǎng)絡(luò)

Barabási等指出真實(shí)網(wǎng)絡(luò)具備無標(biāo)度的特殊性質(zhì)[11]，充分考慮復(fù)雜網(wǎng)絡(luò)“增長”和“擇優(yōu)”的非隨機(jī)動(dòng)態(tài)特性，無標(biāo)度網(wǎng)絡(luò)中具有少量度值很高的Hub節(jié)點(diǎn)和大量低度值的節(jié)點(diǎn)，這種非均勻結(jié)構(gòu)導(dǎo)致偏態(tài)度序列分布，具體表現(xiàn)為冪律的度分布特性

圖1 ER網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其度分布的直方圖(N=50,p=0.2)

(2)

其中，α為系數(shù)，q為分布指數(shù)。通常情況下，真實(shí)網(wǎng)絡(luò)的分布指數(shù)滿足2

BA網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其度分布的直方圖(N=50,m=m0=3),如圖2所示。

圖2 BA網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及其度分布的直方圖(N=50,m=m0=3)

表1為復(fù)雜網(wǎng)絡(luò)模型的相關(guān)特性[9]。

表1 復(fù)雜網(wǎng)絡(luò)模型的相關(guān)特性

2 復(fù)雜網(wǎng)絡(luò)可靠性函數(shù)

2.1 復(fù)雜網(wǎng)絡(luò)可靠性函數(shù)的定義

復(fù)雜網(wǎng)絡(luò)的可靠性是指網(wǎng)絡(luò)在規(guī)定的條件下，在規(guī)定的時(shí)間內(nèi)完成規(guī)定功能的能力[3]。復(fù)雜網(wǎng)絡(luò)通常包含大量網(wǎng)絡(luò)節(jié)點(diǎn)，節(jié)點(diǎn)具備異質(zhì)性及復(fù)雜的連接關(guān)系，整個(gè)網(wǎng)絡(luò)整體呈現(xiàn)多層次、多維數(shù)、多等級和多屬性的復(fù)雜特性。對于無向網(wǎng)絡(luò)而言，不考慮重邊及自環(huán)等特殊情況，利用圖論理論將復(fù)雜網(wǎng)絡(luò)抽象為圖G(V,E)，其中V={v1,v2,…vN}為網(wǎng)絡(luò)的節(jié)點(diǎn)集合，N為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)，E={e1,e2,…eM}為網(wǎng)絡(luò)的邊集合，M為網(wǎng)絡(luò)邊的總數(shù)，集合E滿足E?V×V。網(wǎng)絡(luò)節(jié)點(diǎn)通過邊進(jìn)行信息流、物質(zhì)流和能量流的交換，網(wǎng)絡(luò)節(jié)點(diǎn)及邊的拓?fù)浣Y(jié)構(gòu)決定網(wǎng)絡(luò)的連通性，刪除或添加網(wǎng)絡(luò)邊對網(wǎng)絡(luò)的連通性及網(wǎng)絡(luò)功能產(chǎn)生重要影響。由于復(fù)雜網(wǎng)絡(luò)的度及其度分布是網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的直接體現(xiàn)，因此本文基于節(jié)點(diǎn)度值的標(biāo)準(zhǔn)差σ來定義網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)。

本文對網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)作如下定義

(3)

2.2 網(wǎng)絡(luò)可靠性函數(shù)的性質(zhì)

依據(jù)可靠性定義，網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)滿足以下兩個(gè)性質(zhì)：

(1)收斂性：對于給定的任意節(jié)點(diǎn)總數(shù)N和邊數(shù)M，0≤H(σ,N,M)≤1。

(2)單調(diào)性：對于給定的任意網(wǎng)絡(luò)，任意刪除1條邊，網(wǎng)絡(luò)可靠性H(σ,N,M)減小。

下面分別對兩個(gè)性質(zhì)進(jìn)行證明：

(1)對于網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)而言，函數(shù)為指數(shù)函數(shù)且滿足

(4)

圖3 全局耦合網(wǎng)絡(luò)(N=10)

對于另外一種極端情況，網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)為N，邊數(shù)M=0，整個(gè)網(wǎng)絡(luò)中不存在連接邊，稱為孤立點(diǎn)網(wǎng)絡(luò)，如圖4所示。此時(shí)網(wǎng)絡(luò)的度值標(biāo)準(zhǔn)差σ=0，計(jì)算得到網(wǎng)絡(luò)可靠度為H(σ,N,M)=exp(-10)=4.54×10-5≈0。

圖4 孤立點(diǎn)網(wǎng)絡(luò)(N=10)

通過對兩種情況分析，證明得到0≤H(σ,N,M)≤1，因此性質(zhì)1成立。

本文采用逆推法，證明過程如下：

對不等式左側(cè)σ′2進(jìn)行計(jì)算

(5)

對不等式右側(cè)(σ+N)2進(jìn)行計(jì)算

(6)

若σ′2<(σ+N)2，需要滿足

(7)

(8)

由于dmax=N-1，因此

(9)

上式在N≥3時(shí)恒成立，即對于任意節(jié)點(diǎn)數(shù)N≥3的復(fù)雜網(wǎng)絡(luò)，不等式σ′2<(σ+N)2恒成立，因此可靠性函數(shù)H(σ,N,M)滿足性質(zhì)2。

從本節(jié)分析中可以看出，以網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N、網(wǎng)絡(luò)邊數(shù)M和網(wǎng)絡(luò)度值標(biāo)準(zhǔn)差σ構(gòu)造網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)能嚴(yán)格收斂于區(qū)間[0,1]中，孤立點(diǎn)網(wǎng)絡(luò)和全局耦合網(wǎng)絡(luò)分別對應(yīng)Hmin=0和Hmax=1；網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)具備單調(diào)性，任意刪除網(wǎng)絡(luò)中的1條邊，H(σ,N,M)嚴(yán)格遞減，可以用H(σ,N,M)來度量復(fù)雜網(wǎng)絡(luò)的網(wǎng)絡(luò)可靠度，研究復(fù)雜網(wǎng)絡(luò)的可靠性與拓?fù)浣Y(jié)構(gòu)的關(guān)系。

3 仿真分析

3.1 失效模式

對于ER隨機(jī)網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)，采用兩種失效方式逐步移除網(wǎng)絡(luò)中的邊：隨機(jī)破壞和蓄意攻擊。隨機(jī)破壞是指沒有固定目標(biāo)，完全隨機(jī)地按照一定比例地將邊進(jìn)行

移除；蓄意攻擊是指按照一定策略，有針對性地對重要連接邊進(jìn)行移除。在兩種模式下，網(wǎng)絡(luò)中逐漸出現(xiàn)孤立節(jié)點(diǎn)，網(wǎng)絡(luò)的連通性逐漸降低，當(dāng)所有連接邊被移除，網(wǎng)絡(luò)則無法進(jìn)行信息流、物質(zhì)流和能量流的交換，從而無法完成網(wǎng)絡(luò)規(guī)定的功能，此時(shí)認(rèn)為網(wǎng)絡(luò)可靠度為零[12,13]。

在蓄意攻擊的失效模式下，本文采用邊介數(shù)來表征連接邊的重要度[14,15]，邊em的介數(shù)Bm定義為

(10)

邊介數(shù)Bm描述了邊em對網(wǎng)絡(luò)中節(jié)點(diǎn)對之間信息傳播的控制能力，若節(jié)點(diǎn)對ii′不存在路徑或邊em不存在最短路徑中，則邊em不具備對于節(jié)點(diǎn)對ii′信息傳播的控制能力。通常情況下，節(jié)點(diǎn)對的最短路徑存在多條，信息傳播總是沿著其中的一條最短路徑進(jìn)行，邊介數(shù)Bm則為信息通過邊em的概率。

3.2 仿真結(jié)果及分析

圖5為兩種失效模式下，ER隨機(jī)網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)與連接邊移除比例f的仿真結(jié)果，其中網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N=100，初始時(shí)刻網(wǎng)絡(luò)的平均度λ=90。

圖5 ER網(wǎng)絡(luò)和BA網(wǎng)絡(luò)可靠性函數(shù)與邊移除比例的仿真結(jié)果

分析仿真結(jié)果可得到以下結(jié)論：

(1)在兩種失效模式下，網(wǎng)絡(luò)可靠性隨著邊移除比例f增大而逐漸降低，并且可靠性函數(shù)H(σ,N,M)嚴(yán)格遞減。隨著邊移除比例f逐漸增大，網(wǎng)絡(luò)中的節(jié)點(diǎn)逐漸成為孤立節(jié)點(diǎn)，無法完成信息流、物質(zhì)流和能量流的傳輸?shù)裙δ?，最終網(wǎng)絡(luò)可靠度逐漸降低到零。

(2)在隨機(jī)破壞的失效模式下，相對于ER隨機(jī)網(wǎng)絡(luò)而言，BA無標(biāo)度網(wǎng)絡(luò)整體表現(xiàn)出較強(qiáng)的可靠性，當(dāng)f<0.5時(shí)，BA無標(biāo)度網(wǎng)絡(luò)的可靠性下降速度較慢，整體表現(xiàn)出較高的可靠性；ER隨機(jī)網(wǎng)絡(luò)面對隨機(jī)破壞的失效模式，網(wǎng)絡(luò)可靠性下降速率相對平穩(wěn)，未出現(xiàn)較大波動(dòng)。

(3)在蓄意攻擊的失效模式下，BA無標(biāo)度網(wǎng)絡(luò)的可靠性速度下降非常迅速，在f=0.4附近時(shí)接近于零，體現(xiàn)出明顯的脆弱性；ER隨機(jī)網(wǎng)絡(luò)的可靠性下降速度也比隨機(jī)破壞下迅速，當(dāng)f=0.8時(shí)基本接近于零。ER隨機(jī)網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)的可靠性在蓄意攻擊模式下整體相對較低，說明蓄意攻擊對網(wǎng)絡(luò)可靠性影響較大。

在隨機(jī)破壞的模式下，BA無標(biāo)度網(wǎng)絡(luò)表現(xiàn)出較高的可靠性，主要是由于BA無標(biāo)度網(wǎng)絡(luò)的度分布為冪律分布，表現(xiàn)出較強(qiáng)的非均勻性：網(wǎng)絡(luò)中存在少量的Hub節(jié)點(diǎn)，度值相對很大，大部分節(jié)點(diǎn)的度值都相對很小，當(dāng)移除比例f較小時(shí)，網(wǎng)絡(luò)中的Hub節(jié)點(diǎn)仍然處于連通狀態(tài)，網(wǎng)絡(luò)的可靠度較高；當(dāng)移除比例f逐漸增大時(shí)，Hub節(jié)點(diǎn)的度值也開始大量下降，直接體現(xiàn)為網(wǎng)絡(luò)可靠性下降。由于這種非均勻性，Hub節(jié)點(diǎn)的連接邊則成為蓄意攻擊的目標(biāo)，有意識地移除Hub點(diǎn)的連接邊會對整個(gè)網(wǎng)絡(luò)的連通度及可靠性產(chǎn)生很大影響。對于ER隨機(jī)網(wǎng)絡(luò)而言，其度分布為泊松分布，大部分節(jié)點(diǎn)的度值分布在λ附近，不會出現(xiàn)度值極大或極小的節(jié)點(diǎn)，網(wǎng)絡(luò)體現(xiàn)出均勻性，在隨機(jī)破壞和蓄意攻擊兩種模式下，ER隨機(jī)網(wǎng)絡(luò)的可靠性下降沒有出現(xiàn)較大波動(dòng)，相對均勻平穩(wěn)。

4 結(jié)束語

由于ER隨機(jī)網(wǎng)絡(luò)是連接邊完全隨機(jī)化的隨機(jī)均勻網(wǎng)絡(luò)，而BA無標(biāo)度網(wǎng)絡(luò)是具備“增長”和“擇優(yōu)”特征的冪律非均勻網(wǎng)絡(luò)，兩者的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有完全不同的特征，本文從度值標(biāo)準(zhǔn)差σ來定義網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)，證明函數(shù)具備收斂性和單調(diào)性，最后通過仿真方法分析在隨機(jī)破壞與蓄意攻擊的失效模式下，ER隨機(jī)網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)的可靠性變化特征，并對變化機(jī)理進(jìn)行闡述分析，驗(yàn)證網(wǎng)絡(luò)可靠性函數(shù)H(σ,N,M)的可行性和有效性。

[1]HEDaren,LIUZonghua,WANGBinghong.Complexsystemsandcomplexnetworks[M].Beijing:HigherEducationPress,2012:178-210 (inChinese).[何大韌,劉宗華,汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)[M].北京:高等教育出版社,2012:178-210.]

[2]SUNXijing,SIShoukui.Complexnetworkalgorithmsapplication[M].Beijing:NationalDefenseIndustryPress,2015:236-257(inChinese).[孫璽菁,司守奎.復(fù)雜網(wǎng)絡(luò)算法與應(yīng)用[M].北京:國防工業(yè)出版社,2015:236-257.]

[3]TANYuejin,ZHAOJuan,WUJun,etal.Reviewonthenetworkreliabilitybasedonpaths[J].SystemsEngineering-Theory&Practice,2012,32(12):2724-2730(inChinese).[譚躍進(jìn),趙娟,吳俊,等.基于路徑的網(wǎng)絡(luò)可靠性綜述研究[J].系統(tǒng)工程理論與實(shí)踐,2012,32(12):2724-2730.]

[4]HUANGNing,WUZhitao.Surveyofnetworkreliabilityeva-luationmodelsandalgorithms[J].SystemsEngineeringand

Electronics,2013,35(12):2651-2660(inChinese).[黃寧,伍志韜.網(wǎng)絡(luò)可靠性評估模型與算法綜述[J].系統(tǒng)工程與電子技術(shù),2013,35(12):2651-2660.]

[5]JiangYN.Surveyonnetworkreliabilityevaluationmethods[J].ComputerScience,2012,39(5):9-13.

[6]WuLS,TanQM,ZhangYH.Networkconnectivityentropyanditsapplicationonnetworkconnectivityreliability[J].PhysicaA,2013,392(2):5536-5541.

[7]WULiusan,TANQingmei,ZHANGYuehui.Theimpactofnetworkarc’sgrowthonthenetworkreliability[J].ChineseJournalofManagementScience,2015,23(1):65-72(inChinese).[吳六三,譚清美,張躍輝.網(wǎng)絡(luò)弧生長對網(wǎng)絡(luò)可靠性的影響[J].中國管理科學(xué),2015,23(1):65-72.]

[8]LUOPeng,LIYongli,WUChong.Complexnetworksevolutionresearchwithusingthenetworkstructureentropy[J].ComplexSystemsandComplexityScience,2013,10(4):62-68(inChinese).[羅鵬,李永立,吳沖.利用網(wǎng)絡(luò)結(jié)構(gòu)熵研究復(fù)雜網(wǎng)絡(luò)的演化規(guī)律[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2013,10(4):62-68.]

[9]LIKai,WUWei.Researchstatusofweaponequipmentsystem-of-systemsbasedoncomplexnetwork[J].JournalofAcademyofForceEngineering,2016,30(4):7-13(inChinese).[李鍇,吳緯.基于復(fù)雜網(wǎng)絡(luò)的武器裝備體系研究現(xiàn)狀[J].裝甲兵工程學(xué)院學(xué)報(bào),2016,30(4):7-13.]

[10]ZhangLM,LiDQ,FuB,etal.Reliabilityanalysisofinterdependentlattices[J].PhysicaA,2016,452(15):120-125.

[11]ColmanER,RodgersGJ.Complexscale-freenetworkswithtunablepower-lawexponentandclustering[J].PhysicaA,2013,392(2):5501-5510.

[12]KernerBS.Criticismofgenerallyacceptedfundamentalsandmethodologiesoftrafficandtransportationtheory:Abriefreview[J].PhysicaA,2013,392(2):5261-5282.

[13]MinOY,PanZZ,HongL,etal.Correlationanalysisofdifferentvulnerabilitymetricsonpowergrids[J].PhysicaA,2014,396(2):204-211.

[14]HuP,FanWL,MeiSW.Identifyingnodeimportanceincomplexnetworks[J].PhysicaA,2015,429(3):169-176.

[15]ZhangJH,XuXM,HongL,etal.Attackvulnerabilityofself-organizingnetworks[J].SafetyScience,2012,50(3):443-447.