高低階耦合網絡的魯棒性研究

摘要： 為了深入理解現(xiàn)實網絡系統(tǒng)中的相互依賴關系，解決復雜網絡及其高階網絡面臨的級聯(lián)故障問題。提出了一種高低階耦合網絡模型，該模型用于描述復雜網絡（低階網絡）及其高階組織（高階網絡）之間的相互依賴。通過對高低階耦合網絡進行隨機攻擊來分析其脆弱性。研究表明，與單獨的低階網絡相比，高低階耦合網絡在面對隨機攻擊時表現(xiàn)出更高的脆弱性。這一結果強調了在設計和管理復雜網絡系統(tǒng)時考慮高低階網絡相互依賴關系的重要性，尤其是在防止級聯(lián)故障時需要特別關注這些相互依賴結構的脆弱性。

關鍵詞： 高階網絡；相互依賴網絡；級聯(lián)失效；魯棒性

中圖分類號： N94;O157 文獻標識碼： A

Study on the Robustness of High-low-order Coupling Networks

ZHANG Chengjun，YAO Hui， LEI Yi，XIA Denghui，LI Qi，SHEN Xinyu，QIAN Ming，YU Wenbin

（Department of Computer and Software， Nanjing University of Information Science and Technology， Nanjing 210044， China）

Abstract：This paper proposes a high-low-order coupled network model to gain a deeper understanding of the interdependent relationships in real-world network systems and address the cascade failure issues faced by complex networks and their higher-order networks. This model describes the interdependencies between complex networks （lower-order networks） and their higher-order organizations （higher-order networks）. Their vulnerability is analyzed by subjecting the high-low-order coupled networks to random attacks. The study reveals that high-low-order coupled networks exhibit greater vulnerability to random attacks than standalone lower-order networks. This finding underscores the importance of considering the interdependencies between high and low-order networks in designing and managing complex network systems， particularly in preventing cascade failures， where special attention should be paid to the vulnerabilities of these interdependent structures.

Keywords： higher-order organization; interdependent network; cascading failure; robustness

0 引言

隨著人類社會的快速發(fā)展，現(xiàn)實生活中的復雜網絡變得更加龐大、復雜[1]。復雜網絡理論在電力、生物、互聯(lián)網等領域中的作用日益凸顯，復雜網絡發(fā)生故障會對社會生活產生巨大影響。為了解這些故障發(fā)生的原因，以及如何防止復雜網絡發(fā)生故障，復雜網絡的魯棒性研究成為網絡科學中的研究重點[23]。隨著網絡科學的不斷發(fā)展，許多具有重要理論價值的網絡模型被提出[49]，例如：無標度網絡模型、小世界網絡模型等，這些網絡模型的研究極大推動了復雜網絡魯棒性研究的發(fā)展。過去幾十年內，復雜網絡魯棒性研究進展大致分為兩個階段：第1階段為單個網絡的魯棒性研究。Albert等[10]首先對單個網絡進行了隨機攻擊和蓄意攻擊，研究結果表明無標度網絡對隨機攻擊的容忍能力很高，對蓄意攻擊的容忍能力很差。Cohen等[11]在Albert等人工作的基礎上，采用滲流理論，對無標度網絡遭受攻擊后的相變點進行研究，研究結果表明即使網絡中的大部分節(jié)點因隨機攻擊而失效，網絡中仍然存在能夠正常工作的巨分量。基于Albert[10]和Cohen等[1112]的研究成果，學者們對單個網絡的魯棒性進行了更加深入的研究。例如，Cohen等[12]對無標度網絡和隨機網絡的魯棒性進行研究，他們詳細分析了不同程度的蓄意攻擊對網絡魯棒性的影響，從理論上證明了無標度網絡在蓄意攻擊下具有脆弱性。Frutos等[13]研究了西班牙最大的馬德里地鐵網絡的魯棒性，研究結果表明馬德里地鐵網絡比其他交通網絡更容易受到攻擊。第2階段為相互依賴網絡的魯棒性研究，2010年，Buldyre等[14]開創(chuàng)性地提出了相互依賴網絡模型，并對相互依賴網絡的魯棒性進行研究。現(xiàn)實中的網絡普遍存在著依賴關系，相互依賴網絡的魯棒性研究具有很強的現(xiàn)實意義。Parshani等[15]在Buldyre的研究基礎上提出了部分依賴網絡模型，依賴網絡中的節(jié)點可能不是全部相互依賴，僅僅是部分節(jié)點相互依賴，并且發(fā)現(xiàn)部分依賴網絡的魯棒性更強。之后，Parshani等[16]發(fā)現(xiàn)網絡的依賴關系不僅存在于依賴網絡中，單個網絡中也可能存在相互依賴關系，單個網絡中的部分節(jié)點可能相互依賴，存在相互依賴連邊，因此提出了含有依賴邊的單個網絡模型。此后更多的依賴網絡模型被提出，相互依賴網絡的基本理論也越發(fā)完善，也為今后的相互依賴網絡的研究提供了理論基礎[1721]。

