基于DomiRank中心性的层影响不均多层网络脆弱性分析方法

李海涛 ,  吉立新 ,  葛东东

信息工程大学学报 ›› 2025, Vol. 26 ›› Issue (03) : 305 -311.

PDF (2646KB)
信息工程大学学报 ›› 2025, Vol. 26 ›› Issue (03) : 305 -311. DOI: 10.3969/j.issn.1671-0673.2025.03.008
网络空间安全

基于DomiRank中心性的层影响不均多层网络脆弱性分析方法

作者信息 +

Vulnerability Analysis Method for Multi-layer Networks with Uneven Layer Impacts Based on DomiRank Centrality

Author information +
文章历史 +
PDF (2708K)

摘要

针对现有多层网络脆弱性分析算法未考虑层影响不均特性对全局脆弱性的影响以及算法性能不足的问题,提出一种基于DomiRank中心性的层影响不均多层网络脆弱性分析方法。首先,引入多层加权因子,构建表征层影响不均特性的多层网络模型;其次,基于加权超邻接矩阵设计一种改进的多层DomiRank中心性(MDRC)指标;最后,按照MDRC大小降序排列多层网络所有节点,开展节点攻击并依序删除网络节点,通过观察不同节点删除比例下多层网络性能变化实现对网络脆弱性的分析。实验结果表明,所提方法性能优于基准方法,多层加权因子能有效区分不同分层特性对脆弱性的影响。

Abstract

A vulnerability analysis method for multi-layer networks with uneven layer impacts is proposed based on DomiRank centrality, aiming to address the limitations of existing algorithms that neglect uneven layer impacts and exhibit inadequate performance. First, multi-layer weighted factors are introduced to construct a network model characterizing uneven layer impacts. Subsequently, an improved multi-layer DomiRank centrality (MDRC) metric is designed using a weighted supra-adjacency matrix. Finally, node attacks are implemented by sequentially removing all nodes sorted in descending order of MDRC values, through which network vulnerability is evaluated by performance degradation under different node removal ratios. Experimental results have demonstrated that the proposed method outperforms benchmark methods, with the multi-layer weighted factors being verified to effectively discriminate vulnerability variations caused by distinct layer characteristics.

Graphical abstract

关键词

多层网络 / 层影响不均 / 节点中心性 / 脆弱性分析

Key words

multi-layer networks / uneven layer impacts / node centrality / vulnerability analysis

引用本文

引用格式 ▾
李海涛,吉立新,葛东东. 基于DomiRank中心性的层影响不均多层网络脆弱性分析方法[J]. 信息工程大学学报, 2025, 26(03): 305-311 DOI:10.3969/j.issn.1671-0673.2025.03.008

登录浏览全文

4963

注册一个新账户 忘记密码

