【处于单一层面的多关系网络级联失效分析7100字】

收稿日期：基金项目：山东省自然基金面上项目（ZR2017MG011）；教育部人文社会科学研究青年项目（15YJC860001）；山东省社会科学规划项目（17CHLJ16）作者简介：贾宁（1996-），男，辽宁省锦州市，硕士研究生，主要研究领域为复杂网络。Email：1227669848@孙更新（1978-），男（汉族），青岛人，青岛大学副教授。主要从事复杂网络研究,近年来着重于探索复杂网络中传播动力学及相关传播模型。Email：sungengxin@而多关系网络是由彼此之间存在多种作用关系的个体组成，例如城市交通网络：城市代表网络中的个体，交通线路代表个体间的连边，影响客流量的多种因素代表个体间的关系，根据多子网复合复杂网络模型初始构建多关系网络A，用四元组GAVA={vEA={<vRA={r1,…,FA构建的多关系网络A如图1.3所示。每个关系关联的节点和连边的数量分别设Nr1,Nr2,Nr3和Er1,Er2,Er3，节点图1.3多关系网络A1.1.2多关系网络级联失效模型在现实中，个体之间普遍存在多种作用关系，每种关系对负载传输量的影响是不同的，所以单纯考虑一种关系必然会与实际有所差异，因此建模应当考虑多种关系的影响。例如在交通网络中，每条交通线路上都可能出现一些突发事件，这些事件相当于不同的影响因素，每种因素对单位时间内通过线路上的客流量产生的影响不同，且流量通常与两端节点的度关联，所以将连边vhvkFv其中，kvhri表示节点正向关系促进负载的流通，使得单位时间内通过连边的负载增大，也导致节点承担的负载增大；而逆向关系会阻碍负载的流通，导致节点先前积累的负载不能及时释放出去，如果有大量带有逆向关系的连边与节点相连，节点承担的负载会非常大。因此综合二者的影响，将节点初始负载定义为节点关于各个关系的流量之和：Lv其中riϵR，R表示与节点vh关联的关系集合。Γvhri是节点节点容量的大小受节点间多种关系的影响，初始负载的定义通过流量描述了关系对节点的影响，所以节点容量仍与初始负载相关联，节点vhCv负载重分配策略普遍采用局域择优重分配，由于该方法不能识别关键节点，容易导致桥节点失效，使得网络的故障规模增大，而节点重要性能反映节点的繁忙程度，当网络发生级联失效时，令重要性高的节点分配少量负载，能有效减小网络规模故障，因此本文根据节点重要性制定负载重分配策略。由于网络中节点和连边相互依存相互影响，与节点相连的边越重要节点就越重要，所以结合多种关系根据如下三个步骤定义节点的重要性：首先，连边两端节点的度越大，该边所能联通的路径的条数就越多，该边也就越重要，如果有其他连边能够取代该边的联通功能，则该边的重要性下降，连边vhvlIvh其中pvhvlr其次，每个端节点由于属性的不同而对边的重要性的贡献比例不同，对边重要性贡献大的节点受到边重要性的影响也应该偏大，对边重要性贡献小的节点受边重要性的影响就应该偏小，节点vl对于连边vhvev最后，节点vl关于关系rWv与单个网络的负载分配方式不同，在多关系网络中，每个关系对负载传输的影响不同，负载的分配应当考虑多种影响因素，以交通网络为例，假设网络中存在正向关系和逆向关系，正向关系表示增加客流量的因素，逆向关系表示减少客流量的因素，节点失效表示城市中大量人口的滞留，根据不同的情境采取的负载重分配方案如下：当部分地区为了促进经济增长，而开通车次时，失效节点与邻居节点间只有正向关系，开通的车次越多，客流量就越大，所以正向关系强度越大，通过的负载就越大，失效节点分配给邻居节点关于关系ri△L其中，sfi表示正向关系ri对负载传输的促进程度，且0<sfi，R+为失效节点与邻居节点间的正向关系集合，当部分地区因突发因素导致城市之间大量交通方式停运时，失效节点与邻居节点间只有逆向关系，虽然逆向关系会阻碍负载的传输，但是不会全部阻碍，如果不存在正向关系，则只导致负载传输速率减慢，负载传输的总量不受影响，因此分配给邻居节点关于关系rj△L其中，R−为失效节点与邻居节点间的逆向关系集合，Ωvhr当部分地区因道路维护，令某些交通方式的运行班次停运，而开通其它交通方式的运行班次时，失效节点与邻居节点间同时存在正向关系和逆向关系，逆向关系会阻挡住一部分负载，且逆向关系强度越大，对负载的阻碍作用越明显，设关系rj为逆向关系，失效节点分配给邻居节点关于关系r△L其中，△Lvhvlrj表示节点vh传递给节点vl关于逆向关系rj由于存在正向关系，被逆向关系阻挡住的负载会倾向于从正向关系传递给其他节点，例如列车部分车次停运，人们为了换乘会乘坐其它的交通方式，如果开通的班次越多，人们就越倾向于使用该交通方式，所以负载倾向于从关系强度大的正向关系流向其他节点，失效节点分配给邻居节点关于关系ri△L△Lvhvlri表示节点vh传递给节点vl关于正向关系ri的负载，R+为失效节点与邻居节点间的正向关系集合，R−邻居节点vl与失效节点vh之间存在多种关系，节点LvlRt=L如果此时节点的总负载大于容量，即：Lv则节点vl因超负荷而失效，其自身负载会沿着连边上的关系传递给它的邻居节点，具体过程如图1.图1.4多关系网络负载分配策略由图1.4可以看出，节点vh故障后，其负载根据连边上三个关系依次传递给节点vl，该节点接收到的负载为△Lvhvl为了更好的描述整个网络中每个节点的状态，本文对每个节点定义一个过载函数值Gk，相当于对每个节点分配一个动态权重，表示节点过载的难度，假设网络中每个节点只有‘正常’和‘失效’两种状态，1表示所有节点处于正常状态，0表示节点处于失效状态，所以节点vGk=1，Lv0即不用移除节点就能显示整个网络的状态。1.1.3鲁棒性评测网络的构建都有成本限制，一般将网络构建成本定义为所有节点的容量与初始负载的比值：E=v∈N其中，N为网络节点总数。将公式3-(3)带入到3-(14)中后得出：E=v∈N网络的构建成本取决于容限系数。为了探究不同影响因素对网络总体的破坏程度，对网络中每一个节点进行攻击，并在每一次级联失效过程结束后计算CFv值，该值表示为移除节点v后失效节点的数量，很显然，0≤CFv≤N−1，再将S=v∈NCFvS的大小衡量了整个网络被破坏的平均程度。S越大，表示网络故障规模越大，网络鲁棒性越差；相反S越小，网络鲁棒性越强。网络构建成本存在一个阈值λcS=0，λ>λ当λ>λc时，网络中不会发生级联失效，当λ<λ1.2实验仿真和结果分析通过调节控制节点容量系数λ和选取不同的关系强度比例参数来进行仿真实验，重点考察正向关系和逆向关系对多关系网络级联失效的影响，本文根据多关系网络级联失效模型，其算法如下：a)攻击网络A中的节点v使其失效，将该节点的过载函数值记为“0”，并找出与v相连的邻居节点；b)对节点v和其邻居节点的负荷进行重分配，有节点过载则将其过载函数记为“0”；c)找出网络A中的失效节点；d)找出其中一个失效节点的全部邻居节点，对失效节点和其邻居节点进行负载重分配，其中，过载函数值为“0”的节点不再接受外来负荷，有节点过载则将其记为“0”；e)重复步骤c)-d)，直到没有节点失效；f)计算整个网络中失效节点的数目记为CFvg)重复步骤a)-f)，直到完成对网络A中每个节点进行了一次攻击，计算网络A的故障规模S。1.2.1网内关系拓扑结构不同条件下关系强度对多关系网络级联失效的影响1)正向关系对多关系网络级联失效的影响在典型的单网络模型中，节点处于同一层次，节点之间只存在单个关系；在多层网络中，每个子网络中的节点属于不同类别且处于不同层次，节点之间存在耦合关系；而在构建的多关系网络模型中，虽然每个节点属于同一类别且都处于同一层次，但节点之间的连边上存在多种关系，节点根据每个关系组成的网络拓扑特征是不同的，因此本文的模型与以往的网络模型相比存在本质上的差别，当关系强度比例参数取不同值时，网络中发生的故障现象将出现不同的性质。为了探究在网内关系对应的网络拓扑结构不同条件下，正向对网络级联失效的影响，首先构建关系r1,r2,r3关联的节点数目为200，连边数目为400，每个关系对应的网络平均度都为4的多关系网络，其中，关系r1,r3为正向关系，关系r2为逆向关系，由于现实网络系统更倾向于WS小世界网络和BA无标度网络，因此在实验中，将每个关系对应的网络拓扑结构为WS,BA其一进行任意组合，设参数（a）WS:WS:WS(b)BA:BA:BA（c）WS:BA:BA（d）WS:WS:BA图1.5在网内拓扑结构不同条件下，正向关系对网络的影响由图1.5可知：在上述实验中可以看出，关系对应的拓扑结构为不同的组合时，取得的实验结果一致：当正向关系r1,r3的关系强度比例为1:1时，网络损毁规模达到0所需的容限系数因此可以得出结论：在网内关系对应的拓扑结构不同条件下，当正向关系强度都一致时，网络鲁棒性最佳。2)逆向关系对多关系网络级联失效的影响由于被逆向关系阻挡住的负载会沿着正向关系传递给其他节点，导致这些节点分配到更多的负载，阻碍程度的大小会对网络故障规模产生一定的影响，因此为了进一步研究，按照上述实验的网络特征，令每个关系对应的网络拓扑结构为WS,BA中的一种，以任意形式进行组合，构建多关系网络。设参数α为1，将正向关系r1,r3的强度比例固定为1:1。当逆向关系强度分别取0.1，0.3，0.5，0.7，0.9时，得出的（a）WS:WS:WS(b)BA:BA:BA（c）WS:BA:BA(d)WS:WS:BA图1.6在网内拓扑结构不同条件下，逆向关系对网络的影响由图1.6可知：上述实验取得的结果一致，随着逆向关系r2强度的增强，网络损毁规模达到0所需的容限系数随之增大，网络鲁棒性明显下降。因此可以得出结论：在网内关系对应的拓扑结构不同条件下，逆向关系对网络的影响是负面的，逆向关系强度越强，网络鲁棒性越差，为了保护网络，我们应该尽量减少逆向关系对负载的阻碍程度，以避免其他邻居节点分配的负载过大。1.2.2网络平均度不同条件下关系强度对多关系网络的影响1)正向关系对多关系网络级联失效的影响网络平均度是反映网络整体的平均交互程度，本文定义的鲁棒性测度S表示网络整体的平均故障程度，所选指标和测度都是均值，因此实验中不会受网络个别因素的影响，而且网络平均度是复杂网络级联失效研究中普遍应用的指标，因此该指标具有合理性。以往文献的研究表明：网络平均度越大，网络抵御级联失效的能力越强。但在多关系网络中，节点间存在多种关系，且存在着不同的关系类型，当每个关系对应的网络平均度不同时，网络中发生的级联失效现象会以往的研究有所差异。为了进一步研究，首先探究正向关系对网络的影响，在实验中，构建网内关系拓扑结构都为WS的多关系网络，且每个关系关联的节点数目相同，网络总节点数为200，设参数α为1，关系r1,r3为正向关系，关系r2为逆向关系，固定逆向关系强度为0.1，关系r1,(a)网内关系平均度分别为2,4,2(b)网内关系平均度分别为2,4,4(c)网内关系平均度分别为2,4,6(d)网内关系平均度分别为2,4,8图1.7在网内关系平均度不同条件下，正向关系对网络的影响由图1.7可知：在图（a）和（b）中，当关系r1,r3强度比例为1:1时，网络鲁棒性最强，随着关系在图（c）和（d）中发现：随着关系r3平均度的增大，关系r1,r3综上所述，在网内关系平均度不同条件下，网络平均度小的关系的强度占比越小，网络平均度大的关系的强度占比越大，网络抵御级联失效的能力越强。2)逆向关系对多关系网络级联失效的影响前面实验得出结论：逆向关系对网络影响是负面的，但是在每个关系平均度相同条件下证明的，因此在本实验中令正向关系和逆向关系对应的平均度不同，探究逆向关系对网络的影响。首先构建网络节点总数为200，网络拓扑结构都为WS的多关系网络，令每个关系关联的节点数目相同，参数α为1，关系r1,r3为正向关系，关系r2为逆向关系，固定正向关系r(a)网内关系平均度分别为4,2,4