相依網(wǎng)絡(luò)的條件依賴群逾滲*

韓偉濤 伊鵬

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

1 引 言

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

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

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

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

2 模 型

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

圖1 具有多依賴關(guān)系的相依網(wǎng)絡(luò)逾滲示意圖, 初始攻擊導(dǎo)致紅色節(jié)點失效, 隨后發(fā)生級聯(lián)失效過程, 最終相依網(wǎng)絡(luò)僅有極少數(shù)節(jié)點存活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.

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

圖2 相依網(wǎng)絡(luò)的條件依賴群逾滲模型 A網(wǎng)絡(luò)節(jié)點隨機依賴于B網(wǎng)絡(luò)的 個節(jié)點( ), 反之亦然; A網(wǎng)絡(luò)的a節(jié)點依賴的3個節(jié)點有一個失效, 但失效比例未超過容忍度 , a節(jié)點繼續(xù)工作; B網(wǎng)絡(luò)的b節(jié)點依賴的節(jié)點失效比例超過 , 所以b節(jié)點失效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 理論分析

本文提出的相依網(wǎng)絡(luò)逾滲模型級聯(lián)失效過程如下.

Step 3： 循環(huán)進行Step 2, Step 3直至相依網(wǎng)絡(luò)中不再有新的節(jié)點失效.

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

對于單個網(wǎng)絡(luò), 聯(lián)立上述兩式可解出巨分量的大小. 傳統(tǒng)的一對一相依網(wǎng)絡(luò)求解與單網(wǎng)絡(luò)相似,這里直接給出[23]

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

其中

4 仿 真

4.1 RR-RR相依網(wǎng)絡(luò)

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

圖3 不同 取值的RR?RR相依網(wǎng)絡(luò)逾滲, 每個網(wǎng)絡(luò)節(jié)點數(shù) , 平均度 , , 空心標記為仿真值, 實線為逾滲方程數(shù)值解 (a) 巨分量 與 對應(yīng)關(guān)系; (b) 級聯(lián)失效迭代次數(shù)(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相依網(wǎng)絡(luò)

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

上式即為相同度分布的ER?ER相依網(wǎng)絡(luò)巨分量方程. 定義如下：

4.3 SF-SF相依網(wǎng)絡(luò)

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

圖4 不同 值對應(yīng)的ER?ER相依網(wǎng)絡(luò)相變點, 網(wǎng)絡(luò)平均度 ,Fig. 4. Graphical solutions of ER?ER interdependent networks transition for different . The average degree is 6, .

圖5 不同 取值的ER?ER相依網(wǎng)絡(luò)逾滲, 每個網(wǎng)絡(luò)節(jié)點數(shù) , 平均度 , , 空心標記為仿真值, 實線為逾滲方程數(shù)值解 (a) 巨分量 與 對應(yīng)關(guān)系; (b) 級聯(lián)失效迭代次數(shù)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相依網(wǎng)絡(luò)逾滲,, 分別用實心和空心標記表示, 每個網(wǎng)絡(luò)節(jié)點數(shù) , 平均度 (a) 巨分量 與對應(yīng)關(guān)系; (b) 級聯(lián)失效迭代次數(shù)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相依網(wǎng)絡(luò)相變點, 空心標記為仿真結(jié)果, 實線是理論值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.

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

圖8 不同 取值的SF?SF相依網(wǎng)絡(luò)逾滲, 每個網(wǎng)絡(luò)節(jié)點數(shù) , 平均度 , , , 空心標記為仿真值, 實線為逾滲方程數(shù)值解 (a) 巨分量與 對應(yīng)關(guān)系; (b) 級聯(lián)失效迭代次數(shù)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的仿真結(jié)果可以看出, 在本文選取的值范圍內(nèi), 三種相依網(wǎng)絡(luò)皆不存在二階相變, 這與理論分析的結(jié)果吻合.

根據(jù)本文理論分析與仿真結(jié)果可知, 可從兩個方面提高多依賴相依網(wǎng)絡(luò)魯棒性：

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

6 結(jié) 論

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