異質弱相依網絡魯棒性研究*

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

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

1 引 言

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

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

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

本文的內容主要包括: 第2部分理論分析異質弱相依網絡模型的巨分量方程和相變點; 第3部分仿真驗證本文模型理論框架有效性并討論本文研究成果; 第4部分對全文進行總結.

2 理論分析

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

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

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

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

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

類似地,B網絡巨分量大小為

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

利用概率的加法規則求得fA為

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

同理可知fB為

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

通過聯立求解(13)—(16)式可得隨機攻擊后異質弱相依網絡的巨分量規模.當γ取值唯一時,模型退化為同質弱相依網絡; 當γ=0時,模型退化為傳統相依網絡.

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

顯然(18)式在f=0存在平凡解,表明相依網絡不存在巨分量.在相變點處,若(18)式存在正數解,意味著該相變為連續相變.為了解出相變點pc,γ,對(18)式兩邊求關于f的偏導,可得

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

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

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

3 仿真與討論

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

圖1 同質對稱ER弱相依網絡對于不同g值的巨分量μ∞與p對應關系(網絡節點數為200000,平均度為4)(a) 巨分量大小 μ∞ 與p對應關系,空心標記表示仿真結果,實線是根據(17)和(18)式得到的理論值; (b) 級聯失效迭代次數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 同質對稱SF弱相依網絡對于不同 γ 的巨分量μ∞與p對應關系(網絡節點數為20000,平均度為4,λ=2.6)(a) 巨分量大小 μ∞ 與p對應關系,空心標記表示仿真結果,實線是根據(17)式和(18)式得到的理論值; (b) 級聯失效迭代次數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.

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

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

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

圖3 同質對稱ER弱相依網絡對于不同g值的數值解示意圖(網絡平均度為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 同質對稱SF弱相依網絡對于不同g值的數值解示意圖(網絡平均度為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 不同平均度同質對稱ER弱相依網絡相變點pc與g對應關系,其中網絡的節點數為200000; 空心標記為仿真結果; 理論值分別通過實線和短劃線表示,其中實線為連續相變,短劃線為非連續相變; 垂直的點狀線為連續相變和非連續相變的邊界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分布的同質和異質ER弱相依網絡的仿真結果,其中網絡節點數為200000,平均度是4,q=0.5 ; 空心標記表示仿真結果,實線是理論分析值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分布異質對稱ER弱相依網絡相變點 pc 與?γ值的仿真結果,其中網絡節點數為200000,平均度是4,q=0.5; 空心標記表示仿真值,短劃線和實線分別表示非連續相變與連續相變的理論值,點狀線是連續相變和非連續相變的分界線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分布異質對稱ER弱相依網絡相變點與 ?γ值對應關系的仿真結果,圖中連續相變與非連續相變分界線與(23)式求解方法類似,通過對(19)式兩邊求f的偏導,再將fc=0 代入得到

聯立(20)和(24)式可解出相變分界點與 ?γ的對應關系,如圖7所示.從圖7可以看出,隨著 ?γ增大,網絡的相變點pc逐漸減小,網絡的魯棒性有所提升.當=0.16 時,?γ值的增大使網絡逾滲相變從非連續變為連續.更大 ?γ值意味著網絡弱相依關系的異質性越強,同時會使網絡抵抗隨機攻擊的能力提高.

對于更一般的異質網絡,本文假設p(γ) 服從于以下特殊高斯分布

圖8 連接邊失效概率服從高斯分布的異質對稱ER弱相依網絡巨分量 μ∞ 與p的對應關系,其中高斯分布的均值為0.7,σ 分別為0.9,0.4,0.2; 根據(25)式,σ=0 時p(γ)=δ(γ?); 空心標記為仿真結果,實線為理論分析值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 結 論

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