相依網絡的條件依賴群逾滲*

韓偉濤 伊鵬

(國家數字交換系統工程技術研究中心, 鄭州 450000)

1 引 言

現實世界中的許多復雜系統都可以用復雜網絡描述, 例如生物神經系統、社交網絡、交通系統、互聯網等[1?3]. 隨著研究人員對復雜網絡認識的逐漸深入, 相關研究成果已成為人們理解現實世界復雜系統的重要工具. 但現實生活中的復雜系統通常并不是孤立的, 往往多個系統之間存在相互依賴關系, 這種依賴性會導致網絡魯棒性的急劇下降.2003年意大利大停電是典型的相依網絡級聯失效引起的重大生產事故, 最初電網和通信網中極少的節點失效使意大利接近半數的電力設施癱瘓, 數百萬人失去電力供應[4]. 在單個網絡中, 隨著初始刪除節點比例增大, 網絡巨分量(giant component)連續減小, 整個解體過程呈現出二階相變, 但在多個相依網絡, 巨分量減小的過程多為一階相變, 表明相依網絡的魯棒性遠不如單個網絡. 近些年來,相依網絡的魯棒性開始引起研究人員的重視[3,5?13],網絡魯棒性研究主要基于經典統計物理的逾滲模型[14], 該模型能準確描述網絡解體的相變過程.

以往關于相依網絡魯棒性的研究主要針對一對一相依節點[12,15?19], 但在現實情況中, 一個節點往往會依賴于多個節點[6], 這多個被依賴節點稱為該節點的依賴群. 例如一個通信基站會有多個電廠為其供電, 食物鏈中一種生物會捕食多種生物. 近年來, 已有學者對存在依賴群的網絡展開了研究.Shao等[6]提出了一種耦合網絡中存在依賴群的模型, 該模型認為只有當某節點依賴群的全部節點失效后該節點才會失效, 這種依賴模式有效改善了相變點. Wang等[20]研究了網絡的群滲流現象, 網絡節點的存活取決于其所在超級節點是否連向巨分量, 這種網絡模型在一定程度上提高了網絡的魯棒性, 但逾滲類型仍然是一階相變. Parshani等[7]研究了單個網絡中存在依賴群的情況, 發現隨著依賴群規模增大網絡會變得更加脆弱, 極少數節點失效會導致整個網絡崩潰. Wang等[9,21]提出了一種單個網絡中存在條件依賴群的模型, 認為當某節點依賴的節點失效數量超過一定比例時該節點才失效,研究發現隨著失效比例閾值增大, 一階相變甚至會變為二階相變.

本文研究了具有多依賴節點的相依網絡的逾滲現象, 提出相依網絡的條件依賴群逾滲模型并給出巨分量相變方程. 仿真結果表明, 在確定依賴度分布的情況下, 相依網絡逾滲模擬結果與方程數值解相吻合, 并且通過增大失效容忍度或依賴群規模可增強網絡魯棒性. 雖然模型對于任意依賴度分布的相依網絡不存在二階相變, 但本文所述逾滲模型對提高相依網絡魯棒性仍具有一定指導作用.

本文的內容主要包括： 第2部分闡述相依網絡的條件依賴群逾滲模型的基本概念; 第3部分通過理論分析給出模型的巨分量相變方程; 第4部分仿真驗證理論框架有效性; 第5部分討論本文研究成果; 第6部分是結論.

2 模 型

傳統相依網絡逾滲模型多為一對一依賴, 一對一依賴可使網絡滿足無反饋條件, 便于理論分析[3],但嚴格的一對一依賴在現實網絡中通常是不存在的, 一個網絡節點可能會依賴于另一個網絡的多個節點, 若節點依賴的所有節點中有任意一個節點失效, 按照傳統模型的分析方法, 該節點也會失效,如圖1所示.

