異質(zhì)弱相依網(wǎng)絡(luò)魯棒性研究*

韓偉濤 伊鵬 馬海龍 張鵬 田樂

(中國人民解放軍戰(zhàn)略支援部隊信息工程大學(xué),信息技術(shù)研究所,鄭州 450000)

1 引 言

現(xiàn)實生活中許多網(wǎng)絡(luò)系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)進(jìn)行建模分析,包括互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)、物聯(lián)網(wǎng)、食物鏈等[1?3].這些復(fù)雜網(wǎng)絡(luò)系統(tǒng)的健壯與否對人們的生產(chǎn)生活起著至關(guān)重要的作用.學(xué)者對真實復(fù)雜網(wǎng)絡(luò)的進(jìn)一步研究發(fā)現(xiàn),多個網(wǎng)絡(luò)系統(tǒng)之間往往存在相互依賴的關(guān)系,即某個網(wǎng)絡(luò)中某些節(jié)點需要依賴于其他網(wǎng)絡(luò)的節(jié)點才能正常工作[4?6],例如,電力系統(tǒng)需要互聯(lián)網(wǎng)傳遞維持正常運(yùn)轉(zhuǎn)的配置消息,食肉動物需要捕食其他物種補(bǔ)充生存所需能量.學(xué)術(shù)界通常使用逾滲模型分析復(fù)雜相依網(wǎng)絡(luò)的魯棒性[7?10],隨機(jī)從相依網(wǎng)絡(luò)中移除 1?p比例的節(jié)點會觸發(fā)逾滲過程,多個網(wǎng)絡(luò)間的節(jié)點會因相依關(guān)系而發(fā)生級聯(lián)失效,即使移除少部分節(jié)點仍可能導(dǎo)致整個相依網(wǎng)絡(luò)的崩潰.

近些年來,學(xué)者們提出了多種模型用于研究現(xiàn)實復(fù)雜網(wǎng)絡(luò)的魯棒性,這些模型研究了網(wǎng)絡(luò)中各種連接邊和依賴邊對網(wǎng)絡(luò)魯棒性造成的影響,包括l-hop逾滲、靴襻逾滲、k-核逾滲等[11?15].除了真實存在的相依邊,還有學(xué)者研究了相依群對復(fù)雜網(wǎng)絡(luò)魯棒性的影響,群內(nèi)節(jié)點互相存在依賴關(guān)系,其中一個節(jié)點失效可能會導(dǎo)致整個相依群完全失效,研究者發(fā)現(xiàn)相依群規(guī)模會對網(wǎng)絡(luò)魯棒性造成較大影響[16?18].為了解釋真實相依網(wǎng)絡(luò)魯棒性優(yōu)于理論分析結(jié)果的現(xiàn)象,有學(xué)者提出了部分依賴相依網(wǎng)絡(luò)模型[19?21],該模型認(rèn)為每個網(wǎng)絡(luò)只有部分節(jié)點依賴于其他網(wǎng)絡(luò),隨著相互依賴比例的減少,網(wǎng)絡(luò)魯棒性會增加.Liu等[22]提出了一種能夠緩解級聯(lián)失效程度的網(wǎng)絡(luò)模型,該模型中被依賴節(jié)點失效不會導(dǎo)致依賴節(jié)點的全部連接邊失效,但作者只考慮了同質(zhì)網(wǎng)絡(luò),即所有連接邊失效概率是相同的,實際網(wǎng)絡(luò)的復(fù)雜性決定了這種同質(zhì)網(wǎng)絡(luò)一般是不存在的.Kong等[23]研究了單個網(wǎng)絡(luò)存在異質(zhì)弱相依邊的情況,但并未考慮多個相依網(wǎng)絡(luò)的情況.

