復雜加權供應鏈網絡級聯抗毀性研究

趙志剛,周根貴,杜 輝

1(浙江工業大學 計算機科學與技術學院,杭州 310014)2(浙江工業大學 經貿管理學院,杭州 310014)3(浙江傳媒學院,杭州 310018)

1 概 述

復雜網絡的早期研究主要集中在無權網絡,無權網絡僅體現節點間有無連接的概況.但在很多實際網絡中,網絡各個節點間具有不同權值,或者說耦合的強度不同.因此,加權網絡更能描述節點間的緊密程度,能更真實地表達網絡的結構[1].日常生活中電力網絡、交通網絡、通信網絡、物流網絡和供應鏈網絡多是加權網絡.它們在運行過程中常會由于受到攻擊或關鍵節點的故障而引發節點失效.這樣失效節點的負載會流向網絡中的其它節點,導致其它節點負荷超載而失效,這種連鎖的反應過程被稱為級聯失效過程[2,3].級聯失效的破壞效應會迅速蔓延到整個網絡中,大大降低復雜網絡的穩定性和安全性,因此研究級聯失效顯得越來越重要[4].

近些年來,科研人員對復雜網絡的級聯失效已進行諸多研究.Motter和Lai定義節點的初始負荷是節點介數,進而引入一個負載容量線性模型研究網絡的級聯失效[5];丁琳等提出一種新的基于介數的初始負載線性函數,在無標度網絡上建模,對比了節點的度加權和介數加權,研討了加權策略對提高網絡的抗毀性的影響[6];李朝陽等使用節點強度作為節點的初始負荷,以節點容量作為負荷分配依據,比較不同參數下負荷的局部和全局重分配策略對加權BA網絡抗毀性的影響[7];柳虹等也根據節點度和介數等指標較為全面地定義了節點的初始負荷,但失效節點的負荷重分配是根據其相鄰節點的容量比例進行的[8];彭興釗等也把節點強度作為初始負荷并基于BBV模型構建網絡,使用攻擊最大負荷節點和攻擊最小負荷節點兩種策略下,討論控制參數對網絡級聯抗毀性的影響,并比較多種抗毀性指標的可行性[9].黃英藝等結合其定義的節點重要度和節點容量提出一種新的失效負載分流準則,從而建立物流網絡級聯失效模型[10];王甲生等使用非線性的負載容量模型,對加權復雜網絡的冗余資源進行優化分配[11],但冗余容量的分配也是基于邊的初始負荷的比例進行分配的.

以上研究成果的研究涉及到網絡節點(或邊)的初始負荷的定義、容量的定義以及節點失效后負荷重分配原則等方面.但不難發現,節點的初始負荷僅僅限制于表現網絡局部特性的節點度及節點強度或反映網絡全局特性的節點介數,沒有把局部特性和全局特性綜合考慮.此外還應該關注節點的鄰居節點的特性,因為鄰居節點的重要程度對研究失效節點的負荷分配也起著關鍵的作用.對于級聯失效后失效節點的負載重分配問題,文獻也多是根據相鄰節點的度、介數或是容量的比例進行分配的,本文認為更應該考慮相鄰節點現有實際的剩余負載量進行有效地比例分配,這將更符合實際情況,因此有必要對負載-容量模型和如何合理分配失效節點負載的方法進行改進.

2 復雜供應鏈網絡建模及性能指標

2.1 網絡建模

供應鏈網絡是一個復雜適應性系統,它內部的大部分企業都圍繞少數核心企業旁邊,具有“集聚”特征.集聚型供應鏈網絡的特點是無標度性,即度分布符合冪律分布,網中大多數節點度值都不大,但存在著度數高的中樞節點[12,13].供應鏈網絡實際上是復雜加權無標度網絡的在供應鏈企業聯系中的一種應用實例,結合文獻[12],加權建模的方式借鑒文獻[7],構成了本文的加權無標度網絡.

