复杂加权供应链网络级联抗毁性研究

赵志刚,周根贵,杜 辉

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)适当提高加权网络权值调节参数θ的值,有助于提高网络的抗毁性.

本文研究了复杂加权供应链网络的级联失效抗毁性,可在有限资源的情况下,通过调节负载-容量模型的参数,优化节点的负载,可控制复杂加权网络级联失效的产生和传播,更好地保护网络.下步的工作将研究复杂加权网络在动态变化过程中的风险传播的模型及其控制的问题.