基于复杂网络理论的有向多关系网络级联失效研究.pdf

第3 6卷 第3期2023 年08月 青 岛 大 学 学 报(自 然 科 学 版)J O U R N A L O F Q I N G D A O U N I V E R S I T Y(N a t u r a l S c i e n c e E d i t i o n)V o l.3 6 N o.3A u g.2023 文章编号:1 0 0 6 1 0 3 7(2 0 2 3)0 3 0 0 4 1 0 9d o i:1 0.3 9 6 9/j.i s s n.1 0 0 6 1 0 3 7.2 0 2 3.0 3.0 8基于复杂网络理论的有向多关系网络级联失效研究周 博,宾 晟,孙更新(青岛大学计算机科学技术学院,青岛 2 6 6 0 7 1)摘要:针对复杂网络中关键节点识别仅限于单个关系网络的问题,根据复杂网络理论构建有向多关系网络级联失效模型,研究多关系网络中节点重要性的识别与网络鲁棒性问题;依据所建模型提出多关系网络节点及连边指标与节点重要性识别公式。通过对网络模型采取不同攻击方式,验证所提指标与关键节点识别的有效性。研究结果表明,所提指标可以很好的反映网络模型的结构与特点,优先攻击高重要性的节点后网络失效节点比例快速增加,网络连通性大大降低,破碎程度迅速增大,对网络鲁棒性的影响大于随机攻击与高度数攻击;证明了所提关键节点识别方法的有效性,优先保护本文所提重要节点可以大大降低网络构建成本,提高网络抗风险能力。关键词:级联失效;多关系网络;关键节点识别;鲁棒性中图分类号:T P 3 9 1 文献标志码:A收稿日期:2 0 2 2-1 1-0 9基金项目:教育部人文社会科学研究青年项目(批准号:1 5 Y J C 8 6 0 0 0 1)资助;山东省自然科学基金面上项目(批准号:Z R 2 0 1 7MG 0 1 1)资助;山东省社会科学规划项目(批准号:1 7 C HL J 1 6)资助。通信作者:孙更新,男,博士,副教授,主要研究方向为复杂网络。E-m a i l:s u n g e n g x i n q d u.e d u.c n 随着社会的不断发展以及科学技术的进步,复杂系统在现实中的应用越来越广泛1。研究发现真实世界网络并不是随机网络,而是具有特殊拓扑结构特征的复杂网络。复杂网络本身存在一定的脆弱性,网络中包含少部分重要节点,失效后的负面影响可以快速波及到整个网络,使网络陷入瘫痪2,如2 0 0 8年中国南方电网因雪灾造成大规模崩溃3,2 0 1 2年印度大停电事故4等均是由于电网具有的无标度特性导致级联故障快速蔓延致使整个网络迅速崩溃。因此识别网络中重要节点对提高网络鲁棒性,抵制级联失效现象有着重要意义。目前针对复杂网络级联失效的研究主要分为两类:单个网络的级联失效以及耦合网络级联失效5-7。文献8 最先研究了不同拓扑结构的网络应对节点移除攻击的鲁棒性,为复杂网络级联失效研究奠定理论基础;文献9 根据理论基础将节点聚集系数与度中心性算法相结合识别网络中的关键节点,有效识别出单个网络中的关键节点;节点的“介数”可以衡量节点的重要性,分析网络中级联故障的发展进程,可知网络在对高介数节点的蓄意攻击下十分脆弱,然而单纯使用节点介数来判断节点的重要性,而忽视节点所在区域的局部特性,并不能很好的体现节点的重要程度1 0;采用基于节点收缩的方法可将网络凝聚度作为节点重要度评价的指标,但是该方法的收缩范围并不好确定,适用性较差1 1;利用基于节点删除的方法,删除节点后网络的连通度可以评价节点重要性,但该方法对节点删除后无法连通的网络不能有效评价,存在一定的局限性1 2。考虑节点位置信息提出的K-s h e l l分解算法对节点进行分层,算法中节点所在的层级越高越重要,但存在无法比较同层节点重要性的缺陷1 3。对于耦合网络级联失效的研究,根据复合网的度中心性而提出的MC C N-D e g r e e算法识别地铁公交耦合网络的关键节点,有效的保护了城市公共交通网络中的重要站点1 4;文献1 5 以实际电力通信双层网络为例,以复杂网络理论为基础建模,分析网络特性,发现网络的拓扑结构对电力通信网的脆弱性有重要影响,网络中的高度数节点和高介数线路是网络中的脆弱环节;考虑拓扑结构并结合电网特性提出的电气介数指标识别电力信息双层网络关键节点算法,能更加真实的识青 岛 大 学 学 报(自 然 科 学 版)第3 6卷别出电网中的关键节点1 6;结合电力通信双层网络的线路已用率来辨识网络中信息网的薄弱环节,发现对于现有的网络结构,可以通过优化路由策略和增加网络冗余性来降低网络的脆弱性,以提高可靠性1 7;文献1 8 在评估节点重要性时综合了网络拓扑结构、节点的异质性、以及节点的流量,共同判别多层网中的重要节点,使辨识结果更加科学合理;从级联故障的起因和传播过程出发,从分布的聚集性和分布均匀角度,采用广义熵理论辨别关键节点,识别出的关键节点更加符合真实网络情况1 9。综上,目前对于复杂网络级联失效研究主要集中在单一关系的单个网络与耦合网络中,通过度中心性、介数并结合网络特性可以很好的识别单关系网络中的关键节点。然而现实世界中,真实的网络系统节点之间并不是单一关系,而是存在着不同方向上的两种或更多关系,传统识别算法并没有考虑到网络中存在的多种关系,在研究真实网络系统级联失效时并不能很好的反映网络特性,所得结果与真实情况并不匹配。因此,本文根据复杂网络理论1 7,建立具有方向性的有向多关系网络模型,提出复合网络特性的节点及连边计算指标,依据所提指标提出更符合真实网络的多关系网络关键节点判别公式,通过仿真实验验证其有效性。1 有向多关系网络模型根据多子网复合复杂网络理论2 0,初始创建向量复合网A=(GA,SA,MA),其中GA=(VA,EA,RA,FA)为有向多关系网络A,VA=v1,v2,vn 表示多关系网络中节点的集合,EA=|vm,vn图1 有向多关系网络AVA 表示网络中连边的集合,RA=r1,r2,rn 表示多关系网中节点之间相互作用关系的集合,FA表示连边和关系的映射,FA:EA RA,SA表示多关系网A的关系强度向量空间,MA表示连边和关系强度向量空间的映射,其中 MA:EA SA。如图1所示,设RA=r1,r2,r3,r4,r5 表示有向多关系网络中个体间可能存在的5种关系,网络中个体的不同方向均间可能会存在一种或多种关系。关系强度向量空间S=s=s(r1),s(r2),s(r3),s(r4),s(r5),其 中s(ri)i1,2,3,4,5 表示第i种关系的关系强度值。2 有向多关系网络级联失效模型对于有向多关系网络,级联现象建模需要考虑不同节点间的不同方向存在的多种关系,将节点间的关系均看作其间连边,因此定义下列指标用来计算网络级联现象。2.1 节点平衡度网络中,每种关系的关系强度指此种关系的连边数量占总连边数量的比值。网络中每个节点都具有接收负载和释放负载的能力,有向多关系网络中,每种关系下节点包含入度值ki nim(与节点m相连的上游邻居节点边数量的和)与出度值ko u tim(与节点m相连的下游邻居节点连边数量的和),节点平衡度用来评价节点m在接收到其它节点传输的负荷时保持自身收放稳定的能力,在关系ri中平衡度B Lm的大小与节点的出入度与关系强度为B Lm=riRsiki nimko u tim(1)其中,si表示关系i的关系强度值。入度值大于出度值时,该节点吸收外来负荷的可能性较大;出度值大于入度值时,则节点向外发出负荷的可能性较大;若节点的出度与入度相等,则节点的负载处于一种相对稳定的状态。24 第3期 周 博等:基于复杂网络理论的有向多关系网络级联失效研究2.2 节点间连通能力网络中的节点之间通过边相连,节点间连通能力值越小,说明两节点间负载流通的可能性越大,互为彼此的关键邻居节点。在有向多关系网络中,节点m与节点n之间边连通能力的计算有三种情况:(1)Vm到Vn存在连边,Vn到Vm不存在连边,则节点间连通能力为C Am n1=riR1ko u trim-1ki nrin;(2)Vn到Vm存在连边,Vm到Vn不存在连边,则节点间连通能力为C Am n2=riR1ko u trin-1ki nrim;(3)Vn与Vm之间彼此存在连边,则节点间连通能力为C Am n=C Am n1+C Am n2=riR1ko u trin-1ki nrim+r iR1ko u trim-1ki nrin(2)其中,C A为两节点间的连通能力值,ki nr i和ko u tr i分别为节点在关系ri下的入度和出度。上游节点m所有出度连边中指向下游节点n的比例和下游节点n所有入度连边中指向上游节点m的比例,两者之差的绝对值衡量了两个节点的比例差异程度。2.3 初始负载与负载重分配依据负载容量级联失效模型,在复杂网络中节点的负载通常与所经过节点的流量有关,由于节点的平衡度可以衡量经过节点释放或吸收负载的能力,而节点的度在一定程度上反映可能流经该节点的负载多少。因此节点的平衡度及其大小通常在很大程度上影响通过节点的流量。在多关系网络中,由于节点之间存在着多种关系,每种关系的关系强度和在此种关系下节点的度都有所不同,因此每种关系均对负载的传输造成不同的影响。因此,有向多关系网络中节点的初始负载为Lv m(0)=(riR(v qriv m(v priv m(krimkriq krimkrip B Lm)(3)其中,Lv m(0)表示节点m的初始负载,其中R表示与节点m相关联的关系集合,riv m表示节点m关于关系ri的上游邻居节点集合,riv m表示节点m关于关系ri的下游邻居节点集合,krim,kriq,krip 分别为节点m,节点q和节点p在关系ri中的度,a为负载可变参数,取a1。在负载容量级联失效模型中,多关系网络中节点最大容量仍与初始负载呈线性相关且受到节点间多种关系的影响,因此将节点m的最大容量定义为Cv m=(1+b)Lv m(0)(4)其中,b为耐受参数,衡量节点负载容量,体现节点抵御级联失效的能力。节点受到攻击而失效后,自身负载会按照一定比例分配给邻居节点,为保证级联故障过程不会过于严重,负载的转移通常会按照一定的重分配策略进行,在经典复杂网络或单关系网络中普遍采用局部择优重分配或剩余负载重分配的策略,然而在多关系网络中,原有的分配策略没有很好的考虑网络特性与邻居节点的实际情况,导致重分配后级联故障加剧。在本文有向多关系网络模型中,负载的传输与节点的平衡度,节点之间连通度以及关系强度均有关系,节点m的邻居节点平衡度越大,说明该节点有吸收分配而来的负载的倾向,节点m与其邻居节点之间的连通性越强,两节点间负载转移的可能性也更大,因此,节点失效时其向邻居节点负载转移的重分配公式为drim n=B LrinC Arim n-Lv n(0)riR(v kriv m(B LrikC Arim k-Lv k(0)(5)其中,drim n表示节点m失效后向其邻居节点n关于关系ri的负载的转移量,B Lrin表示节点n在关系ri中的平衡度,C Arim n表示节点m与邻居节点n之间关于关系ri的连通程度,Lv n(0)为节点n的初始负载,riv m表示节点m的邻居节点集合。34青 岛 大 学 学 报(自 然 科 学 版)第3 6卷当节点n收到失效节点m通过各个关系分配的负载后,若自身负载大于其最大容量,则该节点继续失效,失效节点不会再接收任何外来负载,负载从该节点继续按照分配策略向其邻居节点转移,级联故障在网内散播开来,直到分配到某一个节点时其自身负载小于最大容量或该节点没有下游邻居节点为止,级联故障结束。2.4 鲁棒性评价在级联失效模型中,鲁棒性通常被用来衡量网络在遭受攻击情况下的抗毁能力。本文使用失效规模,最大连通子图规模,分别从网络的破碎性与结构连通性两个方面评价网络的鲁棒性。从网络整体破碎性的角度分析,用网络的失效规模衡量网络整体鲁棒性。首先按照攻击方式删除网络中的某个节点m,计算失效规模(级联故障停止时失效节点的总数),根据每组级联故障被攻击失效节点数量依次对网络中的节点按照攻击方式移除,再取所有网络中失效节点规模Sm的平均数S=1MmNSmM(6)其中,S表示k个节点失效后级联故障导致的网络失效规模,M是网络中的节点总数;当S0时,节点数量在级联故障前后损失不大,网络具有较强的鲁棒性;当S1时,网络几乎被完全撕裂成碎片,级联故障在网络中的传播已难以控制。采用最大连通子图规模从网络结构连通性角度计算网络鲁棒性g=n n(7)其中,n和n分别代表故障前和故障后的最大连通子图中的节点总数。当网络中的节点被移除时,整个网络可能分解成若干个子网。g下降得越慢,说明网络整体结构连通性越高,对节点失效移除的鲁棒性越强。3 关键节点识别由于现实中网络结构纷繁复杂,一旦网络受到蓄意攻击,造成的损失难以估计,因此准确地辨别网络中的脆弱节点,对构建网络拓扑和网络关键部位的保护具有重要意义。越重要的节点失效时对网络造成的损害越大,级联失效后果越严重。目前针对复杂网络的节点重要性辨别大都集中在使用节点度,节点介数等方法。然而多关系网络中节点之间存在着多种关系,关系强度以及网络不同的拓扑结构都会对节点的重要性产生不同的影响,单纯的使用度或介数并不能真实的反映出理想的结果。在多关系网络中,由于节点与连边间通过多种关系相互依存相互影响,节点的重要性与边的重要性紧密相关,节点的度越大,与该节点相连的连边越多,则其在网络中所处位置越重要,节点重要性越高,节点与邻居节点之间连边条数所占其出度边数比例越多,则可能经过该节点流向下游的负载越多,该节点重要性越高。在多关系网络中节点连边的关系强度越高,该节点的重要性也必然越高。关键节点的识别公式为MB Dm=riR(krimkrimkrikko u trim )+riRB Lrim(8)其中,MB Dm为节点m的重要性评价指标,krim为节点m在关系ri下的度,rim为m邻居节点的集合。4 仿真实验分析在实验中,构建多关系网络GA,网络中存在5种可能的关系r1,r2,r3,r4,r5。对于最大连通子图,采用随机攻击、高度数攻击和本文所提的高重要性攻击3种不同攻击方式对网络进行连锁攻击,评价网络鲁棒性并验证所提节点重要性指标的有效性。实验时,每次攻击都将失效节点从网络中移除并不再恢复,并于结束后马上重新计算最大连通子图中节点数目的变化,以表征该节点失效对系统影响的大小。仿真级联过程如图2所示。44 第3期 周 博等:基于复杂网络理论的有向多关系网络级联失效研究S t e p 1 建立具有5种不同关系的有向多关系网络A,每种关系对应的网络为随机网络、小世界网络、无标度网络或以上3种网络随机组合而成网络,根据式(1)和(2)计算网络中节点的初始负载等各项指标,设定负载参数a以及耐受参数b,并根据要攻击的节点个数,设定攻击次数k;S t e p 2 选择不同攻击策略对相应节点进行攻击,被攻击节点失效,将失效节点从网络中移除,并找出失效节点的邻居节点;S t e p 3 将失效节点的负载根据式(5)的重分配策略分配给其邻居节点,并重新计算网络中节点的负载,并将负载值与最大容量比较,超出最大容量的节点继续失效移除;S t e p 4 重复步骤S t e p 2和S t e p 3直到所有节点的负载小于其最大容量,则该节点的级联故障结束,计算当前网络鲁棒性的评价指标;S t e p 5 在根据攻击策略选择下一次失效的节点,重复步骤S t e p 3和S t e p 4,之后重复S t e p 5再次选择下一个攻击节点直到次数达到起始设定的攻击次数k。对于失效规模,采用随机攻击、高度数攻击和高重要性攻击3种不同攻击方式对网络进行连锁攻击,如图3所示。图2 最大连通子图级联故障流程图图3 网络失效规模级联故障流程图 S t e p 1 随机攻击时,随机选择一个节点使其受到攻击而失效,计算节点失效后造成的网络失效规模,失效节点被移除不再恢复;S t e p 2 再依次随机选择k个节点进行攻击移除,分别计算每个节点失效后所造成的的网络失效规模,之后对k个失效规模值计算平均数,作为第一组节点失效后的破碎程度评价数值;S t e p 3 恢复前k个失效节点,再随机选择k个节点重复以上过程直至网络中所有节点均遭到攻击而54青 岛 大 学 学 报(自 然 科 学 版)第3 6卷失效;S t e p 4 对于高度数攻击与高重要性攻击,先按照其度数或重要程度高低进行排序,根据排序顺序依次选择k个失效节点并计算失效规模。4.1 不同攻击方式对有向多关系随机网络鲁棒性的影响与单关系网络相比,多关系网络中每种关系对网络故障现象的影响不尽相同。为探索不同攻击方式对有向多关系网络鲁棒性的影响,并验证所提重要性指标对关键节点识别的有效性,建立节点总数为2 0 0,节点之间概率0.5随机相连的有向多关系随机网络,关系集合为R=r1,r2,r3,r4,r5。采用上文提出的3种攻击方式,设定负载参数a=1,耐受参数b=0.1,网络破碎性评估设定2 0个节点为一组,最大连通子图规模研究设定攻击次数k=1 5,记录每组或每次攻击后的鲁棒性表现,多次仿真结果如图4所示。图4 不同攻击方式对有向多关系随机网络鲁棒性影响(a)网络破碎程度变化;(b)最大连通子图规模变化 由图4可知,多关系随机网络在面对随机攻击时,网络具有较强的鲁棒性,而面对目标攻击则鲁棒性均较差。从图4(a)中看出,将重要性最高的2 0个节点移除后,失效规模接9 0%,网络濒临破碎,在图4(b)中,随机网络在面对高重要性攻击时,网络最大连通子图规模快速下降,受到的损害程度远大于高度数攻击。4.2 不同攻击方式对有向多关系小世界网络鲁棒性的影响现实世界中许多网络为小世界网络,因此建立节点总数为2 0 0,网络节点度平均为3,随机化重连概率为0.5的有向多关系小世界网络,关系集合R=r1,r2,r3,r4,r5。攻击方式与参数设定同上,记录每组或每次攻击后的鲁棒性表现,多次仿真结果如图5所示。小世界多关系网络在面对随机攻击时,也具有较强的鲁棒性,随机攻击对网络造成的伤害并不大,而面对目标攻击时则鲁棒性较差。从图5(a)中可以看出,节点在经历高重要性攻击和高度数攻击后,失效规模均超过5 0%,面对高重要性攻击时网络破损程度达到了7 0%,而对多关系小世界网络进行低度数或低重要性攻击时,网络几乎保持完整。在图5(b)中,可以看出在面对高重要性攻击时,网络在1 5次攻击后连通程度小于高度数攻击。4.3 不同攻击方式对有向多关系无标度网络鲁棒性的影响现实中大部分网络的少数节点拥有大量的连接,而大部分节点的连接却很少,因此建立节点总数为2 0 0,网络节点度平均为2的有向多关系无标度网络,关系集合R=r1,r2,r3,r4,r5。攻击方式与参数设定同上,记录每组或每次攻击后的鲁棒性表现,多次仿真结果的曲线如图6所示。64 第3期 周 博等:基于复杂网络理论的有向多关系网络级联失效研究图5 不同攻击方式对有向多关系小世界网络鲁棒性影响(a)网络破碎程度变化;(b)最大连通子图规模变化图6 不同攻击方式对有向多关系无标度网络鲁棒性影响(a)网络破碎程度变化;(b)最大连通子图规模变化 无标度多关系网络在面对随机攻击时鲁棒性非常强。通过图6(a),网络在被高度数攻击后破损程度达到8 0%,超过了高重要性攻击,由于无标度网络中,仅有极少数高度数节点占据关键位置,而大部分节点的度很低,所以当占据重要位置的高度数节点失效移除后,对整个网络的破坏是非常严重的,但在经过多组攻击后,由高重要性攻击造成网络的失效规模超过了高度数攻击。在图6(b)中,被高重要性攻击后,网络最大连通子图规模下降速度也大于高度数攻击。4.4 不同攻击方式对有向多关系混合网络鲁棒性的影响复杂网络的种类复杂多样,因此将每个关系对应的网络拓扑结构为随机,小世界,无标度网络3种随机组合。建立节点总数为2 0 0,网络节点度平均为2的有向多关系混合网络,关系集合R=r1,r2,r3,r4,r5。攻击方式与参数设定同上,记录每组或每次攻击后的鲁棒性表现,多次仿真结果的曲线如图7所示。在图7中,有向多关系混合网络在面对随机攻击时,表现出了较好的鲁棒性。而在面对目标攻击时,不论是网络失效规模还是最大连通子图规模,高重要性攻击对有向多关系网络的打击均要大于高度数攻击;由图7(a),在面对高重要性攻击时,网络破碎性达到5 0%,图7(b)中,在高重要性攻击策略下,7次攻击后最大连通子图规模即趋近于0,网络连通能力几乎完全损坏,而高度数攻击策略在1 3次攻击后最大连通子图规模才接近0。74青 岛 大 学 学 报(自 然 科 学 版)第3 6卷图7 不同攻击方式对有向多关系混合网络鲁棒性影响(a)网络破碎程度变化;(b)最大连通子图规模变化5 结论针对目前级联失效研究中关键节点识别仅限于单个关系的网络,根据复杂网络理论提出了更接近真实网络的有向多关系网络模型,依据网络模型特点定义了网络中节点与其间连边相关指标,并提出有向多关系网络中节点重要性的判别方法。对于不同类型的多关系网络,所提节点重要性判别方法相比于传统办法效果均更为显著,重要性更高的节点失效后对多关系网络鲁棒性影响更大。为减小级联故障对网络的损坏,应重点保护所提重要性更高的节点,提高网络的鲁棒性。后续研究会考虑将所提模型运用到实际网络中,验证其识别关键节点的有效性,以实现对现实网络更好的保护。参考文献1 房翠娟,邵峰晶,隋毅,等.基于复杂网络的气象网络分析J.青岛大学学报(自然科学版),2 0 1 7,3 0(4):4 7-5 4.2 邵峰晶,孙仁诚,李淑静,等.多子网复合复杂网络及其运算研究J.复杂系统与复杂性科学,2 0 1 2,9(4):2 0-2 5.3 孙雅萍.对中国南方特大雪灾的成因分析及思考J.国土与自然资源研究,2 0 0 9(2):7 2-7 3.4 丁理杰,曹一家,刘美君.复杂电力网络的连锁故障动态模型与分析J.浙江大学学报(工学版),2 0 0 8(4):6 4 1-6 4 6.5 方锦清.从单一网络向 网络的网络 的转变进程略论多层次超网络模型的探索与挑战J.复杂系统与复杂性科学,2 0 1 6,1 3(1):4 0-4 7.6A L B E R T R,J E ON G H,B A RA B A S I A L.D i a m e t e r o f t h e w o r l d-w i d e w e bJ.N a t u r e,1 9 9 9,4 0 1(6):1 3 0-1 3 1.7B U L D Y R E V S V,P A R S HAN I R,P AU L G,e t a l.C a t a s t r o p h i c c a s c a d e o f f a i l u r e s i n i n t e r d e p e n d e n t n e t w o r k sJ.N a t u r e,2 0 1 0,4 6 4(7 2 9 1):1 0 2 5-1 0 2 8.8A L B E R T R,J E ON G H,B A RA B A S I A L.E r r o r a n d a t t a c k t o l e r a n c e o f c o m p l e x n e t w o r k sJ.N a t u r e,2 0 0 0,4 0 6(6 7 9 4):3 7 8-3 8 2.9 项小东,翟蔚,黄言态,等.基于X c e p t i o n-C EM s神经网络的植物病害识别J.中国农机化学报,2 0 2 1,4 2(8):1 7 7-1 8 6.1 0 C RU C I T T I P,L AT O R A V,MA R C H I O R I M.A t o p o l o g i c a l a n a l y s i s o f t h e I t a l i a n e l e c t r i c p o w e r g r i dJ.P h y s i c a A,2 0 0 4,3 3 8(1):9 2-9 7.1 1 王班,马润年,王刚.加权网络节点重要性评估的改进节点收缩法J.计算机应用研究,2 0 1 6,3 3(7):2 1 2 2-2 1 2 4.1 2 周遵仁,黄遵国.基于删除法的节点重要性分析及O P N E T仿真J.电脑知识与技术,2 0 1 3(4):7 5 9-7 6 3.1 3 R E DMON J,D I VVA L A S,G I R S H I C K R,e t a l.Y o u o n l y l o o k o n c e:U n i f i e d,r e a l-t i m e o b j e c t d e t e c t i o nC/2 0 1 6 I E E E C o n f e r e n c e o n C o m p u t e r V i s i o n a n d P a t t e r n R e c o g n i t i o n.S e a t t l e,2 0 1 6:7 7 9-7 8 8.1 4 王欣.基于多子网复合复杂网络的关键节点识别算法J.信息与电脑(理论版),2 0 2 2,3 4(4):8 8-9 0+9 7.1 5 郭静,王东蕊.基于复杂网络理论的电力通信网脆弱性分析J.电力系统通信,2 0 0 9,3 0(9):6-1 0.1 6 王文波.基于复杂网络的电网级联失效建模与鲁棒性研究D.南京:南京邮电大学,2 0 2 0.1 7 尹军,李炅菊,黄宏光.基于链路已用率的电力通信网脆弱性分析.电力系统保护与控制J.2 0 1 8,4 6(2):3 1-3 6.1 8 崔力民,耿子惠,舒勤等.考虑电网关联度的电力通信网关键环节识别.电力建设J.2 0 1 7,3 8(5):1 2 4-1 3 2.1 9 李勇,刘俊勇,刘晓宇.基于潮流熵的电网连锁故障传播元件的脆弱性评估J.电力系统自动化,2 0 1 2,3 6(1 9):1 1-1 6.2 0 隋毅.多子网复合复杂网络模型及其相关性质的研究D.青岛:青岛大学,2 0 1 2.84 第3期 周 博等:基于复杂网络理论的有向多关系网络级联失效研究C a s c a d i n g F a i l u r e s o f M u l t i-r e l a t i o n a l N e t w o r k s B a s e d o n C o m p l e x N e t w o r k T h e o r yZ HOU B o,B I N S h e n,S UN G e n g-x i n(S c h o o l o f C o l l e g e o f C o m p u t e r S c i e n c e a n d T e c h n o l o g y,Q i n g d a o U n i v e r s i t y,Q i n g d a o 2 6 6 0 7 1,C h i n a)A b s t r a c t:I n o r d e r t o s o l v e t h e p r o b l e m t h a t t h e i d e n t i f i c a t i o n o f k e y n o d e s i n c o m p l e x n e t w o r k s i s l i m i t e d t o a s i n g l e r e l a t i o n a l n e t w o r k,a c c o r d i n g t o c o m p l e x n e t w o r k t h e o r y,t h e c a s c a d i n g f a i l u r e m o d e l o f d i r e c t-e d m u l t i-r e l a t i o n s h i p n e t w o r k w a s c o n s t r u c t e d,t h e r e c o g n i t i o n o f n o d e i m p o r t a n c e i n m u l t i-r e l a t i o n s h i p n e t w o r k s i s s t u d i e d,t h e r e c o g n i t i o n o f n o d e i m p o r t a n c e a n d n e t w o r k r o b u s t n e s s i n m u l t i-r e l a t i o n s h i p n e t-w o r k s a r e s t u d i e d.A c c o r d i n g t o t h e b u i l t m o d e l,t h e r e c o g n i t i o n f o r m u l a o f n o d e a n d e d g e i n d e x a n d n o d e i m p o r t a n c e i n m u l t i-r e l a t i o n s h i p n e t w o r k i s p r o p o s e d.B y t a k i n g d i f f e r e n t a t t a c k m o d e s o n t h e n e t w o r k m o d e l,v e r i f y t h e e f f e c t i v e n e s s o f t h e p r o p o s e d i n d i c a t o r s a n d k e y n o d e i d e n t i f i c a t i o n.T h e r e s e a r c h r e s u l t s s h o w t h a t t h e p r o p o s e d i n d i c a t o r s c a n w e l l r e f l e c t t h e s t r u c t u r e a n d c h a r a c t e r i s t i c s,a f t e r g i v i n g p r i o r i t y t o a t t a c k i n g n o d e s o f h i g h i m p o r t a n c e,t h e p r o p o r t i o n o f f a i l e d n o d e s i n t h e n e t w o r k i n c r e a s e s r a p i d l y,t h e n e t w o r k c o n n e c t i v i t y i s g r e a t l y r e d u c e d,t h e d e g r e e o f f r a g m e n t a t i o n i n c r e a s e s r a p i d l y,t h e g r e a t e s t i m p a c t o n n e t w o r k r o b u s t n e s s.T h e e f f e c t i v e n e s s o f t h e p r o p o s e d k e y n o d e i d e n t i f i c a t i o n m e t h o d i s p r o v e d,a n d p r i o r i t y p r o t e c t i o n o f i m p o r t a n t n o d e s c a n g r e a t l y r e d u c e t h e n e t w o r k c o n s t r u c t i o n c o s t,i m p r o v e n e t w o r k a n t i-r i s k c a p a b i l i t y.K e y w o r d s:c o s c a d i n g f a i l u r e;m u l t i-r e l a t i o n s h i p n e t w o r k;k e y n o d e i d e n t i f i c a t i o n;r o b u s t n e s s(上接第4 0页)A l g o r i t h m f o r R a n k i n g t h e I m p o r t a n c e o f N o d e s i n C o m p l e x N e t w o r k s B a s e d o n t h e H-i n d e x o f L o c a l N e a r e s t N e i g h b o r sD ONG X i a n g-n i n g,B I N S h e n g,S UN G e n g-x i n(S c h o o l o f C o m p u t e r S c i e n c e a n d T e c h n o l o g y,Q i n g d a o U n i v e r s i t y,Q i n g d a o 2 6 6 0 7 1,C h i n a)A b s t r a c t:A n o d e i m p o r t a n c e r a n k i n g a l g o r i t h m w i t h H-i n d e x o f l o c a l n e a r e s t n e i g h b o r n o d e w a s p r o p o s e d i n o r d e r t o d e t e c t t h e i m p o r t a n c e o f n o d e s i n r a n k i n g c o m p l e x n e t w o r k m o r e e f f i c i e n t l y,a n d t h e s e c o n d a r y i n f l u e n c e w e i g h t c o e f f i c i e n t o f t h e n e a r e s t n e i g h b o r n o d e s w a s i n t r o d u c e d t o m e a s u r e t h e w e i g h t o f i n f l u-e n c e e x e r t e d b y n e i g h b o r n o d e s o n t h e n o d e s t h e m s e l v e s.I n t h e r e a l c o m p l e x n e t w o r k,t h e S u s c e p t i b l e-I n-f e c t e d-R e c o v e r e d(S I R)p r o p a g a t i o n m o d e l w a s u s e d t o s i m u l a t e t h e i n f o r m a t i o n p r o p a g a t i o n p r o c e s s,a n d K e n d a l l c o r r e l a t i o n c o e f f i c i e n t,c o m p l e m e n t a r y c u m u l a t i v e d i s t r i