上述的魯棒性研究都是在“點—邊”為基本單元的低階網絡上展開的，低階網絡往往會忽視節(jié)點之間的高階交互關系，隨著對現(xiàn)實世界的不斷深入探索，學者們發(fā)現(xiàn)在真實網絡中，節(jié)點個體之間不僅存在二元交互關系，也廣泛存在多個節(jié)點同時（或以特定順序）進行交互，即高階交互關系。例如，在社交網絡中，合作關系往往同時發(fā)生在多個個人之間，比如多名學者共同完成一篇科研文章。而Benson等[22]提出的基于模體的高階網絡就能夠體現(xiàn)這些高階交互關系，同時高階網絡對網絡的功能至關重要。過去，學者們都是將低階網絡和高階網絡孤立起來研究，鑒于此，本文針對低階網絡和高階網絡之間的依賴關系，提出了一種無向網絡的高低階耦合網絡模型，并對高低階耦合網絡的魯棒性進行研究。

1 相關理論

1.1 高階網絡與模體

真實網絡中存在著大量具有交互性、傳遞性的子圖結構，這些子圖結構又被稱為網絡模體，而真實網絡存在以網絡模體為基本單元的高階網絡結構[23]。網絡模體是高階網絡的一種重要的表現(xiàn)形式[22]。根據模體中的節(jié)點數(shù)量，可以將模體分為三階模體、四階模體等。通常選擇三階模體或四階模體作為基本研究單元，因為真實網絡中更高階模體的數(shù)量較少。在無向網絡中，通常將3個節(jié)點組成的全連接結構作為三階模體，如圖1所示。

定義1 基于模體的鄰接矩陣。給定一個模體M，對于擁有N個節(jié)點的網絡G，其基于M的高階鄰接矩陣可以定義為WM=wijN×N，矩陣元素wij為G中連邊eij在模體M中出現(xiàn)的次數(shù)，可定義為

wij=∑1，eij∈M且i≠j0，其他（1）

定義2 高階網絡。高階網絡表示為G=V，E，WM，其中V=vi|i=，…，n表示點集，E=eij|i，j=，…，m表示邊集，eij是一條由節(jié)點vi指向節(jié)點vj的連邊，WM是基于模體M的高階鄰接矩陣。

1.2 網絡攻擊策略和評價指標

1.2.1 攻擊策略

本文采用隨機攻擊的方法對網絡進行攻擊，模擬網絡中某個節(jié)點受到了意外情況而失效。在隨機攻擊方法中，隨機移除網絡中的節(jié)點，無需考慮節(jié)點之間的區(qū)別。

1.2.2 評價指標