在現(xiàn)實的相依網(wǎng)絡(luò)中,異質(zhì)弱相依邊是普遍存在的.例如,某個電子元器件工廠需要另一個化工廠的原材料維持生產(chǎn),當(dāng)化工廠關(guān)閉后,電子元器件工廠仍可以生產(chǎn)部分種類的產(chǎn)品,因為其本身可制造部分原材料供自身使用,但實際社會生產(chǎn)供應(yīng)鏈?zhǔn)菑?fù)雜的,某些工廠依賴的上游供應(yīng)商倒閉后,由于異質(zhì)弱相依關(guān)系的存在,即使是同類的工廠失去的產(chǎn)能也是不同的.基于此現(xiàn)象,提出一種異質(zhì)弱相依網(wǎng)絡(luò)模型,其中弱相依指的是當(dāng)兩個相互依賴節(jié)點的其中一個失效后,另一個節(jié)點的連接邊以概率g失效而不是全部失效,此外,為了更好地描述現(xiàn)實網(wǎng)絡(luò)節(jié)點異質(zhì)性,本模型中任意節(jié)點因弱相依失效導(dǎo)致的連接邊失效概率g也互不相同.本文利用生成函數(shù)方法給出異質(zhì)弱相依網(wǎng)絡(luò)的逾滲方程,并解出任意隨機(jī)分布異質(zhì)對稱弱相依網(wǎng)絡(luò)的連續(xù)相變點.仿真結(jié)果驗證了本文理論解與隨機(jī)網(wǎng)絡(luò)逾滲模擬值的一致性,通過對兩種不同g分布的異質(zhì)對稱弱相依網(wǎng)絡(luò)逾滲分析可知,相依網(wǎng)絡(luò)魯棒性會隨著網(wǎng)絡(luò)弱相依關(guān)系的異質(zhì)性增大而提高.

本文的內(nèi)容主要包括: 第2部分理論分析異質(zhì)弱相依網(wǎng)絡(luò)模型的巨分量方程和相變點; 第3部分仿真驗證本文模型理論框架有效性并討論本文研究成果; 第4部分對全文進(jìn)行總結(jié).

2 理論分析

本文利用生成函數(shù)方法分析相依網(wǎng)絡(luò)的魯棒性[24].隨機(jī)網(wǎng)絡(luò)的度分布和余度分布生成函數(shù)分別為其中為網(wǎng)絡(luò)中任取一個節(jié)點度為k的概率,表示網(wǎng)絡(luò)的平均度.在單個網(wǎng)絡(luò)中,對于一個度為k的節(jié)點,只要它有一條邊通向巨分量,該節(jié)點就屬于巨分量.令f為沿任意一條邊到達(dá)的節(jié)點位于巨分量的概率,則任取一個度為k的節(jié)點位于巨分量的概率為 1?(1?f)k,因此網(wǎng)絡(luò)中任意節(jié)點位于巨分量的概率均值為若初始隨機(jī)攻擊導(dǎo)致 1?p比例節(jié)點失效,在以上概率均值的基礎(chǔ)上乘以p,可得隨機(jī)攻擊后任意節(jié)點位于巨分量的概率

(1)式中的f可通過以下方法求解,沿一條邊到達(dá)的節(jié)點度為k,只要它剩余的k–1條邊有一條通向巨分量,該節(jié)點就屬于巨分量,概率為 1?(1?f)k?1,在整∑個網(wǎng)絡(luò)上求關(guān)于余度分布的概率均值可得f=kP(k)k[1?(1?f)k?1]/?k?,考慮到隨機(jī)攻擊導(dǎo)致1–p比例節(jié)點失效,那么f滿足自洽方程

任意節(jié)點位于巨分量的概率可通過求解(1)與(2)式得到.

為了便于后文分析,首先考慮同質(zhì)弱相依網(wǎng)絡(luò).當(dāng)網(wǎng)絡(luò)某節(jié)點失效后,其相依節(jié)點的連接邊以概率g失效,在整個網(wǎng)絡(luò)中,弱相依導(dǎo)致的連接邊失效概率g對于任意節(jié)點是相同的,這樣的網(wǎng)絡(luò)稱為同質(zhì)弱相依網(wǎng)絡(luò).本模型初始攻擊導(dǎo)致的相依失效與傳統(tǒng)模型相同,即初始攻擊隨機(jī)移除A網(wǎng)絡(luò)1–p節(jié)點,對應(yīng)B網(wǎng)絡(luò)對應(yīng)1–p節(jié)點也失效.隨后發(fā)生級聯(lián)失效過程直至網(wǎng)絡(luò)不再有新的節(jié)點失效,該過程中節(jié)點間依賴關(guān)系是弱相依的.最終狀態(tài)A網(wǎng)絡(luò)任意節(jié)點位于巨分量概率取決于以下兩種情況: (E1)該節(jié)點及其弱相依節(jié)點都在巨分量中;(E2)該節(jié)點的弱相依節(jié)點失效導(dǎo)致它的每條連接邊以概率g失效,但該節(jié)點仍位于巨分量.兩種概率的表達(dá)式P(E1)和P(E2) 分別為