关键基础设施系统(Critical Infrastructure Systems, CIS)包括电力系统、电信系统、运输系统、金融系统等,它们是现代社会正常运转的基石。由于地位重要,CIS经常面临恐怖袭击、黑客入侵等的蓄意攻击破坏。因此,对CIS开展安全防护研究[1-2]具有重要意义。脆弱性分析[3-4]可以发现影响系统完整性和正常功能的关键组件,是CIS安全防护研究的基础。
复杂网络理论[5-6]将脆弱性分析问题转化为重要节点识别的研究,其核心是设计节点中心性指标。然后基于中心性指标开展节点攻击,依次删除网络中的重要节点,通过分析攻击效果评估网络脆弱性[7]。相同攻击强度下使得网络性能下降越快的中心性指标,其性能越好。当前研究提出了多种类型节点中心性指标,主要分为基于节点邻居特性的指标如节点度中心性,基于路径的指标如节点介数中心性,以及基于特征向量的指标如PageRank等[8]。文献[9]提出一种DomiRank中心性指标,通过单个可调参数整合局部和全局拓扑信息来评估节点重要性,其脆弱性分析效果优于大多数现有中心性指标。但是,这些指标多应用于单层网络脆弱性分析。而随着信息化和智能化不断演进,CIS间的关联日益紧密且彼此影响,更适合建模为多层网络进行研究。如何将上述指标拓展适用于多层网络脆弱性分析是一个亟需解决的问题。
当前,多层网络脆弱性分析研究尚处于起步阶段。文献[10]将智能电网看作信息物理异构互联系统,利用多层网络中心性指标确定系统重要节点集合。但是,该模型的多层指标只是各个单层指标的复合叠加。文献[11]充分考虑电力网络和通信网络之间的耦合特性,提出基于熵权法的多维多层节点重要度模型,为重要节点的分析和评估提供了理论依据。该方法虽然考虑了多层特性,但只是不同维度节点重要性的分别加权。上述方法均忽视了层间连接对网络脆弱性的不同影响。已有研究表明,在多层网络分析中不考虑网络间的相互作用,可能会在表征系统的真实脆弱性方面产生严重偏差[12]。因此,多层网络脆弱性需要从整体考虑,综合不同分层以及层间连接的特性开展全局分析。文献[13]将最优瓦解策略推广到多层网络,从全局攻击角度识别重要节点。文献[14]从相依网络的整体角度出发,研究了随机攻击、定向攻击和局部攻击组合下的脆弱性分析问题。但是,上述方法假定每个分层在网络脆弱性影响方面是同等的,这种假设并非总是成立。比如对于地铁和公交组成的多层网络,同一位置的地铁站点出现故障对出行所造成的影响往往要远大于公交站点停用所带来的影响。针对多层网络影响不均衡场景下的脆弱性分析仍需进一步研究。
针对以上需求,提出一种基于DomiRank中心性的层影响不均多层网络脆弱性分析方法。首先,构建多层网络模型,采用多层加权因子表征不同分层特性对网络脆弱性的影响;其次,基于多层网络加权超邻接矩阵,设计了改进的多层DomiRank中心性(Multi-layer DomiRank Centrality, MDRC)指标,并定义了度量脆弱性变化的多层网络性能指标;最后,利用MDRC大小降序排列多层网络所有节点,按照不同节点比例开展节点攻击,并基于攻击前后多层网络性能的变化分析脆弱性。仿真结果表明,该方法在脆弱性分析中的性能优于基于节点度中心性和节点介数中心性基准方法,且不同类型多层网络的脆弱性分析结果与网络实际特性相一致,实现了不同分层特性对脆弱性影响的区分。

1 系统模型

多层网络模型[15]由网络层和层间连边组成,如图1所示。

多层网络模型可表示为

M=(G,H)

式中:G表示不同的网络层,如层A与层B;H表示层间连边,灰色虚线为层间连边,黑色实线为层内连边,其中

G=Gαα1,2,,L

式中:L=G代表总层数;Gα=(Vα, Eα),Vαα层网络的节点集,Eαα层网络的层内连边集,式(3)可表示为

Eα=(Vαi,Vαj)Vαi,VαjVα;ij

层间连边H可表示为

H=Eαβα, β1,2,,L;αβ

EαβGαGβ的层间连边,则有:

Eαβ=(Vαi,Vβj)α, β1,2,,L,αβ

针对上述多层网络模型,文献[11]在开展脆弱性分析时将节点重要性定义为节点的自身拓扑重要性(节点度)、局部拓扑重要性(邻域内的最短路径比例)和全局拓扑重要性(节点介数)的综合加权。但是,该方法的节点重要性计算将不同分层对脆弱性的影响同等看待,未区分不同分层特性对多层网络整体脆弱性的影响,导致脆弱性分析结果不准确。

为此,面向图1的网络模型,本文引入多层加权因子wls以区分不同分层特性对网络整体脆弱性的影响。当l=s=A时,wls为层A内连边EA的加权因子;当l=A,s=B时,wls为层A和层B间连边EAB的加权因子。然后,基于wls给出多层网络加权超邻接矩阵A¯的定义:

A¯=w11A1w12C12w21C21w22A2

式中:A1表示层A的邻接矩阵;A2表示层B的邻接矩阵;C12表示层A和层B的连接关系矩阵;C21表示层B和层A的连接关系矩阵。

此外,多层网络具有多层关联性和动态变化性,不同网络层间深度耦合且节点重要性随节点邻域特性的变化而不同。多层网络节点中心性指标多数是基于网络拓扑的静态定义,忽略了网络内部的动态性,会带来脆弱性分析算法无法揭示网络深层脆弱性、算法性能不足的问题。为此,将引入动态竞争机制的DomiRank中心性拓展到多层网络,设计一种基于MDRC的多层网络脆弱性分析方法。