網絡發(fā)生故障或者遭受攻擊時會分裂成多個規(guī)模不同的連通分量，其中規(guī)模最大的分量被稱為巨型強連通分量。隨機從網絡中移除1-p的節(jié)點，以此來模擬網絡的級聯(lián)故障，當網絡剩余節(jié)點p達到臨界值pC時，網絡開始出現(xiàn)巨型強連通分量。用PSymboleB@表示巨型強連通分量中節(jié)點個數(shù)與總節(jié)點的比例，PSymboleB@可表示為SymboleB@=nN（2）

其中，n為巨型強連通分量中的節(jié)點個數(shù)，而N為原始低階網絡的節(jié)點個數(shù)。對于低階網絡的滲流，也就是單個網絡的滲流，通常表征為二階滲流相變，可利用PSymboleB@（p）和p表示，其中PSymboleB@（p）為p的連續(xù)函數(shù)。本文基于相互依賴網絡的基本理論，將低階網絡和高階網絡相互依賴，當?shù)碗A網絡被隨機移除1－p的節(jié)點后，低階網絡會分裂成多個連通分量，高低階耦合網絡將發(fā)生相繼故障，直到低階網絡和高階網絡的巨型強連通分量相同時，高低階耦合網絡達到一個穩(wěn)定的狀態(tài)，利用穩(wěn)定時低階網絡的巨型強連通分量的變化情況來研究該高低階耦合網絡的魯棒性。

2 高低階耦合網絡

本文提出了無向網絡的高低階耦合網絡模型。無向三元閉合結構（三個節(jié)點的全連接結構）是無向網絡的三階模體，即三階閉包模體，通過該三階模體可以構建無向網絡的高階網絡模型。低階網絡與高階網絡之間存在依賴關系，通過該依賴關系構建高低階耦合網絡模型。

簡單起見，新建兩個網絡A和B，其中網絡A是一個獨立的無向網絡，同時它也是低階網絡。再以無向三元閉合結構作為三階模體，構建網絡A的高階網絡，即網絡B。兩個網絡的節(jié)點數(shù)相同，并且在網絡A和網絡B中構建一對一的依賴連邊。如圖2所示，藍色無向網絡為低階網絡，綠色無向網絡為低階網絡的高階網絡。攻擊低階網絡中的節(jié)點4、7，高階網絡中的節(jié)點4、7失效，同時高階網絡中節(jié)點4、7所在模體的其他節(jié)點0、5、6、8、9也同樣失效，高低階耦合網絡發(fā)生相繼故障后，各自的最大連通子圖都只有3個節(jié)點。

3 實驗

為研究高低階耦合網絡的魯棒性，本文構建了ER、SW、BA網絡的高低階耦合網絡，同時也將高低階耦合網絡模型應用于20個真實網絡中，對低階網絡進行隨機攻擊，研究高低階耦合網絡的魯棒性，并和其低階網絡的魯棒性進行對比。

3.1 實驗數(shù)據集

為研究多種場景下高低階耦合網絡的魯棒性，本文選擇了20個不同領域的真實網絡數(shù)據集，其中包括合作網絡（CSphd、Erdos、Netscience、f0d85d7e3a5a0f533dea4291724e71c52439d94a89b827b143db5e96aff043b7Jazz）、電子郵件網絡（ArenasEmail）、生物網絡（BDH、BCG、Celgans）、雜項網絡（Name、G51、Si2、MSC、Plat、NASA）、社交互動網絡（Socwiki、IaInfect）、電力網絡（Bus、Bcs09、Bcs06）、生態(tài)網絡（Wildbird），這些數(shù)據集全部來自文獻[24]。具體的真實網絡的基本屬性如表1所示。表1中N為網絡的節(jié)點總數(shù)，E為網絡連邊總數(shù)，〈k〉為網絡的平均度，C為網絡的集聚系數(shù)。本文選取的真實網絡的平均度范圍在 32之間。

3.2 實驗結果分析