把(3)和(4)式代入(5)式可得

類似地,B網(wǎng)絡(luò)巨分量大小為

求解(6)和(7)式需要得到fA和fB的自洽方程,A網(wǎng)絡(luò)沿著任意邊抵達(dá)巨分量概率fA也包含兩種情況: (E3)沿著這條邊到達(dá)的節(jié)點及其弱相依節(jié)點都在巨分量中; (E4)沿著這條邊抵達(dá)的節(jié)點的弱相依節(jié)點失效導(dǎo)致它的每條連接邊以概率g失效,但該節(jié)點仍位于巨分量.兩種情況的概率方程分別為

利用概率的加法規(guī)則求得fA為

將(8)和(9)式代入(10)式可得

同理可知fB為

接著分析異質(zhì)弱相依網(wǎng)絡(luò).當(dāng)網(wǎng)絡(luò)某節(jié)點失效后,其對應(yīng)依賴節(jié)點的連接邊仍以某概率失效,但從整個網(wǎng)絡(luò)層面來講,不同節(jié)點因相依節(jié)點失效導(dǎo)致的連接邊失效概率不完全相同,而是服從一定的概率分布,這種網(wǎng)絡(luò)稱作異質(zhì)弱相依網(wǎng)絡(luò).假設(shè)存在弱相依關(guān)系節(jié)點的邊失效概率取值范圍是γ={γ1,γ2,γ3,···},任意節(jié)點邊失效概率p(γ) 服從分布則新的μ∞和f值可通過對求概率均值得到,即如下:

通過聯(lián)立求解(13)—(16)式可得隨機(jī)攻擊后異質(zhì)弱相依網(wǎng)絡(luò)的巨分量規(guī)模.當(dāng)γ取值唯一時,模型退化為同質(zhì)弱相依網(wǎng)絡(luò); 當(dāng)γ=0時,模型退化為傳統(tǒng)相依網(wǎng)絡(luò).

理論分析任意度分布的異質(zhì)弱相依網(wǎng)絡(luò)復(fù)雜度較高,本文考慮對稱網(wǎng)絡(luò)以簡化分析.假設(shè)對稱相依網(wǎng)絡(luò)具有相同的度分布和余度分布,即GA0(x)=GB0(x)=G0(x),GA1(x)=GB1(x)=G1(x) ,所以(13)—(16)式簡化為

顯然(18)式在f=0存在平凡解,表明相依網(wǎng)絡(luò)不存在巨分量.在相變點處,若(18)式存在正數(shù)解,意味著該相變?yōu)檫B續(xù)相變.為了解出相變點pc,γ,對(18)式兩邊求關(guān)于f的偏導(dǎo),可得

為了便于進(jìn)一步簡化分析,假設(shè)相依網(wǎng)絡(luò)為對稱的Erd?s-Rényi (ER)[25]同質(zhì)網(wǎng)絡(luò),即任意節(jié)點連接邊失效概率均為γ,且網(wǎng)絡(luò)的度分布和余度分布生成函數(shù)相同,G0(x)=G1(x)=e??k?(1?x),則(20)式可簡化為

(21)式只在γ<γc有效,若γ>γc,網(wǎng)絡(luò)不存在連續(xù)相變.在點γ=γc處,會出現(xiàn)相依網(wǎng)絡(luò)連續(xù)與非連續(xù)相變的交匯點,所以當(dāng)γ=γc時,兩種相變存在相同的fc值,即fc=0.因此可以對(19)式兩邊求關(guān)于f的偏導(dǎo)并將f=0 代入得到γc的取值,如下:

通過求解(23)式可知γc=0.16071.此外,對于其他異質(zhì)相依網(wǎng)絡(luò),仍然可以采用以上方法求γc,但復(fù)雜度較高且最終解可能不具備較為簡潔的形式.

3 仿真與討論

首先考慮同質(zhì)對稱弱相依網(wǎng)絡(luò),圖1和圖2分別為ER和scale-free (SF)[26]對稱弱相依網(wǎng)絡(luò)的逾滲仿真結(jié)果.圖中給出了巨分量μ∞和級聯(lián)失效迭代次數(shù)(number of iterative,NOI)與初始保留節(jié)點比例p的關(guān)系.從圖1和圖2可以看出仿真結(jié)果與理論分析擬合.隨著γ值的減小,相變點pc逐漸減小的同時網(wǎng)絡(luò)魯棒性有所提升.對于非連續(xù)相變,NOI曲線在相變點處存在尖峰,連續(xù)相變的NOI曲線一直比較平緩.

圖1 同質(zhì)對稱ER弱相依網(wǎng)絡(luò)對于不同g值的巨分量μ∞與p對應(yīng)關(guān)系(網(wǎng)絡(luò)節(jié)點數(shù)為200000,平均度為4)(a) 巨分量大小 μ∞ 與p對應(yīng)關(guān)系,空心標(biāo)記表示仿真結(jié)果,實線是根據(jù)(17)和(18)式得到的理論值; (b) 級聯(lián)失效迭代次數(shù)Fig.1.Simulation results of μ∞ versus p for homogeneous symmetric interdependent ER networks for different g (each network has 200000 nodes,average degree is 4).(a) The size of the giant component μ∞ versus p.The symbols represent the simulation results,and the solid lines show the corresponding analytical predictions of Eqs.(17) and (18).(b) Number of iterative failures.

圖2 同質(zhì)對稱SF弱相依網(wǎng)絡(luò)對于不同 γ 的巨分量μ∞與p對應(yīng)關(guān)系(網(wǎng)絡(luò)節(jié)點數(shù)為20000,平均度為4,λ=2.6)(a) 巨分量大小 μ∞ 與p對應(yīng)關(guān)系,空心標(biāo)記表示仿真結(jié)果,實線是根據(jù)(17)式和(18)式得到的理論值; (b) 級聯(lián)失效迭代次數(shù)Fig.2.Simulation results of μ∞ versus p for homogeneous symmetric interdependent SF networks for different g (each network has 200000 nodes,average degree is 4,λ=2.6).(a) The size of the giant component μ∞ versus p.The symbols represent the simulation results,and the solid lines show the corresponding analytical predictions of Eqs.(17)and (18).(b) Number of iterative failures.

下面通過圖形示意方法討論逾滲相變點數(shù)值解,令D(f)=rhs?f,其中 rhs 表示(18)式等號右邊的部分,顯然D(0)=0 ,即D(f) 在0點處與f軸相交.隨著初始保留節(jié)點比例p的增大,D(f) 曲線會逐漸上升,直到p增大到相變點,D(f) 曲線會第一次與f軸相切,此時的p即為相變點pc.圖3和圖4分別為同質(zhì)ER,SF弱相依網(wǎng)絡(luò)的逾滲數(shù)值解示意圖,圖中給出了D(f) 與f的對應(yīng)關(guān)系.從圖3和圖4可以看出,當(dāng)p=pc時,D(f) 曲線會與圖f軸相切,并且連續(xù)相變的切點為0 (圖3(a)、圖4(a)),非連續(xù)相變的切點大于0 (圖3(b)、圖4(b)).

圖5給出了根據(jù)(21)和(23)式求出的不同平均度同質(zhì)對稱ER弱相依網(wǎng)絡(luò)相變點pc與g對應(yīng)關(guān)系.從圖5可以看出,對于同質(zhì)對稱ER相依網(wǎng)絡(luò),γc取值唯一且與網(wǎng)絡(luò)度分布無關(guān),這與前文理論分析結(jié)果一致.此外,隨著平均度的增加,pc隨之減少,意味著網(wǎng)絡(luò)中更多的連接邊可使網(wǎng)絡(luò)更加魯棒.