以供應鏈網絡為例建模,復雜供應鏈網絡在其正常運行過程中通常會出現故障或遭受攻擊,網絡將遭遇節點退出或邊的斷裂.當供應鏈網絡中的節點遭到攻擊后,其相鄰企業會通過供應鏈網絡上下游關系把失效負荷進行傳播,所以可把此網絡看成為無向網絡[14].

本文構建的供應鏈網絡是由點集V和邊集E組成的無向加權圖G=(V,E)表示.一個具有N個點的供應鏈網絡可用一個N×N鄰接矩陣表示.A的矩陣元素aij代表企業i和企業j之間的有無供需關系.如果企業節點i與企業節點j之間有直接供需聯系,則aij=1,否則aij=0.給每條邊都賦予相應的權值,該網絡為加權網絡,加權網絡的權值是邊的兩個端節點的度的乘積,這種賦值方式有實證數據為依據,在加權網絡中已得到廣泛的應用,其表達式為[15]:

Wij=aij*(ki*kj)θ

(1)

其中,θ為加權權值調節參數.冪律指數θ決定網絡邊的差異性,同時也決定網絡的加權性,θ越大則各邊之間的差異越大,θ=0時,Wij=Wji=1,網絡退化為無權網絡.除非特別說明,本文為方便計算取θ=1.

2.2 統計特征

節點i的度是與該節點連接邊的條數,即為Ki.介數體現節點或邊的重要程度.節點u的介數是網絡中經過節點u的最短路徑占所有最短路徑的比重.記(i,j)之間的最短路徑的集合為gij.則節點u的介數定義為:

(2)

節點強度Si定義為與該節點相連的所有邊的權值之和:

Si=∑Wij

(3)

其中i∈[1,N],j∈[i+1,N].

2.3 抗毀性衡量標準

1)最大連通子圖的相對大小R

當對網絡的節點或邊進行攻擊后,網絡的抗毀能力會發生改變.因此可用最大連通子圖的相對規模反映網絡在受到攻擊時的抗毀性[16]:

R=N′/N

(4)

其中,N′是網絡級聯失效后,網絡的最大連通子圖的節點數目,N是指原始網絡的節點數目.

2)失效規模

另外一種可以使用相對失效規模表示動態抗毀性.假定網絡失效前總共有N個節點,一個節點i在每一輪會遭受攻擊后失效,繼而會引發CNi個其他節點產生失效,對N個節點則可用歸一化的量CF來表示其抗毀性,計算全網抗毀性的方法如公式(5),其中i∈[1,N].本文采用這種更為通用的方法,CF的值越大代表級聯失效失效節點越多,網絡的抗毀性越弱[17].

CF=∑CNi/N(N-1)

(5)

公式(5)立足角度是依托攻擊節點,使得節點負荷失效進而重分配,從而研究級聯失效的抗毀性的.網絡失效規模與網絡的節點數和邊數都有關系,但節點失效的同時其連接的所有邊也會跟著同時失效,失效的更徹底些;反過來,如網絡中某條邊失效,與該條邊連接的節點不一定失效,只有與該節點連接的所有邊失效,該節點才會失效.本文依托攻擊節點使其失效來綜合體現節點和其聯系的邊的失效現象.文獻[5]到文獻[10]都是基于節點攻擊的,文獻[6]和文獻[17]也是這樣進行歸一化處理,描述失效規模進而反映網絡的抗毀性的.

3 級聯失效模型

3.1 負載容量模型

因此,本文兼顧考慮了節點局部和全局信息以及鄰居信息,采用體現全面性的量Li來表示節點i的初始負載為:

(6)

其中a為權重系數,Bi為節點i的介數,Ki為i的度數,Si為i的節點強度.Kj是節點j的度數,Sj為j的節點強度,節點j是節點i的相鄰節點,Ti表示節點i的所有相鄰節點的集合.五個量是連乘積的形式.i∈[1,N],j∈[i+1,N].

此外,可用常見的比例關系確定節點容量,所以可定義節點i的容量Ci為[17]:

Ci=(1+β)Li(0)