圖3展示了低階網絡遭受隨機攻擊后，低階網絡和其高低階耦合網絡的魯棒性比較。其中圖3中的網絡的相關參數(shù)為：低階網絡的節(jié)點數(shù)為1 000，SW網絡的斷邊重連概率為0.05，BA網絡的度分布的冪指數(shù)為-3，圖3b中的低階網絡的平均度〈k〉為16，Low曲線為低階網絡PSymboleB@變化情況，Low-High曲線為高低階耦合網絡的PSymboleB@變化情況。

如圖3a所示，當?shù)碗A網絡的節(jié)點數(shù)相同時，網絡的平均度〈k〉越大，低階網絡的魯棒性就越強，即低階網絡的魯棒性與平均度成正比。對于ER、SW、BA網絡來說，網絡的平均度越大，說明網絡中任意兩個節(jié)點之間的連通路徑就越多，即使網絡被移除部分節(jié)點后，其余節(jié)點仍然能夠保持良好的連通性，因此平均度大的網絡具有較強的魯棒性。接著，本文生成了節(jié)點數(shù)為1 000、平均度為16的ER、SW、BA網絡，并對它們進行隨機攻擊，以研究低階網絡和其高低階耦合網絡的魯棒性，結果如圖3b所示?？梢园l(fā)現(xiàn)ER、BA、SW低階網絡的滲流皆為連續(xù)相變，BA、ER高低階耦合網絡的滲流同樣也是連續(xù)相變，而SW高低階耦合網絡的滲流卻是不連續(xù)相變，這說明SW高低階耦合網絡對于隨機攻擊比較敏感。ER、BA網絡未被攻擊時，其高階網絡擁有多個子圖分量，因此高低階耦合網絡同樣發(fā)生相繼故障，即當p=1時，高低階耦合網絡的PSymboleB@值不為1。同時從圖3b中也可以發(fā)現(xiàn)，ER、BA、SW網絡的Low曲線均在Low-High曲線的上方，這說明低階網絡PSymboleB@的下降速度比高低階耦合網絡快，這也意味著低階網絡的魯棒性比高低階耦合網絡強，即高低階耦合網絡比較脆弱。

圖3b中的低階網絡的節(jié)點數(shù)和平均度均相同，低階網絡遭受隨機攻擊后，ER、BA、SW的高低階耦合網絡的魯棒性都比其低階網絡脆弱。于是本文將ER、BA、SW網絡的規(guī)模設置為相同的數(shù)值，通過調整網絡的平均度，研究低階網絡和其高低階耦合網絡的魯棒性變化。在這一實驗中，本文采用了PSymboleB@變化曲線的曲線下面積R來評估網絡的魯棒性，R的值越大，說明網絡的魯棒性越強。相關實驗結果如圖4所示，圖4網絡的相關參數(shù)：低階網絡的節(jié)點數(shù)均為1 000，低階網絡的平均度調整范圍為〈k〉∈4，6，8，…，32。

如圖4所示，低階網絡遭受隨機攻擊后，無論低階網絡的平均度如何變化，低階網絡的R值均大于高低階耦合網絡的R值，即高低階耦合網絡的魯棒性比低階網絡差。在低階網絡規(guī)模相同的情況下，隨著低階網絡平均度的增大，低階網絡的R也在緩慢增大，且低階網絡的R值普遍大于0.4，這說明低階網絡應對隨機攻擊的能力很強。在無向網絡中，網絡的平均度越大，則說明網絡中的冗余連邊多，網絡即便被移除部分節(jié)點，其余節(jié)點仍然有路徑連通，導致低階網絡的PSymboleB@的變化曲線接近曲線y=x，即低階網絡的R接近0.5。而對于高低階耦合網絡，低階網絡的平均度越小，高低階耦合網絡的魯棒性就越脆弱。當?shù)碗A網絡的平均度小于10時，ER、BA、SW高低階耦合網絡的R均小于0.2，尤其是ER高低階耦合網絡的R幾乎等于0，而且與其對應的低階網絡的R相比差異巨大，這些都表明高低階耦合網絡十分脆弱。但是隨著低階網絡平均度的增大，高低階耦合網絡的R值也在逐漸上升，高低階耦合網絡的魯棒性與低階網絡的平均度成正比，同時低階網絡和高低階耦合網絡的魯棒性差異也在不斷減小。