2 多层网络脆弱性分析方法

网络脆弱性通常基于节点攻击前后的网络性能变化进行衡量和分析。基于MDRC的多层网络脆弱性分析方法包括3个步骤:首先,基于多层网络加权超邻接矩阵计算得到每个节点的MDRC指标;然后,依据MDRC大小对多层网络中的所有节点进行降序排列,开展节点攻击并依序删除一定比例的网络节点;最后,计算并比较节点删除前后多层网络的性能变化,从而分析多层网络的脆弱性。

2.1 MDRC指标计算

多层网络DomiRank中心性通过引入竞争水平参数实现了节点与邻居之间不断竞争相互主导的动态过程。面向图1所示的多层网络,将MDRC定义为如下动力学方程的平稳分布。

dΓ(t)dt=αA¯(θ1N×1-Γ(t))-βΓ(t)

式中:αβθ为可调参数;limtΓ(t)=Γ为多层网络DomiRank中心性向量,该向量包含了多层网络中每个节点的DomiRank中心性指标数值,可表示为

Γ=θσ(σA¯+IN×N)-1A¯1N×1

式中:A¯为多层网络加权超邻接矩阵;IN×N是一个单位矩阵,N大小与网络中节点的数量相同;θ是一个常数,用于调节DomiRank中心性指标数值的规模,由于θ仅对DomiRank中心性起重新标度作用,因此不失一般性,令θ=1σ=αβ是一个可调节的竞争水平参数,它控制着局部节点和全局拓扑结构间的平衡,当σ较大时,该参数描述了节点在整个网络结构中的相对位置和作用,而当σ较小时,节点的DomiRank中心性指标数值更多地依赖于它们的局部连接特性,可表示为

σ(N)(0,-1λN)

式中,λNA¯的最小负特征值。同时,为了设计并行算法实现对Γ的高效计算,给出MDRC基于迭代方式的表达式:

Γ(t+dt)=Γ(t)+βσA¯(1N×1-Γ(t))-Γ(t)dt

通过求解式(10),可得到MDRC特征向量ΓΓ包含了多层网络每个节点的MDRC指标。

注意,求解使用的σ是最优竞争水平参数σ*,其计算方法为:对于式(9)σ收敛区间内的不同取值,迭代搜索获得对网络产生最大破坏攻击时的竞争水平参数。σ*的获取过程反映了Γ求解中的动态竞争机制。

2.2 基于MDRC的节点攻击

节点攻击对网络结构和功能的破坏程度反应了网络的脆弱性。可依据不同攻击策略开展节点攻击,这些策略包括基于MDRC指标的随机攻击、局部目标攻击和全局目标攻击等。本文使用基于每个节点MDRC指标的全局目标攻击策略,攻击对象是多层网络所有分层中的节点。

首先,按照MDRC大小对所有节点进行降序排列;然后,面向图1所示的多层网络M,对已经排序过的节点开展删除攻击,每次删除一定比例的多层网络节点;最后,变换删除比例,得到不同的删除节点集合,并依据该集合完成相应的节点攻击。因此,对于多层网络M中选定的删除节点集合,其节点攻击机制如下。

1)若节点集合中节点i的MDRC指标大于节点j的MDRC指标,则删除节点i

2)若节点集合中节点i的MDRC指标等于节点j的MDRC指标,则随机删除节点ij中的一个;

3)完成节点集合中所有节点的删除,得到节点攻击后的多层网络M^

2.3 多层网络脆弱性分析

本文通过比较攻击前后多层网络最大互连通片[16](Largest Mutually Connected Component, LMCC)的相对大小,来衡量多层网络的性能变化。

如果多层网络M中任意两个节点是连通的,则称M为连通图;当M中节点受到攻击并从M删除时,连通图分解为不同的子图或孤立节点;连通节点最多的子图为M的最大连通子图,定义该子图为多层网络的LMCC。此时,LMCC的大小定义为LMCC中包含的节点数,记为Φ。基于Φ,得到多层网络性能的度量指标η,可表示为

