基于度值標準差的復雜網絡可靠性

李 鍇，何永鋒

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

0 引 言

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

1 復雜網絡模型

復雜網絡模型主要經歷4個模型階段：規則網絡(regular network)、隨機網絡(random network)、小世界網絡(small-world network)和無標度網絡(scale-free network)。為研究復雜網絡模型的拓撲結構，專家學者定義許多特征量，主要有度與度分布、平均距離，聚類系數、點(邊)介數，譜半徑、連通性、密度、網絡效率和網絡熵等[9]。例如度及度分布按照拓撲結構對網絡進行分類，網絡的熵描述了網絡的隨機程度。隨機網絡和無標度網絡是兩種典型網絡模型，對于隨機網絡本身而言，節點對之間是否存在連接邊是完全隨機的，網絡整體體現均勻的特性；無標度網絡認為網絡本身不是靜態的，并且連接邊的存在并非完全隨機化，而是滿足一定的演化規則，現在許多關鍵基礎設施網絡(如互聯網、電力和鐵路網絡)均滿足無標度特性[10]。

1.1 ER隨機網絡

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

(1)

其中，λ為ER隨機網絡的平均度。

ER網絡拓撲結構及其度分布的直方圖(N=50,p=0.2),如圖1所示。

1.2 BA無標度網絡

Barabási等指出真實網絡具備無標度的特殊性質[11]，充分考慮復雜網絡“增長”和“擇優”的非隨機動態特性，無標度網絡中具有少量度值很高的Hub節點和大量低度值的節點，這種非均勻結構導致偏態度序列分布，具體表現為冪律的度分布特性

圖1 ER網絡拓撲結構及其度分布的直方圖(N=50,p=0.2)

(2)

其中，α為系數，q為分布指數。通常情況下，真實網絡的分布指數滿足2

BA網絡拓撲結構及其度分布的直方圖(N=50,m=m0=3),如圖2所示。

圖2 BA網絡拓撲結構及其度分布的直方圖(N=50,m=m0=3)

表1為復雜網絡模型的相關特性[9]。

表1 復雜網絡模型的相關特性

2 復雜網絡可靠性函數

2.1 復雜網絡可靠性函數的定義

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

本文對網絡可靠性函數H(σ,N,M)作如下定義

(3)

2.2 網絡可靠性函數的性質

依據可靠性定義，網絡可靠性函數H(σ,N,M)滿足以下兩個性質：

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

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

下面分別對兩個性質進行證明：

(1)對于網絡可靠性函數H(σ,N,M)而言，函數為指數函數且滿足

(4)

圖3 全局耦合網絡(N=10)

對于另外一種極端情況，網絡中的節點數為N，邊數M=0，整個網絡中不存在連接邊，稱為孤立點網絡，如圖4所示。此時網絡的度值標準差σ=0，計算得到網絡可靠度為H(σ,N,M)=exp(-10)=4.54×10-5≈0。

圖4 孤立點網絡(N=10)

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

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

對不等式左側σ′2進行計算

(5)

對不等式右側(σ+N)2進行計算

(6)

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

(7)

(8)

由于dmax=N-1，因此

(9)

上式在N≥3時恒成立，即對于任意節點數N≥3的復雜網絡，不等式σ′2<(σ+N)2恒成立，因此可靠性函數H(σ,N,M)滿足性質2。

從本節分析中可以看出，以網絡節點數N、網絡邊數M和網絡度值標準差σ構造網絡可靠性函數H(σ,N,M)能嚴格收斂于區間[0,1]中，孤立點網絡和全局耦合網絡分別對應Hmin=0和Hmax=1；網絡可靠性函數H(σ,N,M)具備單調性，任意刪除網絡中的1條邊，H(σ,N,M)嚴格遞減，可以用H(σ,N,M)來度量復雜網絡的網絡可靠度，研究復雜網絡的可靠性與拓撲結構的關系。

3 仿真分析

3.1 失效模式

對于ER隨機網絡和BA無標度網絡，采用兩種失效方式逐步移除網絡中的邊：隨機破壞和蓄意攻擊。隨機破壞是指沒有固定目標，完全隨機地按照一定比例地將邊進行

移除；蓄意攻擊是指按照一定策略，有針對性地對重要連接邊進行移除。在兩種模式下，網絡中逐漸出現孤立節點，網絡的連通性逐漸降低，當所有連接邊被移除，網絡則無法進行信息流、物質流和能量流的交換，從而無法完成網絡規定的功能，此時認為網絡可靠度為零[12,13]。

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

(10)

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

3.2 仿真結果及分析

圖5為兩種失效模式下，ER隨機網絡和BA無標度網絡可靠性函數H(σ,N,M)與連接邊移除比例f的仿真結果，其中網絡的節點數N=100，初始時刻網絡的平均度λ=90。

圖5 ER網絡和BA網絡可靠性函數與邊移除比例的仿真結果

分析仿真結果可得到以下結論：

(1)在兩種失效模式下，網絡可靠性隨著邊移除比例f增大而逐漸降低，并且可靠性函數H(σ,N,M)嚴格遞減。隨著邊移除比例f逐漸增大，網絡中的節點逐漸成為孤立節點，無法完成信息流、物質流和能量流的傳輸等功能，最終網絡可靠度逐漸降低到零。

(2)在隨機破壞的失效模式下，相對于ER隨機網絡而言，BA無標度網絡整體表現出較強的可靠性，當f<0.5時，BA無標度網絡的可靠性下降速度較慢，整體表現出較高的可靠性；ER隨機網絡面對隨機破壞的失效模式，網絡可靠性下降速率相對平穩，未出現較大波動。

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

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

4 結束語

由于ER隨機網絡是連接邊完全隨機化的隨機均勻網絡，而BA無標度網絡是具備“增長”和“擇優”特征的冪律非均勻網絡，兩者的網絡拓撲結構具有完全不同的特征，本文從度值標準差σ來定義網絡可靠性函數H(σ,N,M)，證明函數具備收斂性和單調性，最后通過仿真方法分析在隨機破壞與蓄意攻擊的失效模式下，ER隨機網絡和BA無標度網絡的可靠性變化特征，并對變化機理進行闡述分析，驗證網絡可靠性函數H(σ,N,M)的可行性和有效性。

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

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

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

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

Electronics,2013,35(12):2651-2660(inChinese).[黃寧,伍志韜.網絡可靠性評估模型與算法綜述[J].系統工程與電子技術,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).[吳六三,譚清美,張躍輝.網絡弧生長對網絡可靠性的影響[J].中國管理科學,2015,23(1):65-72.]

[8]LUOPeng,LIYongli,WUChong.Complexnetworksevolutionresearchwithusingthenetworkstructureentropy[J].ComplexSystemsandComplexityScience,2013,10(4):62-68(inChinese).[羅鵬,李永立,吳沖.利用網絡結構熵研究復雜網絡的演化規律[J].復雜系統與復雜性科學,2013,10(4):62-68.]

[9]LIKai,WUWei.Researchstatusofweaponequipmentsystem-of-systemsbasedoncomplexnetwork[J].JournalofAcademyofForceEngineering,2016,30(4):7-13(inChinese).[李鍇,吳緯.基于復雜網絡的武器裝備體系研究現狀[J].裝甲兵工程學院學報,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.