级联失效matlab,加权无标度网络的级联失效模型

社交网、交通网、通信网等领域均呈现无标度特性[, 是复杂网络中常见的一种现象, 不同网络中的节点和边都承载着不同形式的负载, 且负载的承受能力是有限的.加权无标度网络是指节点和边根据权值构建成的网络[, 应用在专家网等领域.

在复杂网络中, 节点和边承担的负载是不断演化的, 具有一定的动力学特征, 当节点或边的负载大于自身容量而导致失效后, 使得失效节点或边的负载通过网络的相互连接被重新分配到相关节点或边上, 从而引起其他节点或边失效, 产生级联效应, 进而可能导致整个网络的瘫痪[, 这种由微小事件引发的连锁故障称为级联失效.在现实世界中, 由级联失效引发的故障包括北美电力网崩溃事故、Internet阻塞、交通堵塞以及经济危机等.因此, 构建合理、完善的级联失效模型, 并分析参数对级联失效的影响, 对提升网络的鲁棒性具有重要的意义[.

近年来, 级联失效的研究主要基于复杂网络, 其中以无标度网络为主, 主要是从节点的初始负载、节点容量与初始负载的关系、节点失效后负载重分配规则这3个方面进行研究.复杂网络的主要特性包括节点度、集聚系数和平均最短路径长度, 其中, 节点度(包括邻居节点度)对节点负载起到决定性作用, 其属于局域范畴; 平均最短路径长度通过介数的表达方式体现出对节点负载的影响, 其属于全局范畴; 集聚系数表示网络中节点聚集程度的系数, 与节点负载没有密切关系.在加权的复杂网络中, 还需要考虑节点权重对负载的影响.因此, 节点的初始负载通常定义为关于度、介数或者邻居度的幂函数, 幂指数是用来控制初始负载强度的参数; 负载重分配主要考虑邻居的容量、负载、度数和与失效节点的距离等因素; 节点的容量必然要大于节点的初始负载, 一般定义为关于初始负载的比例函数.在这些方面, 段等人[基于初始负载与度的幂函数关系, 构建关于距离和节点度的择优分配规则, 分析了负载重分配的范围和均匀性.Yin[和Liu[等人同样采用关于度的初始负载模型, 利用邻居节点度或节点能量进行负载重分配, 通过对级联失效的演化分析得出了网络的临界负载以及能量对级联失效产生影响的结论.王等人[构建了初始负载关于节点度与邻居节点度总和乘积的幂函数, 并利用节点度和邻居节点度总和进行择优分配, 分析幂指数与容忍参数的影响关系.Liu等人[利用节点介数构建网络的初始负载模型, 通过容量与负载的差值进行择优分配, 分析得出容量的容忍参数对级联失效的影响.Peng[和Dou等人[构建初始负载关于介数的幂函数, 并分析幂指数的取值范围与抗击级联失效的关系.此外, 一些文献

然而, 在现实世界中, 加权网络是普遍存在的, 典型的例子有大型的信息网络(如Internet、电话网)、交通网络(如铁路网、航空网)、生物网络(如生物神经网、蛋白质网)、社会网络(如科学家合作网、社交网)以及电网.无权网络只是反映顶点之间是否存在相互作用, 在很多情况下, 顶点之间相互作用的强度差异起着至关重要的作用, 如神经元突触之间的连接在学习和认知过程中是不变的, 只是突触之间连接强度的变化使大脑皮层产生了新的功能.再如, Internet上的带宽、航空网中两个机场间航班数量或者座位数、专家合作网中的合作次数等都是影响系统性质的重要因素.同样, 相同网络结构中的同一节点的角色和重要性也有很大差异.如电网中的开关处于大型高压配电中心或大型信息交换中心与处于普通配电站的作用有巨大的差别.因此, 无权网络完全可以作为加权网络的一种特例, 基于加权网络的级联失效研究具有更强烈的实际需求.目前, 关于加权网的研究成果远不及无权网的研究.加权网最经典的是Barrat等人[提出的BBV(Barrat Barthélemy Vespignani)模型, 在此模型基础上, Zhao[和Ding等人[采用关于介数的初始负载模型, 在网络的节点的失效演化过程中涉及到边权的变化, 介数从全局的结构角度体现出节点承担的负载, 但是, 不同通信路径的选择会使得计算结果与实际结果有偏差.Wang[和Andrea等人[将权重转化为节点度乘积的幂函数进行负载重分配, 从局域的角度分析网络不发生级联失效的幂指数范围, 虽然降低了算法复杂度, 但是网络的全局结构特征对网络的变化起到至关重要的作用, 忽略全局因素会使得部分特殊位置节点的负载计算不够准确.Jin等人[基于有向加权网建立初始负载关于节点度和权重乘积的函数关系, 并分析了有向边的情况下容量参数的临界阈值, 其初始负载考虑了局域范围内的节点度和权值, 只是同样未涉及到全局的影响因素.综上所述, 加权网络中的节点权重对网络的构建具有重要的影响, 如何将节点权重与网络的全局和局域因素相结合, 并利用数学方法推导出参数之间的变化规律, 具有重要的研究意义.

针对以上问题, 本文基于加权的无标度网络, 研究初始负载、容量和负载重分配中的参数的相互影响关系及其对级联失效的影响, 提出一个同时考虑全局和局域因素的初始负载模型, 构建关于容量的负载重分配机制, 并分析容量中的容忍参数分别与网络抵抗级联失效的鲁棒性和初始负载中的强度参数的关系.

1 加权无标度模型和问题描述

1.1 BBV模型

级联失效的分析是基于节点负载和容量展开的, 在加权无标度网络中, 以点权为驱动机制的经典模型为BBV模型, 因此, 对于加权无标度网络中的级联失效研究大多基于BBV模型及其衍生模型.BBV模型的点权、度和边权分布都服从幂率分布, 保持了无标度网络的强容错性能.

在BBV模型中, 节点i的点权wi的表达式为

{{w}_{i}}=\sum\limits_{j\in N}{{{t}_{ij}}}

(1)

其中, tij为节点i和j之间的边权, 且tij=tji, 当i和j之间无连接时, 则tij=0, N为网络中的节点个数.

BBV模型的构建主要包含两个步骤:增长方式和权重演化.

(1) 增长:初始网络是包含m0个节点的全连通网络, 每个时间间隔加入一个新节点nnew, 新节点与网络中已经存在的m(≤m0)个节点相连, 网络中节点i被选中与nnew相连的概率与i的点权成正比, 择优连接概率为

\prod\limits_{{{n}_{new}}\to i}{=\frac{{{w}_{i}}}{\sum\nolimits_{j}{{{w}_{j}}}}}

(2)

(2) 权重演化:新加入的边ennewi的权重的初始值设为t0=1, ennewi的加入会导致节点i与其邻居节点j之间的边权重新分配, 调整规则如下:

{{t}_{ij}}\to {{t}_{ij}}+\Delta {{t}_{ij}}

(3)

其中, Δtij与tij和节点i的权重wi相关为

\Delta {{t}_{ij}}={{\delta }_{i}}\frac{{{t}_{ij}}}{{{w}_{i}}}

(4)

其中, δi为节点i新增一条边所带来的额外流量负担(一般情况下, 设δi=δ=1).进而可得i的点权调整为

{{w}_{i}}\to {{w}_{i}}+{{t}_{0}}+{{\delta }_{i}}

(5)

当权重更新之后, 进入下一个时间轮, 直到网络构建结束.BBV模型权重演化规则如

图 1

Fig. 1

Fig. 1 The evolution rule in weights of EH-BBV

图 1 BBV权重演化规则图

依据平均场理论得到最终的点权分布$ P(w)\sim {{w}^{-\alpha }}, $其中, $ \alpha =\frac{4\delta +3}{2\delta +1}$, 与度分布的幂率指数相同.实验中所用加权网络是BBV模型在局域范围内的衍生模型, 生成原理与演化规则是一致的.

1.2 问题描述

级联失效出现在现实世界中, 大多是由于单个节点受环境影响或人为因素导致失效, 出现负载分流现象, 这些分配出去的负载导致被分配的节点由于超载而失效, 出现再次负载重分配的现象, 这种现象持续发生会导致网络瘫痪.级联失效后的负载重分配示意图如i失效后, i的负载进行重分配, 以相应的分配比例分配给节点i的邻居节点j1、j2和j3, j1节点由于超载会进行再次分配, 如此循环下去, 直到网络中不再出现节点超载的现象.

图 2

Fig. 2