η=Φ(M^)Φ(M)

式中,η代表了LMCC的规模,对于初始多层网络Mη=1M受到攻击后的删除节点越多,η越小,网络破坏越严重,网络脆弱性越大。

给定攻击删除的节点比例为p[0,1],通过观察不同p取值下的η大小变化,可以实现对多层网络脆弱性的分析。以图2的多层网络为例,基于MDRC的多层网络脆弱性分析总体流程如算法1所示。其中,多层网络由层A和层B组成;橙色节点为层A的节点;蓝色节点为层B的节点;红色虚线为选中的攻击节点;红色节点为攻击失效节点;黑色实线为层内连边;灰色虚线为层间连边;图2(b)中深灰色底色包围的节点集合为攻击后的LMCC。

算法1 基于MDRC的多层网络脆弱性分析算法

输入:多层网络M

输出:不同节点删除比例下的网络性能η变化

1. 根据多层网络分层特性对层A、层B以及层间连接分别设定加权因子wls,由式(6)获得加权超邻接矩阵A¯

2. 求解A¯的最大负特征值λN

3. 基于λN迭代求解最优竞争水平参数σ*

4. 利用A¯σ*,由式(10)使用并行迭代算法计算得到层A和层B中所有节点的MDRC。

5. 按照MDRC大小降序排列所有节点。

6. 令节点删除比例p在[0, 1]间以一定间隔取值。

7. 基于节点攻击机制依序删除M中的节点,如层A的节点8和层B的节点7,直到删除节点比例等于p,得到攻击删除后的网络M^

8. 由式(11)计算M^的性能η,其中,节点攻击后的LMCC为图2(b)中深灰色底色包围的节点集合。

9. 重复步骤6~8,通过变化节点删除比例,得到多层网络面向不同攻击下的网络脆弱性变化。

3 实验与分析

为了对所提方法进行验证,选取基于节点度中心性、节点介数中心性和随机节点删除的脆弱性分析方法为基准,开展3类实验:一是对比实验,通过对比基于不同方法节点攻击造成的多层网络性能的变化,验证本文所提方法是否具有更优的性能;二是有效性实验,通过将本文所提方法应用于不同类型的多层网络,检验方法是否能有效揭示网络脆弱性;三是参数敏感性实验,对于本文所提用于表征分层特性对网络脆弱性不均匀影响的多层加权因子,分析其在不同组合参数设置下对脆弱性的影响。

针对多层网络层影响不均的特性,将适用于单层网络的节点度中心性、节点介数中心性向多层网络进行拓展。定义多层节点度中心性(Multilayer Degree Centrality, MDC)为

k˜i=j=1, jiNwij

式中:ijM中的节点;NM的总节点数;wijA¯中节点i和节点j间的连边加权因子。定义多层节点介数中心性(Multi-layer Betweenness Centrality,MBC)为

b˜i=k˜ik˜sitσst iσst

式中:k˜=1Nj=1Nk˜j为多层节点平均度;σst为节点s和节点t间最短路径的数目;σst i为这些最短路径中经过节点i的数目。同时,随机节点删除方法(Random Node Deletion, RND)以随机方式对节点进行删除。

多层网络数据集通过选取不同单层网络进行耦合构建。记每层网络分别为层A、层B,每层节点数为500。将层A中的节点按照节点度降序排列,分别与层B中按节点度降序排列的节点进行一一连接,得到节点规模为1 000的耦合双层网络。其中,典型单层网络有Erdős-Rényi(ER)随机网络[17]、Barabási-Albert(BA)无标度网络[18]和Watts-Strogatz(WS)小世界网络[19]。ER网络的节点以相同概率随机连接,BA网络的度分布具有幂律特性,WS网络同时具有较高聚集系数和较短平均路径长度,由这些网络耦合成的双层网络详情见表1。以ER-WS为例,ER代表层A,WS代表层B。

3.1 不同脆弱性分析方法对比