(7)

其中,β≥0,為容忍系數,用來表示節點的負載冗余能力.當β的值越大,節點的容量也越大,此時節點的失效不容易引發級聯失效.但β的值越大網絡成本也會變大,因此存在一個合適的β門限值βc,在網絡容量一定的情況下,既能使得網絡不發生級聯失效,又能保證不浪費網絡資源.βc的值越小,則表明網絡抵制級聯失效的能力越強.

3.2 局部負載重分配原則

級聯失效過程中,故障的空間傳播行為關注的是故障傳播的路徑.已有模型大都假設故障之間是近鄰傳播,當網絡中的節點i失效后,節點i的負載最直接的就是通過其相鄰節點傳輸.節點的負載會按照某種比例分配給其相鄰節點.常用的分配方法多是按相鄰節點的容量比例份額實施的.失效節點i的相鄰節點j從節點i分配到的負載比例為:

(8)

其中,節點k為節點i的相鄰節點,Ti為節點i的相鄰節點集合.

本文改進的失效節點負載分配比例是按照其相鄰節點的當前實際剩余負載量進行的,剩余負載量大的相鄰節點將獲得較大的負載分配量,由此,節點i的相鄰節點j分配到的負載比例為:

(9)

由公式(9)可得相鄰節點j分配到失效節點i的負載ΔLji為:

ΔLji=Lji*Li

(10)

當更新后節點j的負載超出其容量時,即

ΔLji+Lj>Cj

(11)

此時節點j將會過載,繼而引發網絡其它節點的級聯失效.在程序設計上,可以先對網絡中的負載按照降序排列,首先攻擊負載最大的節點,其上面的負載將會分配給相鄰節點.然后通過發現函數find()找到當前攻擊節點的鄰居節點IndexC.設置標識變量flag,當flag=1時按照失效節點的相鄰節點的容量比例分配負荷;當flag=0時按照失效節點的相鄰節點的實際剩余負載比例分配失效節點的負荷.直到網絡中的所有節點都不出現過載現象為止.

本文綜合了局域層面的節點度、節點強度、節點相鄰節點的度之和、相鄰節點強度加權和、以及全局層面的介數指標,定義了網絡的初始負載,繼而引入容忍系數β,建立了負載-容量模型.通過調節合適的a和β值,在以下仿真過程的模型對比分析中可以獲得比只考慮單一因素定義節點負載更全面更好的網絡抗毀性效果.此外本文對失效節點的相鄰節點進行負載重分配時,并沒有依據其原始容量比例分配負載,而是根據其當前實際的剩余可用負載量的比例進行負載重分配,這樣就能合理的“按需分配”,有效控制級聯失效過程的蔓延,從而提高網絡的抗毀性.

4 實驗仿真及分析

本文在Matlab的環境下仿真.度分布表示節點度的概率分布函數P(K).強度分布表示節點強度為S的概率分布函數P(S),它是強度為S的節點在網絡中存在的概率.本文的復雜加權供應鏈網絡模型是在BA網絡基礎上建成,加權權值調節參數θ=1,取初始節點數m0=2,每次新節點連邊老節點數m=2,網絡規模N=500,經過仿真得到如圖1所示的節點度分布圖,圖2所示的是節點強度分布圖.

圖1 加權網絡節點度分布圖Fig.1 Figure of weighted network node degree distribution

由圖1和圖2可見,本加權網絡的節點度分布和節點強度分布呈現出較為明顯的冪率分布,體現出無標度網絡的特征.絕大多數節點的和強度較低,而只有少數節點的和強度較高.

圖2 加權網絡節點強度分布圖Fig.2 Figure of weighted network node strength distribution

4.1 攻擊策略

為研究加權供應鏈網絡的抗毀性,首先把網絡初始化為G=(V,E),具有初始的m0個節點,每次新節點連邊老節點數為m,按照BA網絡生長,并按前面方法進行加權構成網絡.設計的攻擊算法思想是按節點的最大負荷降序依次攻擊節點,對于每一輪攻擊.