圖5展示了當?shù)碗A網絡規(guī)模相同時，低階網絡平均度對高低階耦合網絡的魯棒性影響，結果表明高低階耦合網絡的魯棒性與平均度成正比。接著本文將ER、BA、SW網絡的平均度設置為定值，通過調整網絡的節(jié)點規(guī)模，研究高低階耦合網絡的魯棒性。相關實驗結果如圖5所示，圖中網絡的相關參數(shù)為：低階網絡節(jié)點數(shù)調整范圍為N∈100，500，1 000，2 000，低階網絡的平均度范圍為〈k〉∈4，6，…，32。

在圖5a中，當?shù)碗A網絡的平均度相同時，節(jié)點數(shù)規(guī)模N增大，低階網絡的R值幾乎沒有變化，這說明低階網絡的魯棒性與節(jié)點數(shù)規(guī)模無關。然而在圖5b中，當?shù)碗A網絡的平均度相同時，隨著節(jié)點規(guī)模N的增大，高低階耦合網絡的R值在逐漸減小，這一現(xiàn)象在ER、BA高低階耦合網絡中尤為明顯，這些都表明高低階耦合網絡的魯棒性與節(jié)點規(guī)模成反比。

在上述實驗中，本文研究了ER、SW、BA網絡中低階網絡和高低階耦合網絡的魯棒性，研究結果表明低階網絡比高低階耦合網絡強健。那么現(xiàn)實中的真實網絡是否也存在這樣的現(xiàn)象，本文接下來將構建真實網絡的高低階耦合網絡模型，并研究它們的魯棒性。

圖6展示了不同平均度的真實網絡被隨機攻擊后，其低階網絡和高低階耦合網絡的魯棒性。這20個真實網絡中低階網絡的R值均大于其高低階耦合網絡的R值，這說明這些真實網絡的低階網絡魯棒性要強于其高低階耦合網絡的魯棒性，即高低階耦合網絡比較脆弱。真實網絡的平均度越大，其高低階耦合網絡抵抗隨機攻擊的能力越強，且與低階網絡的魯棒性差異也越小。

4 結語

本文提出了一種無向網絡的高低階耦合網絡模型，采用隨機攻擊的方法，對高低階耦合網絡的魯棒性進行研究。在ER、SW、BA網絡中，其低階網絡的魯棒性要強于高低階耦合網絡，并且高低階耦合網絡的魯棒性與低階網絡的平均度成正比，與低階網絡的節(jié)點規(guī)模成反比。同樣在20個不同領域的真實網絡中，其高低階耦合網絡的魯棒性也比低階網絡脆弱，平均度越大的真實網絡，其高低階耦合網絡的魯棒性也越強。

綜上，在無向網絡中，高低階耦合網絡要比低階網絡脆弱，復雜網絡會隨著低階網絡和高階網絡的相互依賴而變得脆弱。傳統(tǒng)網絡科學認為復雜網絡的魯棒性與網絡節(jié)點規(guī)模無關，但是本文研究發(fā)現(xiàn)當復雜網絡中的高低階網絡耦合以后，低階網絡的節(jié)點規(guī)模越大，高低階耦合網絡的魯棒性就越差，這個結論與傳統(tǒng)復雜網絡魯棒性研究的結論完全不一致，該結論也對未來的網絡魯棒性研究具有了一定的指導意義。

參考文獻：

[1]NICOL D M， YAN G. High-performance simulation of low-resolution network flows[J]. Simulation， 2006， 82（1）： 2142.