圖1 具有多依賴關系的相依網絡逾滲示意圖, 初始攻擊導致紅色節點失效, 隨后發生級聯失效過程, 最終相依網絡僅有極少數節點存活Fig. 1. The model of percolation of interdependent net?works with multiple support?dependence relations. The red node fails after the initial attack. Then the cascading fail?ure process leads to a catastrophiccollapse of the interde?pendent networks. Finally, only a small fraction of nodes survive.

這種嚴格的多依賴關系會大幅降低相依網絡的魯棒性, 少部分節點失效就會造成相依網絡完全崩潰. 但現實中的網絡卻沒有這么脆弱. 通過觀察可以發現, 只要依賴群有部分節點存活則依賴節點仍有效, 例如在某產業鏈中, 存在生產同類型產品的工廠若干, 其中少部分同類工廠倒閉并不會導致有關產業鏈的癱瘓[9]. 因此本文提出了一種允許部分相依節點失效的相依網絡逾滲模型, 用以描述在部分被依賴節點失效情況下依賴節點仍正常工作的現象, 如圖2所示.

圖2 相依網絡的條件依賴群逾滲模型 A網絡節點隨機依賴于B網絡的 個節點( ), 反之亦然; A網絡的a節點依賴的3個節點有一個失效, 但失效比例未超過容忍度 , a節點繼續工作; B網絡的b節點依賴的節點失效比例超過 , 所以b節點失效Fig. 2. The model of percolation in interdependent net?works with conditional dependency clusters. Nodes in net?work A randomly depends on ( ) nodes in network B and vice versa. One of the three nodes which node a in network A depends on fails, but the failure proportion does not exceed , node a still works. Two of the three nodes which node b in network B depends on fail, the fail?ure proportion exceeds , node bfails.

3 理論分析

本文提出的相依網絡逾滲模型級聯失效過程如下.

Step 3： 循環進行Step 2, Step 3直至相依網絡中不再有新的節點失效.

根據生成函數理論[22], 網絡的度分布生成函, 余度分布生成函數為, 其 中表 示 任 取一個節點其度為的概率,表示網絡的平均度.隨機刪除網絡比例節點后, 令為隨機選擇一條邊連接的節點通向巨分量的概率, 則滿足自恰方程

對于單個網絡, 聯立上述兩式可解出巨分量的大小. 傳統的一對一相依網絡求解與單網絡相似,這里直接給出[23]

與一對一相依網絡情況不同, 本文提出的模型一個節點可依賴多個節點, 只有當某節點依賴的節點失效比例超過容忍度時, 該節點失效, 令表示在 i 網絡中隨機選擇節點的依賴群失效比例不超過的概率, 則本文模型關于巨分量的方程為

其中

4 仿 真

4.1 RR-RR相依網絡

隨機規則(random regular, RR)網絡的度分布生成函數為, 余度分布生成函數為. 假設兩個RR網絡具有相同的分布, 那么將兩個生成函數代入(7)式可得方程

圖3 不同 取值的RR?RR相依網絡逾滲, 每個網絡節點數 , 平均度 , , 空心標記為仿真值, 實線為逾滲方程數值解 (a) 巨分量 與 對應關系; (b) 級聯失效迭代次數(number of iterations, NOI)Fig. 3. The results of the percolation of RR?RR interde?pendent networks for different , each network has 200000 nodes, average degree is 6, . The symbols repres?ent the simulation results, and the solid linesshow the cor?responding analytical predictions. (a) The size ofthe giant component versus ; (b) number of iterations.

4.2 ER-ER相依網絡

Erd?s?Rényi (ER)網絡[24]的度分布與余度分布生成函數相同, 都為,假設兩個ER網絡具有相同的分布, 那么將兩個生成函數代入(7)式可得方程

上式即為相同度分布的ER?ER相依網絡巨分量方程. 定義如下：

4.3 SF-SF相依網絡

無標度網絡(scale free network, SF)是指服從于分布的隨機網絡, 它的度分布生成函數和余度分布生成函數可以分別近似為[12]：