具體步驟是:

1)對網絡節點進行負載選擇性攻擊,即將各個節點負荷進行降序排列,從中選取負荷最大的節點移除,若存在多個節點具有相同的最大負荷,則從中隨機選取一個節點移除.

2)對被選定攻擊的當前節點i失效后,對其相鄰節點采用節點實際剩余負載的策略進行負載比例分配,則其相鄰節點j的負載為:

Lj(new)=ΔLji+Lj

(12)

3)對于所有i的鄰接節點j,測試其負載,若新的Lj>Cj,則引起節點j的級聯失效,使j→i,再重復2),否則不變.

4)模擬終止條件:如對網絡中所有的節點k(k=1,2…,n),都有Lk≤Ck,過程結束.

4.2 抗毀性分析

本文研究失效節點的負載分給其相鄰節點有以下幾種負載定義方式對失效負荷進行比例分配:

1) 按度定義負載;

2) 按介數定義負載;

3) 按節點強度定義負載;

4) 按節點個人綜合信息定義負載(節點的度數、強度和介數三者的乘積);

5) 考慮節點鄰居信息情況下,按本文擴展鄰居信息的節點綜合信息定義節點負載,比較其抗毀性.

a為負載權重系數,幾種方式分別為:

1)按節點度衡量節點初始負載

Li(0)=(Ki)a

2)按節點介數衡量節點初始負載

Li(0)=(Bi)a

3)按節點強度衡量節點初始負載

Li(0)=(Si)a

4)按節點個人信息衡量節點初始負載

Li(0)=(Bi*Ki*Si)a

5)考慮節點鄰居信息情況下,按本文擴展鄰居信息的節點綜合信息,衡量節點初始負載:

4.2.1 負載權重系數a與抗毀性的關系

設置β=0.2,a∈[0,2]變化.圖3是不同負載定義下采用公式(9)根據相鄰節點實際剩余負載比例分配負載的a與抗毀性關系圖,圖4是不同負載定義下采用公式(8)根據相鄰節點容量比例分配負載的a與抗毀性關系圖,根據公式(5)的定義,CF值越小,網絡抗毀性越好.由圖3和圖4可以看出,隨著權重系數a的增加,圖中按節點個人信息的負載方式和按本文擴展鄰居節點信息的綜合負載方式由于構造更全面,分配地更合理,使得網絡的抗毀性不斷增加,剩余三種負載分配方式下,網絡抗毀性先減少但后面慢慢增加,不是很穩定.但同一a值情況下,本文的擴展鄰居節點信息的綜合負載方式相比其它四種方式進行負載定義的對應的網絡抗毀性更好.同時,對于同一種負載定義方式而言,比如對圖3和圖4中都采用本文的擴展鄰居節點信息的綜合負載定義方式,圖3中由于采用了公式(9)中改進的對失效節點負載分配比例是按照其相鄰節點的當前實際剩余負載進行比例分配的,從而獲得了比圖4采用公式(8)中對失效節點負載按相鄰節點容量比例分配的方式更好的抗毀性.

圖3 不同負載定義下采用剩余負載分配a與抗毀性關系圖Fig.3 Relationship between parameters a and invulnerability under different load allocation modes by using remaining load

圖4 不同負載定義下采用容量分配a與抗毀性關系圖Fig.4 Relationship between parameters a and invulnerability under different load allocation modes by using capacity load

4.2.2 容忍系數β與抗毀性的關系

設置a=1,β∈[0,1]變化.由圖5可見,隨著容忍系數β的增加,5種負載方式下網絡的抗毀性都增加,網絡成本也在增加.但按本文擴展鄰居節點信息的綜合負載定義下,在采用實際剩余負載方式進行負載比例重分配時的門閾值βc更小,由前面的理論所述,其網絡對應的抗毀性也更好.

4.2.3 平均度與抗毀性的關系

