加权无标度网络的级联失效模型-韩丽 , 刘彬 , 邓玉静 , 王倩悦 , 尹荣荣 , 刘浩然.pdf

上善若水

336

13页

0次

2022-05-20

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2017,28(10):27692781 [doi: 10.13328/j.cnki.jos.005173] http://www.jos.org.cn

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





韩

丽

1,2,3

刘

彬

1,2

邓玉静

1,2

王倩悦

尹荣荣

1,2

刘浩然

1,2

(燕山大学信息科学与工程学院,河北秦皇岛 066004)

(河北省特种光纤与光纤传感重点实验室(燕山大学),河北秦皇岛 066004)

(河北科技师范学院网络技术中心,河北秦皇岛 066004)

通讯作者: 刘彬, E-mail: liubin@ysu.edu.cn

摘要: 在加权的无标度网络中,为了抵抗网络的级联失效,增强网络的鲁棒性,提出了一种参数可调的级联失效

模型.该模型从全局和局域的角度,将节点介数、节点度、节点权重和邻居节点权重相结合构建节点的初始负载,并

建立节点容量与初始负载的比例关系,当节点失效后,通过结合失效节点邻居的容量来制定负载重分配规则,进而通

过对网络级联失效的分析,推导负载参数的演化过程,得出模型中的参数对网络鲁棒性的影响.最后,通过实验验证

了所提方法的有效性.

关键词: 无标度网络;级联失效;负载;加权;容量

中图法分类号: TP393

中文引用格式: 韩丽, 刘彬,邓玉静,王倩悦,尹荣荣,刘浩然.加权无标度网络的级联失效模型.软件学报,2017,28(10):

27692781. http://www.jos.org.cn/1000-9825/5173.htm

英文引用格式: Han L, Liu B, Deng YJ, Wang QY, Yin RR, Liu HR. Cascading failure model of weighted scale-free networks.

Ruan Jian Xue Bao/Journal of Software, 2017,28(10):27692781 (in Chinese). http://www. jos.org.cn/1000-9825/5173.htm

Cascading Failure Model of Weighted Scale-Free Networks

HAN Li

1,2,3

, LIU Bin

1,2

, DENG Yu-Jing

1,2

, WANG Qian-Yue

, YIN Rong-Rong

1,2

, LIU Hao-Ran

1,2

(School of Information Science and Engineering, Yanshan University, Qinhuangdao 066004, China)

(The Key Laboratory for Special Fiber and Fiber Sensor of Hebei Province (Yanshan University), Qinhuangdao 066004, China)

(Network Technology Center, Hebei Normal University of Science & Technology, Qinhuangdao 066004, China)

Abstract: The robustness of complex network against cascading failures is of great significance. Based on the weighted scale-free

network, a new cascading failure model with adjustable parameters is proposed. In this model, the nodes’ initial loads are constructed with

node betweenness, node degree, node weight and neighbor node’s weight from both global and local perspective. Meanwhile, the initial

load is made proportional to the node capacity. Adopting a new redistribution rule, the failed nodes’ loads are assigned to their neighbors.

Then the load parameters can be obtained through analyzing the cascade failure process. Finally, the effectiveness of the proposed method

are verified by experiment.

Key words: scale-free network; cascading failure; load; weight; capacity

社交网、交通网、通信网等领域均呈现无标度特性

[13]

,是复杂网络中常见的一种现象,不同网络中的节点

和边都承载着不同形式的负载,且负载的承受能力是有限的.加权无标度网络是指节点和边根据权值构建成的

 基金项目: 河北省自然科学基金(F2014203239, F2015203091); 河北省科技计划(15275423); 燕山大学青年教师自主研究计划

(14LGB017)

Foundation item: Natural Science Foundation of Hebei Province (F2014203239, F2015203091); Science and Technology Project of

Hebei Province (15275423); Young Teachers Research Project of Yanshan University (14LGB017)

收稿时间: 2015-08-25; 修改时间: 2016-03-22, 2016-06-12; 采用时间: 2016-10-27

2770

Journal of Software 软件学报 Vol.28, No.10, October 2017

网络

[4,5]

,应用在专家网等领域.

在复杂网络中,节点和边承担的负载是不断演化的,具有一定的动力学特征,当节点或边的负载大于自身容

量而导致失效后,使得失效节点或边的负载通过网络的相互连接被重新分配到相关节点或边上,从而引起其他

节点或边失效,产生级联效应,进而可能导致整个网络的瘫痪

[6,7]

,这种由微小事件引发的连锁故障称为级联失

效.在现实世界中,由级联失效引发的故障包括北美电力网崩溃事故、Internet 阻塞、交通堵塞以及经济危机等.

因此,构建合理、完善的级联失效模型,并分析参数对级联失效的影响,对提升网络的鲁棒性具有重要的意义

[8,9]