图3给出了3类典型方法与本文所提方法(图中所示为MDRC)的性能对比结果。令双层网络中层A的加权因子为1.5,层B的加权因子为1,层间加权因子为1。首先,计算每个多层网络的MDC、MBC和MDRC;然后,按照MDC、MBC和MDRC降序开展节点删除以及随机节点删除;最后,分析节点删除对网络的破坏效果。其中,使得网络性能下降最快的方法所选取的删除节点集合更好地反映了网络的脆弱特性。为消除随机性,每个方法进行100次独立实验。

图3可以看出,MDRC在BA-BA、ER-BA和ER-WS耦合网络中的脆弱性分析性能优于其他脆弱性分析方法,在ER-WS耦合网络中的性能优势最大。ER-WS耦合网络具有混合特性,部分节点具有较高聚集系数,这与MDRC中心性指标选取节点的原则匹配度更高,因此,基于MDRC的节点攻击删除方法在该网络上表现出更高的性能。在BA-WS耦合网络中,当节点删除比例小于0.5时,MDRC的性能优于MDC和MBC;当节点删除比例大于0.5时,MDRC的性能变差,但平均性能仍处于最优水平,说明MDRC在脆弱性分析性能方面具有平稳性,该特性在其他类型的网络中也有明显体现。在ER-ER耦合网络和WS-WS耦合网络中,MDRC的性能在多数情况下优于其他方法,其平均性能处于最优水平。RND方法的性能除了在WS-WS耦合网络中优于MDC之外,其他情况下的脆弱性分析性能最低。这进一步说明了基于节点重要性的攻击删除方法可以有效发现网络中的脆弱节点。基于MDRC的脆弱性分析方法在相同删除比例下能发现使得网络性能下降最快的节点集合,可以更深层地揭示网络的脆弱性。

3.2 MDRC下不同类型多层网络的脆弱性分析

图4给出了MDRC应用于不同类型双层网络的脆弱性分析结果。实验参数设置和上述实验保持一致,每个类型网络各开展100次独立实验。

图4可以看出,ER-ER耦合网络的脆弱性最小,BA-BA耦合网络的脆弱性最大,WS-WS耦合网络的脆弱性处于中间水平。ER网络没有明显的中心性节点,ER-ER组成的耦合网络对于基于MDRC的删除方法表现出最小的脆弱性。BA网络的少数枢纽节点具有非常高的度,而大多数节点的度较低,其节点度分布特性与MDRC的重要节点发现算法高度一致,基于MDRC的方法能找到使得网络性能下降最快的节点集合,使得BA-BA耦合网络的脆弱性最大。WS网络中局部网络的节点紧密连接,与低聚集的BA网络相比,脆弱性有所减小,WS-WS耦合网络脆弱性小于BA-BA耦合网络。其他类型耦合网络的脆弱性也与不同单层网络脆弱性的组合相一致,比如ER-WS耦合网络的脆弱性小于ER-BA耦合网络。MDRC脆弱性分析结果与耦合网络实际特性相一致,进一步验证了该方法的有效性。

3.3 多层加权因子影响分析

图5给出了多层加权因子对网络脆弱性影响的实验结果。选取BA-BA耦合网络,并记层A的加权因子为α,层B的加权因子为β,层间加权因子设置为1。对于多层加权因子的取值,一种情形为逐步拉大层A和层B间加权因子的差距,如α=1β=1逐步拉大到α=1β=5;另一种情形为对称变化层A和层B的加权因子,如α=5β=1α=1β=5。每个多层加权因子组合进行100次独立实验。

图5可以看出,不考虑分层影响即α=1β

=1时,多层网络表现出最大的脆弱性。这是因为,当不考虑不同分层影响时,节点删除会以类似于单层网络中的方式选择连接数目最多的节点进行攻击,从而使得网络较快进入瓦解状态。随着多层加权因子增大,网络脆弱性进一步减小。比如α=5β=1α=1β=5的多层脆弱性整体小于α=3β=1α=1β=3的多层脆弱性。此时,多层加权因子越大,不同分层的特性差别越大,分层间脆弱性的彼此影响越不明显,网络整体脆弱性减小。多层加权因子对称变化时,二者脆弱性虽有不同,但不同对称多层加权因子变化趋势相同,即层A多层加权因子大的网络脆弱性始终小于层B多层加权因子大的网络,如α=5β=1脆弱性小于α=1β=5α=3β=1脆弱性小于α=1β=3。这表明多层加权因子能够区分不同分层特性对脆弱性的影响。