設置a=1,β∈[0,1]變化.按本文擴展鄰居節點信息的綜合負載定義下,在采用實際剩余負載方式進行負載比例重分配時,構造三個加權網絡使得m0=6,10,16,20.根據平均度=2m0,得到=12,20,32,40.由圖6可見,隨著網絡平均度的增加,網絡的抗毀性不斷增大.越大,每個節點的鄰接邊數量就會更多,失效節點把負載可以更好地通過多個鄰接邊進行負載重分配.

4.2.4 加權權值系數與抗毀性的關系

設置a=1,β∈[0,0.25]變化.按本文的擴展鄰居節點信息的綜合負載定義下,在采用實際剩余負載方式進行負載比例重分配時,對于加權網絡權值調節參數θ,使得θ=2,3,5,9.由圖7可見,隨著加權網絡權值調節參數θ的增加,網絡的抗毀性會緩慢增大,但當θ值一定大后,增加就不明顯了.

圖6 本文綜合負載下采用剩余負載分配參數與抗毀性的關系圖Fig.6 Relationship between parameters and invulnerability under integrated load allocation mode by using remaining load

綜上,按照圖3-圖7中的a和β設定的參數值,在本文方法的初始負載定義下,通過運行paremeters_D.m文件,程序計算統計出實驗數據,網絡的基本數據為網絡規模N=500,網絡最大度為54,網絡最小度為2,網絡平均度為3.9880,網絡邊數為997.統計結果顯示隨著a和β的變化,對于不同的a和β值,網絡的基本數據保持不變,網絡中某個特定節點的強度、介數和度數也保持不變,但某個特定節點的初始負載L(0)會隨之發生變化.

圖7 本文綜合負載下采用剩余負載分配參數θ與抗毀性的關系圖Fig.7 Relationship between parameters θ and invulnerability under integrated load allocation mode by using remaining load

5 結束語

本文以復雜供應鏈網絡為例,研究復雜加權網絡的級聯失效過程,定義一種新的節點負載-容量模型.新模型中定義的節點初始負載結合局部和全局兩個方面考慮,失效節點的負荷重分配采用局域重分配原則,依據其相鄰節點的實際剩余負載比例進行分配,更具合理性.通過對復雜加權網絡中5種不同的節點負載模型及負載重分配方案的對比,從失效規模測度研究了網絡的抗毀性.

由仿真結果可得以下了結論:

1)該加權模型的節點度分布和節點強度分布呈現出較為明顯的冪率分布形式,體現出無標度網絡特征;

2)本文在確定節點初始負載進而建立負載-容量模型時,兼顧到節點局部指標和全局指標,充分考慮當前節點的節點度、節點強度、節點介數和其相鄰節點的度加權和及相鄰節點的強度加權和的綜合負載,此外不僅考慮了節點的個人信息,同時也考慮了節點的鄰居信息,因此建立的負載-容量模型更加全面,且從實驗仿真中驗證了有效性;

3)節點失效時,在對失效節點采用局部負載重分配方案時,即對失效節點的相鄰節點進行負載按比例重分配負荷時,考慮的是按其相鄰節點的實時剩余負載而不是相鄰節點的容量進行比例分配,更符合網絡流量分配的實際情況;

4)網絡的抗毀性隨著網絡平均度的增大而變大,啟發可以通過合理加邊提高網絡負載均衡的能力;

5)在冗余資源一定的情況下,本文的擴展鄰居節點信息的節點綜合負載模型及負載重分配方式獲得的抗毀性更好.在冗余資源可變的情況下,達到最佳抗毀性,本文的綜合負載模型及重分配方式可以獲得更小的網絡代價門限βc值;

6)適當提高加權網絡權值調節參數θ的值,有助于提高網絡的抗毀性.

本文研究了復雜加權供應鏈網絡的級聯失效抗毀性,可在有限資源的情況下,通過調節負載-容量模型的參數,優化節點的負載,可控制復雜加權網絡級聯失效的產生和傳播,更好地保護網絡.下步的工作將研究復雜加權網絡在動態變化過程中的風險傳播的模型及其控制的問題.