接下來考慮異質(zhì)對稱弱相依網(wǎng)絡(luò).為了便于仿真分析,首先考慮一種較為簡單的γ分布情況,即γ={??γ,+?γ}且p(γ)～{q,1?q} ,表示網(wǎng)路中任取節(jié)點的弱相依節(jié)點失效后,其連接邊失效概率為??γ的概率為q,連接邊失效概率為+?γ的概率為 1?q.圖6給出了不同簡單γ分布的同質(zhì)(?γ=0)和異質(zhì)(?γ=0) ER相依網(wǎng)絡(luò)的仿真結(jié)果.從圖6可以看出,在相同γ概率均值的情況下,異質(zhì)性的引入會減小pc并提高網(wǎng)絡(luò)的魯棒性.

圖3 同質(zhì)對稱ER弱相依網(wǎng)絡(luò)對于不同g值的數(shù)值解示意圖(網(wǎng)絡(luò)平均度為4; 在相變點pc處,D(f) 曲線與f軸相切) (a) g=0.1; (b) g=0.4Fig.3.Graphical solutions of homogeneous symmetric interdependent ER networks percolation transition for different g: (a) g=0.1; (b) g=0.4.The average degree is 4.At the transition point pc,the curve of D(f) tangents to f axis.

圖4 同質(zhì)對稱SF弱相依網(wǎng)絡(luò)對于不同g值的數(shù)值解示意圖(網(wǎng)絡(luò)平均度為4,λ=2.6 ; 在相變點pc處,D(f) 曲線與f軸相切)(a) g=0.5; (b) g=0.9Fig.4.Graphical solutions of homogeneous symmetric interdependent SF networks percolation transition for different g: (a) g=0.5;(b) g=0.9.The average degree is 4,λ=2.6.At the transition point pc,the curve of D(f) tangents to f axis.

圖5 不同平均度同質(zhì)對稱ER弱相依網(wǎng)絡(luò)相變點pc與g對應(yīng)關(guān)系,其中網(wǎng)絡(luò)的節(jié)點數(shù)為200000; 空心標(biāo)記為仿真結(jié)果; 理論值分別通過實線和短劃線表示,其中實線為連續(xù)相變,短劃線為非連續(xù)相變; 垂直的點狀線為連續(xù)相變和非連續(xù)相變的邊界Fig.5.Simulation results of pc versus g for homogeneous symmetric interdependent ER networks with different,each network has 200000 nodes.The symbols represent the simulation results.The corresponding analytical predictions are shown by lines,solid lines and dashed lines represent continuous and discontinuous phase transitions,respectively.The vertical dotted line is the boundary of continuous and discontinuous regions.

圖6 不同簡單g分布的同質(zhì)和異質(zhì)ER弱相依網(wǎng)絡(luò)的仿真結(jié)果,其中網(wǎng)絡(luò)節(jié)點數(shù)為200000,平均度是4,q=0.5 ; 空心標(biāo)記表示仿真結(jié)果,實線是理論分析值Fig.6.Simulation results of heterogeneous and homogeneous symmetric ER interdependent networks with different g distributions,each network has 200000 nodes,average degree is 4,q=0.5.The symbols represent the simulation results,and the solid lines show the corresponding analytical predictions.

圖7 簡單g分布異質(zhì)對稱ER弱相依網(wǎng)絡(luò)相變點 pc 與?γ值的仿真結(jié)果,其中網(wǎng)絡(luò)節(jié)點數(shù)為200000,平均度是4,q=0.5; 空心標(biāo)記表示仿真值,短劃線和實線分別表示非連續(xù)相變與連續(xù)相變的理論值,點狀線是連續(xù)相變和非連續(xù)相變的分界線Fig.7.Simulation results of critical point pc of simple heterogeneous symmetric ER interdependent networks versus?γ,each network has 200000 nodes,average degree is 4,q=0.5.The symbols represent the simulation results.The corresponding analytical predictions are shown by lines,solid lines and dashed lines represent continuous and discontinuous phase transitions,respectively.The dotted line is the boundary of continuous and discontinuous regions.