4 结束语

针对现有分析多层网络脆弱性算法未考虑层影响不均特性对全局脆弱性的影响,以及算法性能不足的问题,提出一种基于DomiRank中心性的层影响不均多层网络脆弱性分析方法。首先,通过引入多层加权因子表征层间影响不均衡,构建多层网络模型;其次,将单层网络的DomiRank中心性拓展至多层网络,并设计改进算法;最后,利用MDRC指标开展节点攻击,通过观察网络性能变化实现了对多层网络脆弱性的分析。仿真结果表明,所提方法性能优于基于典型节点中心性指标的脆弱性分析方法,实现了不同分层特性对脆弱性影响的区分。

参考文献

[1]

KUMAR RKUMARI SMISHRA A. Robustness of multilayer networks: a graph energy perspective[J]. Physica A: Statistical Mechanics and Its Applications2023,628:No.129160.

[2]

ZHANG XLIU DTU H C, et al. An integrated modeling framework for cascading failure study and robustness assessment of cyber-coupled power grids[J]. Reliability Engineering & System Safety2022,226:No.108654.

[3]

BELLE AZENG Z GDUVAL C, et al. Modeling and vulnerability analysis of interdependent railway and power networks: application to british test systems[J]. Reliability Engineering & System Safety2022,217:No.108091.

[4]

TU H CXIA Y XCHEN X. Vulnerability analysis of cyber physical systems under the false alarm cyber attacks[J]. Physica A: Statistical Mechanics and Its Applications2022,599:No.127416.

[5]

郭程远,陈鸿昶,王庚润,基于迭代K-shell和改进信息熵的节点重要性排序算法[J].信息工程大学学报202223(5):556-562.

[6]

李腾达,王刚,杜冲,基于节点度的网络抗毁性加边策略[J].信息工程大学学报202425(5):608-614.

[7]

MUSAWI A F ALROY SGHOSH P. Examining indicators of complex network vulnerability across diverse attack scenarios[J]. Scientific Reports202313(1):No.18208.

[8]

YANG K WLI J CLIU M D, et al. Complex systems and network science: a survey[J]. Journal of Systems Engineering and Electronics202334(3):543-573.

[9]

ENGSIG MTEJEDOR AMORENO Y, et al. DomiRank centrality reveals structural fragility of complex networks via node dominance[J]. Nature Communications202415(1):No.56.

[10]

ALONSO MTURANZAS JAMARIS H, et al. Cyber-physical vulnerability assessment in smart grids based on multilayer complex networks[J]. Sensors202121(17):No.5826.

[11]

ZHAO MWU M QQIAO L L, et al. Evaluation of cross-layer network vulnerability of power communication network based on multi-dimensional and multi-layer node importance analysis[J]. IEEE Access202210:67181-67197.

[12]

OSAT SFAQEEH ARADICCHI F. Optimal percolation on multiplex networks[J]. Nature Communications20178(1):No.1540.

[13]

QI M ZDENG YDENG H Z, et al. Optimal disintegration strategy in multiplex networks[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science201828(12):No.121104.

[14]

LIU Y YZHAO C LYI D Y, et al. Robustness of partially interdependent networks under combined attack[J]. Chaos: An Interdisciplinary Journal of Nonlinear Science201929(2):No.021101.

[15]

BOCCALETTI SBIANCONI GCRIADO R, et al. The structure and dynamics of multilayer networks[J]. Physics Reports2014544(1):1-122.

[16]

LI H TJI L XLI Y L, et al. Robustness analysis of multilayer infrastructure networks based on incomplete information stackelberg game: considering cascading failures[J]. Entropy202426(11):No.976.

[17]

BARABASI A LALBERT R. Emergence of scaling in random networks[J]. Science1999286(5439):509-512.

[18]

BARABÁSI A LBONABEAU E. Scale-free networks[J]. Scientific American2003288(5):60-69.

[19]

WATTS D JSTROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature1998393(6684):440-442.

基金资助

河南省重大科技专项(221100210700)

AI Summary AI Mindmap
PDF (2646KB)

379

访问

0

被引

详细

导航
相关文章

AI思维导图

/