近年来,级联失效的研究主要基于复杂网络,其中以无标度网络为主,主要是从节点的初始负载、节点容量

与初始负载的关系、节点失效后负载重分配规则这 3 个方面进行研究.复杂网络的主要特性包括节点度、集聚

系数和平均最短路径长度,其中,节点度(包括邻居节点度)对节点负载起到决定性作用,其属于局域范畴;平均最

短路径长度通过介数的表达方式体现出对节点负载的影响,其属于全局范畴;集聚系数表示网络中节点聚集程

度的系数,与节点负载没有密切关系.在加权的复杂网络中,还需要考虑节点权重对负载的影响.因此,节点的初

始负载通常定义为关于度、介数或者邻居度的幂函数,幂指数是用来控制初始负载强度的参数;负载重分配主

要考虑邻居的容量、负载、度数和与失效节点的距离等因素;节点的容量必然要大于节点的初始负载,一般定

义为关于初始负载的比例函数.在这些方面,段等人

[10]

基于初始负载与度的幂函数关系,构建关于距离和节点度

的择优分配规则,分析了负载重分配的范围和均匀性.Yin

[11]

和 Liu

[12]

等人同样采用关于度的初始负载模型,利用

邻居节点度或节点能量进行负载重分配,通过对级联失效的演化分析得出了网络的临界负载以及能量对级联

失效产生影响的结论.王等人

[13]

构建了初始负载关于节点度与邻居节点度总和乘积的幂函数,并利用节点度和

邻居节点度总和进行择优分配,分析幂指数与容忍参数的影响关系.Liu 等人

[14]

利用节点介数构建网络的初始

负载模型,通过容量与负载的差值进行择优分配,分析得出容量的容忍参数对级联失效的影响.Peng

[15]

和 Dou 等

人

[16]

构建初始负载关于介数的幂函数,并分析幂指数的取值范围与抗击级联失效的关系.此外,一些文献

[119]

从有向、攻击和最小化级联失效节点数等方面进行了研究.综上所述,对于初始负载,只考虑局域因素的节点度

数(邻居度数)不能兼顾度数小的重要节点,如桥节点,桥节点是网络中不同分组间通信的重要桥梁,其负载与其

特殊位置有重要关系,利用介数能够更合理地衡量它的负载;只考虑全局因素的介数只是从最短路径的角度分

析,而实际传输中,节点并不一定都按照最短路径进行传输,因此,节点度的分析是对介数分析的完善,单独考虑

某一方面都是片面的.同样地,对于负载重分配,只考虑邻居的负载或度数也不够完善.此外,上述所有文献都是

基于无权网络的级联失效研究,已有可观的成果.

然而,在现实世界中,加权网络是普遍存在的,典型的例子有大型的信息网络(如 Internet、电话网)、交通网

络(如铁路网、航空网)、生物网络(如生物神经网、蛋白质网)、社会网络(如科学家合作网、社交网)以及电网.

无权网络只是反映顶点之间是否存在相互作用,在很多情况下,顶点之间相互作用的强度差异起着至关重要的

作用,如神经元突触之间的连接在学习和认知过程中是不变的,只是突触之间连接强度的变化使大脑皮层产生

了新的功能.再如,Internet 上的带宽、航空网中两个机场间航班数量或者座位数、专家合作网中的合作次数等

都是影响系统性质的重要因素.同样,相同网络结构中的同一节点的角色和重要性也有很大差异.如电网中的开

关处于大型高压配电中心或大型信息交换中心与处于普通配电站的作用有巨大的差别.因此

,无权网络完全可

以作为加权网络的一种特例,基于加权网络的级联失效研究具有更强烈的实际需求.目前,关于加权网的研究成

果远不及无权网的研究.加权网最经典的是 Barrat 等人

[20]

提出的 BBV(Barrat Barthélemy Vespignani)模型,在此

模型基础上,Zhao

[21]

和 Ding 等人

[22]

采用关于介数的初始负载模型,在网络的节点的失效演化过程中涉及到边

权的变化,介数从全局的结构角度体现出节点承担的负载,但是,不同通信路径的选择会使得计算结果与实际结

果有偏差.Wang

[23]

和 Andrea 等人

[24]

将权重转化为节点度乘积的幂函数进行负载重分配,从局域的角度分析网

络不发生级联失效的幂指数范围,虽然降低了算法复杂度,但是网络的全局结构特征对网络的变化起到至关重

要的作用,忽略全局因素会使得部分特殊位置节点的负载计算不够准确.Jin 等人

[25]

基于有向加权网建立初始负

载关于节点度和权重乘积的函数关系,并分析了有向边的情况下容量参数的临界阈值,其初始负载考虑了局域

范围内的节点度和权值,只是同样未涉及到全局的影响因素.综上所述,加权网络中的节点权重对网络的构建具

of 13

免费下载

软件学报计算机技术

关注

评论