圖7是簡單g分布異質(zhì)對稱ER弱相依網(wǎng)絡(luò)相變點與 ?γ值對應(yīng)關(guān)系的仿真結(jié)果,圖中連續(xù)相變與非連續(xù)相變分界線與(23)式求解方法類似,通過對(19)式兩邊求f的偏導(dǎo),再將fc=0 代入得到

聯(lián)立(20)和(24)式可解出相變分界點與 ?γ的對應(yīng)關(guān)系,如圖7所示.從圖7可以看出,隨著 ?γ增大,網(wǎng)絡(luò)的相變點pc逐漸減小,網(wǎng)絡(luò)的魯棒性有所提升.當(dāng)=0.16 時,?γ值的增大使網(wǎng)絡(luò)逾滲相變從非連續(xù)變?yōu)檫B續(xù).更大 ?γ值意味著網(wǎng)絡(luò)弱相依關(guān)系的異質(zhì)性越強(qiáng),同時會使網(wǎng)絡(luò)抵抗隨機(jī)攻擊的能力提高.

對于更一般的異質(zhì)網(wǎng)絡(luò),本文假設(shè)p(γ) 服從于以下特殊高斯分布

圖8 連接邊失效概率服從高斯分布的異質(zhì)對稱ER弱相依網(wǎng)絡(luò)巨分量 μ∞ 與p的對應(yīng)關(guān)系,其中高斯分布的均值為0.7,σ 分別為0.9,0.4,0.2; 根據(jù)(25)式,σ=0 時p(γ)=δ(γ?); 空心標(biāo)記為仿真結(jié)果,實線為理論分析值Fig.8.Simulation results of μ∞ versus p for heterogeneous symmetric ER interdependent networks with Gaussian distributions of connectivity link failure probability.The average valueare set as 0.7,σ are set as 0.9,0.4,0.2,respectively.According to Eq.(25),p(γ)=δ(γ?) when σ=0.The symbols represent the simulation results,and the solid lines show the corresponding analytical predictions.

4 結(jié) 論

現(xiàn)實復(fù)雜網(wǎng)絡(luò)之間往往存在相依關(guān)系,傳統(tǒng)理論分析結(jié)果表明,相依關(guān)系的引入大幅度降低了網(wǎng)絡(luò)抵抗攻擊的能力,但現(xiàn)實網(wǎng)絡(luò)并未因少量節(jié)點遭到攻擊而發(fā)生嚴(yán)重的級聯(lián)失效,其魯棒性往往優(yōu)于傳統(tǒng)理論結(jié)果,因此本文提出一種異質(zhì)弱相依網(wǎng)絡(luò)模型以解釋此現(xiàn)象.與傳統(tǒng)相依網(wǎng)絡(luò)不同,在異質(zhì)弱相依網(wǎng)絡(luò)中,當(dāng)某節(jié)點的相依節(jié)點失效后,該節(jié)點的連接邊以概率g失效而不是全部失效,此外,因為每個節(jié)點存在差異性,不同節(jié)點的連接邊失效的概率也不盡相同.本文給出了異質(zhì)弱相依網(wǎng)絡(luò)模型的逾滲方程,求出關(guān)于任意隨機(jī)網(wǎng)絡(luò)的理論連續(xù)相變點分析了同質(zhì)對稱ER弱相依網(wǎng)絡(luò)連續(xù)與非連續(xù)相變分界點仿真結(jié)果表明,逾滲方程的理論解與隨機(jī)網(wǎng)絡(luò)逾滲模擬結(jié)果相符合,網(wǎng)絡(luò)魯棒性會隨著g值的降低而提高.另外,通過對兩種不同g分布的分析可知,網(wǎng)絡(luò)弱相依關(guān)系的異質(zhì)程度越高魯棒性就越強(qiáng).本文研究成果對如何理解現(xiàn)實復(fù)雜相依網(wǎng)絡(luò)的高魯棒性具有一定的指導(dǎo)意義.