圖4 不同 值對應的ER?ER相依網絡相變點, 網絡平均度 ,Fig. 4. Graphical solutions of ER?ER interdependent networks transition for different . The average degree is 6, .

圖5 不同 取值的ER?ER相依網絡逾滲, 每個網絡節點數 , 平均度 , , 空心標記為仿真值, 實線為逾滲方程數值解 (a) 巨分量 與 對應關系; (b) 級聯失效迭代次數Fig. 5. The results of the percolation of ER?ER interde?pendent networks for different , each network has 200000 nodes, average degree is 6, . The symbols repres?ent the simulation results, and the solid linesshow the cor?responding analytical predictions. (a) The size ofthe giant component versus ; (b) number of iterations.

圖6 不同依賴度分布的ER?ER相依網絡逾滲,, 分別用實心和空心標記表示, 每個網絡節點數 , 平均度 (a) 巨分量 與對應關系; (b) 級聯失效迭代次數Fig. 6. The results of the percolation of ER?ER interde?pendent networks for different dependency degrees, each network has 200000 nodes, average degree is 6. The depend?ency degrees are (solid symbols) and(empty symbols). (a) The size ofthe giant componentversus ; (b) number of iterations.

圖7 不同 取值的ER?ER相依網絡相變點, 空心標記為仿真結果, 實線是理論值Fig. 7. The critical point versus of ER?ER interde?pendent networks, The symbols represent the simulation results, and the solid linesshow the corresponding analytic?al predictions.

將兩個生成函數代入(7)式可求出巨分量. 圖8給出了不同取值的SF?SF相依網絡逾滲仿真結果.

圖8 不同 取值的SF?SF相依網絡逾滲, 每個網絡節點數 , 平均度 , , , 空心標記為仿真值, 實線為逾滲方程數值解 (a) 巨分量與 對應關系; (b) 級聯失效迭代次數Fig. 8. The results of the percolation of SF?SF interdepend?ent networks for different , each network has 200000 nodes, average degree is 6, , . The sym?bols represent the simulation results, and the solid li?nesshow the corresponding analytical predictions. (a) The size ofthe giant component versus ; (b) number of it?erations.

5 討 論

2) 通過觀察圖3, 圖5以及圖8的仿真結果可以看出, 在本文選取的值范圍內, 三種相依網絡皆不存在二階相變, 這與理論分析的結果吻合.

根據本文理論分析與仿真結果可知, 可從兩個方面提高多依賴相依網絡魯棒性：

2) 增加依賴節點的數量, 若某節點存在更多的依賴節點, 則在相同值的情況下存活節點組合更多, 從而提高該節點存活的概率.

6 結 論

相依網絡的魯棒性正在逐漸引起人們的重視,現實網絡中節點往往會依賴于多個節點, 按照傳統相依網絡逾滲理論, 多依賴性通常會降低網絡魯棒性, 但現實網絡并未因此變得更脆弱. 為了更好地描述現實網絡中的這種現象, 提出了一種相依網絡的條件依賴群逾滲模型, 該模型允許在部分被依賴節點失效情況下依賴節點仍正常工作. 本文在逾滲模型的基礎上, 利用生成函數理論[25]給出了上述具有任意度分布模型的巨分量方程, 通過對三種相依網絡模擬仿真可看出方程的數值解與模擬值相吻合, 驗證了理論的有效性. 雖然理論分析發現對于任意依賴度分布的相依網絡模型, 無論取任何值(除外)都不存在二階逾滲相變, 但仿真結果仍表明隨著取值增大網絡魯棒性會逐漸提高.此外, 對比不同依賴度分布的仿真, 在相同值的情況下, 隨著依賴節點的增多, 網絡魯棒性也會相應地提升. 本文的研究結果對提高現實世界相依系統魯棒性具有一定的科學指導意義, 同時也為后續具有多依賴關系的相依網絡研究提供了借鑒.