[2]WERNER N E， BUMPUS M F， ROCK D. Involvement in internet aggression during early adolescence[J]. J Youth Adolesc， 2010， 39（6）： 607619.

[3]BABA T， MATSUDA S. Tracing network attacks to their sources[J]. IEEE Internet Computing， 2002， 6（2）： 2026.

[4]ERDS P， RNYI A. On random graphs[J]. Publicationes Mathematicae Debrecen， 1959， 6： 290297.

[5]ERDS P， RNYI A. On the evolution of random graphs[J]. Publications of the Mathematical Institute of the Hungarian Academy of Sciences， 1960， 5（1）： 1760.

[6]PRICE D. Networks of scientific papers[J]. Science， 1965， 149（3683）： 510515.

[7]PRICE D. A general theory of bibliometric and other cumulative advantage processes[J]. Journal of the American Society for Information Science， 1976， 27（5）： 292306.

[8]WATTS D J， STROGATZ S H. Collective dynamics of "small-world" networks[J]. Nature， 1998， 393（6684）： 440442.

[9]BARABSI A， ALBERT R. Emergence of scaling in random networks[J]. Science， 1999， 286（5439）： 509512.

[10] ALBERT R， JEONG H， BARABSI A. Error and attack tolerance of complex networks[J]. Nature， 2000， 406（6794）： 378382.

[11] COHEN R， EREZ K， BEN-AVRAHAM D， HAVLIN S. Resilience of the internet to random breakdowns[J]. Physical Review Letters， 2000， 85（21）： 46264628.

[12] COHEN R， EREZ K， BEN-AVRAHAM D， et al. Breakdown of the internet under intentional attack[J]. Physical Review Letters， 200 86（16）： 3682.

[13] FRUTOS B E， MART N R A. Study of the structural and robustness characteristics of madrid metro network[J]. Sustainability， 2019， 11（12）： 3486.

[14] BULDYREV S V， PARSHANI R， PAUL G， et al. Catastrophic cascade of failures in interdependent networks[J]. Nature， 2010， 464（7291）： 10251028.

[15] PARSHANI R， BULDYREV S V， HAVLIN S. Interdependent networks： reducing the coupling strength leads to a change from a first to second order percolation transition[J]. Physical Review Letters， 2010， 105（4）： 048701.

[16] PARSHANI R， BULDYREV S V， HAVLIN S. Critical effect of dependency groups on the function of networks[J]. Proceedings of the National Academy of Sciences， 201 108（3）： 10071010.

[17] RADICCHI F. Percolation in real interdependent networks[J]. Nature Physics， 2015， 11（7）： 597602.

[18] SUN S， WU Y， MA Y， et al. Impact of degree heterogeneity on attack vulnerability of interdependent networks[J]. Scientific Reports， 2016， 6： 32983.

[19] BAI Y N， HUANG N， WANG L， et al. Robustn39eb0f3d76d0dd829fd076480f9975848f5f736e5045e1b4a15ca1847be14ad5ess and vulnerability of networks with dynamical dependency groups[J]. Scientific Reports， 2016， 6： 37749.

[20] SMOLYAK A， LEVY O， VODENSKA I， et al. Mitigation of cascading failures in complex networks[J]. Scientific Reports， 2020， 10（1）： 16124.

[21] TURALSKA M， SWAMI A. Greedy control of cascading failures in interdependent networks[J]. Scientific Reports， 202 11（1）： 110.

[22] BENSON A R， GLEICH D F， LESKOVEC J. Higher-order organization of complex networks[J]. Science， 2016， 353（6295）： 163166.

[23] YIN H， BENSON A R， LESKOVEC J， et al. Local higher-order graph clustering[DB/OL].[20220915].https：//dl.acm.org/doi/proceedings/10.1145/3097983.

[24] ROSSI R， AHMED N. The network data repository with interactive graph analytics and visualization[DB/OL].[20220915].https：//dl.acm.org/doi/10.5555/28881162888372.

（責任編輯 耿金花）