APP下载

基于m阶邻居节点的复杂网络关键节点评估

2019-05-23许梁煌郑玉芳

关键词:介数度值阶数

王 锋, 许梁煌, 郑玉芳

(福州大学土木工程学院, 福建 福州 350108)

0 引言

随着复杂网络小世界效应[1]及无标度性[2]的发现, 复杂网络研究已成为各个学科的研究热点, 复杂网络的鲁棒性研究[3-6]是复杂网络研究的一个重要分支. 研究表明: 不同拓扑结构的网络在承受不同的打击方式时表现出不同的鲁棒性, 无标度网络能够很好地抵抗随机攻击, 但在蓄意攻击下却迅速崩溃, 少数关键节点一旦被攻击, 网络便迅速瘫痪[7]. 蓄意攻击本质上是优先攻击网络中的“关键节点”, 因此如何确定网络中的关键节点意义重大. 通过节点重要度评估找出网络中重要的“关键节点”, 一方面可重点保护这些“核心节点”来提高整个网络的可靠性, 另一方面可攻击这些“薄弱环节”达到摧毁整个网络的目的.

目前复杂网络中的关键节点的评估方法主要分为两类: ① 节点重要性等于破坏性, 该方法通过比较在删除该节点后对网络的破坏程度来定义节点的重要性. 文献[8-9]基于源点到汇点最短路径来评价节点重要度, 最重要的节点定义为删除该节点使源点到汇点最短路径距离的增加最大; 文献[10]提出一种基于生成树数目的节点删除法, 定义最重要的节点为去掉该节点使得生成树数目最小, 而该方法存在片面性, 如处于网络末梢的一个节点在删除后造成该网络不连通, 依据这种方法该节点就会被评估为较为重要, 这显然与实际情况不符. ② 节点重要性等价于显著性, 从网络中寻找可以凸显节点的属性来“放大”, 用单一指标定义节点的重要性. 常见的属性有度、 介数、 凝聚度等, 文献[11]将凝聚度定义为网络平均距离与节点数乘积的倒数, 采用节点收缩前后网络凝聚度的变化来定义节点的重要度, 一般认为节点越重要, 收缩后网络的凝聚度越大; 文献[12]在此基础上进行改进, 引入节点连边重要度的概念, 将节点重要度定义为节点重要度和节点连边重要度的加权和.

上述网络研究只考虑了节点自身的属性, 并没有考虑与节点相邻的节点和连边的影响, 也忽略了节点在网络中的位置对重要度的影响, 而实际上节点的重要度和邻居节点有必然的联系, 单纯地从节点的某一属性考虑, 而不考虑相邻节点的影响, 显得不够全面, 从而影响评估的精度. 为弥补删除法和节点收缩法的不足, 文献[13-14]引入重要度评价矩阵的概念, 综合考虑节点的度值, 节点在网络中信息传输的作用以及邻居节点对目标节点的重要度贡献. 但这里所考虑的邻居节点也仅仅是与目标节点直接相连的节点. 而现实存在的复杂网络中, 节点的重要度不仅与其直接相连的邻居节点有关, 非直接相连的节点也对目标节点的重要度有较大的影响. 本文引入m阶邻居节点的概念, 考虑目标节点的m阶邻居节点对其重要度的贡献值, 以便使评估结果更具有可信度.

1 理论基础

1.1 基本概念

图1 复杂网络示意图Fig.1 Complex network diagram

设图G(V,E)是一个无自环的无向网络, 其中V={v1,v2,v3, …,vn}是网络中所有节点的集合;E={E1,E2,E3, …,En}是网络节点间边的集合, 如图1所示.

定义1点的度是指节点i所拥有的边的数量[15], 是刻画和衡量网络中节点特性最重要的指标. 一个节点的度越大说明该节点在网络中与其它节点的连接更加紧密. 其公式为:

(1)

式中:K表示节点的度值;n为网络中的节点数;e为节点i和j之间所连接的边数.

定义2节点介数是指整个复杂网络中经过该节点最短路径的数量比例, 是网络中节点和边在整个网络中的作用和影响力的体现, 是复杂网络的另一个重要指标. 其计算公式为:

(2)

式中:dinj为节点i和节点j之间的最短路径中经过节点n的数量;dij表示节点i和节点j之间的最短路径.

定义3节点效率值的大小反映节点到网络中其他节点的难易程度, 体现节点对网络信息传输所做的贡献. 节点的效率值越大, 在网络信息传输过程中所处的位置越重要. 节点i的网络效率值Ei为:

(3)

式中:n为网络中节点的数量;dki为节点k到节点i之间的距离.

1.2 m阶邻居节点的定义

图2 节点1各邻居节点示意图Fig.2 Neighbor nodes diagram belong to node 1

对于复杂网络G={V,E}中任意节点i(i∈V), 其一阶邻居节点为与节点i的最短距离为一步的节点, 该类节点构成的集合称作节点i的一阶邻居节点集, 记为&(1)(i); 同理, 其二阶邻居节点为与节点i的最短距离为两步的节点, 该类节点构成的集合称作节点i的二阶邻居节点集, 记为&(2)(i); 如此类推, 则与节点i之间的最短距离为m的节点称为m阶邻居节点, 其构成的集合称作节点i的m阶邻居节点, 记为&(m)(i). 节点1的一阶至三阶邻居节点如图2所示, 其中节点2、 3、 6、 10为一阶邻居节点; 4、 5、 7、 8、 11为二阶邻居节点; 9为三阶邻居节点.

1.3 构建m阶节点重要度评价矩阵

在构建m阶节点重要度评价矩阵时, 综合考虑邻居节点的重要度贡献以及节点在网络中的位置. 假设节点重要度评估过程中邻居节点的重要度贡献随距离的增加呈指数衰减趋势[16], 首先构建m阶邻居矩阵的重要度贡献系数矩阵. 网络的邻接矩阵反映了节点之间相邻的情况, 存在一定的映射关系并方便实现计算机编程计算, 若网络中有n个节点, 则构成n×n的邻接矩阵, 其具体的映射关系为:

(4)

对该映射关系做如下调整:

(5)

式(5)构成一个n×n的矩阵, 其中γ为可调参数, 且定义0<γ<1, 用于调整1到m阶邻居节点的依赖程度, 该映射关系综合考虑节点自身及1到m阶邻居节点的重要度贡献. 为便于理解, 可以将评估的m阶邻居节点称作节点重要度评估深度, 且其值应满足0≤m≤D,D值为网络的最大直径, 最后得到的矩阵如下式.

(6)

式(6)为n×n阶方阵, 矩阵中的所有元素均为1与γ的指数幂构成, 0≤x≤D, 该矩阵根据m值大小而变化, 当x=m时, 矩阵中x>m的位置均以0代替, 即得到m阶邻居矩阵重要度贡献系数矩阵Am.

为全面考虑其他阶数的邻居节点的重要度贡献, 基于文献[1]做以下改进: 1)节点vi为所有m阶邻居节点贡献ki/K2的重要度; 2)该重要度的贡献值根据不同的邻居阶数乘以相同的系数. 所有节点对其m阶邻居的度重要度贡献值用矩阵的形式表现出来, 如下式.

(7)

式(7)中的对角线表示节点对自身的重要度贡献值为1, 其与邻接矩阵的映射关系规则如下式.

(8)

该映射规则反映了网络重要度贡献关系的拓扑, 并充分利用邻接矩阵的信息.

为反映节点在网络中的位置重要性, 采用网络效率来衡量节点在网络中的位置关系. 对上述度重要度贡献比例矩阵(7)进行改进, 将矩阵中所有对角线的元素用相对应的节点效率值进行替换, 得到改进后的重要度贡献矩阵, 如下式.

(9)

类似地构建m阶邻居节点的介数重要度贡献矩阵如下式.

(10)

其中Ji表示节点i的介数值, 其映射关系为:

δij=Ji(i=j);δij=Jj(i≠j)

(11)

考虑节点m阶邻居矩阵的度以及介数重要度贡献矩阵, 节点的最终重要度矩阵Cn×n定义如下:

(12)

Ii=Cii(i∈[1,n])

(13)

2 节点重要度的确定算法

综合考虑节点自身的属性、 节点在网络中的位置、m阶邻居节点度重要度贡献和介数重要度贡献后建立评价模型, 其算法如下.

1) 根据网络中各个节点的邻接关系, 由本文提出的映射规则确定整个网络m阶邻居矩阵重要度贡献系数矩阵;

2) 确定网络的重要度贡献比例矩阵T1;

4) 确定网络的介数重要度贡献矩阵T2;

5) 根据重要度定义公式计算各个节点的重要度.

根据本文所提出的模型方法, 可看出整个重要度确定的关键在于m阶邻居矩阵中m的取值, 若取值太小, 评估过程将依赖于节点自身的特性, 从而忽略网络中某些节点对目标节点的重要度贡献, 即忽略节点在网络中的位置信息, 评估结果将近似于传统连接度和连接介数方法; 反之, 若m取值太大, 一方面增大了算法的复杂性, 另一方面m值的不断增大对评估是否有影响及影响程度, 将是实验讨论的重点.

3 实验分析

3.1 本文与其它算法的评价结果对比

图3 实验分析复杂网络示意图Fig.3 Experimental analysis of complex network schematics

ARPA拓扑网络是目前研究复杂网络普遍使用的拓扑干线网络, 其网络的平均度值为2~3之间, 其中大部分节点的度值为2, 如图3所示. 本文研究时所选的分析网络与ARPA拓扑网络基本相似. 该图存在24个节点, 28条边, 网络的平均度为2.42, 平均路径长度为4.75, 直径为9. 如果单纯采用度值对其进行分析, 显然不尽合理, 网络中存在15个节点的度值为2, 但是这15个节点的重要度显然并非全部相同, 如节点6和节点16.

文献[1]提出考虑节点的介数法来对节点重要度进行评估, 但无法细分介数值相同的节点; 如果采用节点删除法对网络进行分析, 由于网络拓扑结构的特殊性, 节点1、 13、 14、 16、 17、 18在删除之后对网络重要性影响都是相同的, 因此无法区分其重要度; 文献[11]采用节点收缩法对网络进行分析, 考虑的是收缩前后网络凝聚度的变化情况, 网络凝聚度又与网络的节点完全相同, 因此也无法区分其重要度. 综上分析, 上述算法均存在其缺陷, 无法对某些网络的节点重要度进行精确区分, 并且对一些特殊节点也发挥不了作用. 现应用本文所提出的算法对该网络进行分析并与其它算法进行对比, 其分析结果如表1所示(取ω1,ω2,γ=0.5).

表1 节点重要度评估结果

由表1可知, 本文算法与其他算法相比, 存在以下两点不同: 1) 由于考虑了邻居节点之间的相互影响, 使得节点之间的重要度在可以区分的前提趋于接近, 相对于其他算法, 评估结果更为精细. 2) 用本文算法进行节点重要度识别时,m的阶数取接近于网络的平均直径时(本文网络的平均直径为4.75, 因此m取5), 评价结果会趋向稳定.

不同的算法所得结论存在较为明显的差异, 如度值法认为重要度靠前的节点是{11, 3, 12, 7, 8}; 介数法的评估结果则是{24, 3, 14, 18, 7}; 本文算法随着m取值的不同, 结果略有变动, 但重要度排序在前的几个节点主要为{12, 24, 3, 8, 7}, 这与文献[11]、 文献[13]、 度值法以及介数法的结果基本符合, 即本文算法与其他算法对于较为重要的节点集均为{11, 3, 21, 24, 8}. 度值法的不足在于无法细分度值相同节点的重要度, 如节点{11, 17, 10, 14, 18}等, 这些节点在网络中的作用和位置不尽相同, 但度值法无法对其做更加精确的判别; 仅仅根据介数指标得出的结果认为v14的重要度排在第3,v11排在第11, 这显然不尽合理,v11处于网络连接的关键通路, 起到“桥梁”的作用, 其重要性应大于v14.

综上, 本文算法可以对前述的节点集进行精度更高的细分且能够解决单一评估指标带来的片面性, 说明本算法的可行性. 本文所提出的方法综合考虑了节点在网络中的全局重要性及局部重要性, 较好地顾及了节点自身及1到m阶邻居节点对该节点的重要度贡献. 运用本文方法对节点重要度进行评估, 可以显著地区分节点之间的重要度差异, 具有较高的评估精度. 随着邻居节点阶数m值的增加, 从重要度的排序看其结果逐步趋向稳定, 为进一步分析m的取值对于评估结果的影响, 针对上述例子, 构建小世界网络随机进行分析.

3.2 m取值对实验结果的影响

图4 小世界随机网络示意图Fig.4 Small world random network diagram

m∈[0,D], 针对上文的实验分析构造小世界网络, 分析节点重要度随m取值的变化情况. 所构造出的小世界随机网络如图4所示, 网络参数分别为: 节点数为20, 邻居节点概率为2, 重连概率取0.5, 平均路径长度为2.63, 平均度值为4, 网络的直径为4, 平均介数值0.064 6.

运用本文所提出的算法在邻居节点阶数m取值不同的情况下对小世界随机网络和上文实验分析所采用的网络节点的重要度进行评估, 结果汇总如图5所示.

图5 关键节点重要度随m变化图Fig.5 The key node importance changes with m

从实验分析可知, 随着邻居阶数m的增加, 节点的重要度值呈现先增加后稳定的趋势, 即节点的重要度从“不稳定的状态”向“稳定的状态”转化, 而阈值为网络的平均路径长度m0. 当m∈{0,m0]时, 节点的重要度处于“不稳定状态”; 当m∈[m0,D]时, 节点的重要度处于稳定状态, 即重要度随着m的增加几乎不再增加. 由此得出结论: 运用本文算法进行节点重要度评估时, 只要m>m0, 便可以得出稳定的节点重要度. 因复杂网络的节点和直径可能会很大, 这一规律的发现有利于评估效率的提高.

4 结语

针对复杂网络的节点重要度评估问题, 在总结节点删除法、 节点收缩法的不足之后, 本文综合考虑节点自身的效率值, 即节点在网络中的信息传输快慢, 节点度值, 节点在网络中的位置关系以及m阶邻居节点的度值和介数重要度贡献, 建立评估模型. 该模型通过节点的效率值来表征节点的全局重要性, 通过m阶邻居节点的重要度贡献来表征节点的局部重要性, 并通过实验分析与其他算法进行对比, 结果表明本文的算法具有更高的评估精度, 验证本文算法的有效性. 此外, 为得到邻居阶数m的数值与节点重要度稳定性的关系, 借助小世界随机网络进行实验分析, 结果表明邻居阶数m趋于网络的平均路径长度时, 节点的重要度趋于稳定状态.

猜你喜欢

介数度值阶数
探讨公路项目路基连续压实质量检测技术
确定有限级数解的阶数上界的一种n阶展开方法
复变函数中孤立奇点的判别
无线传输中短码长喷泉码的度分布优化算法*
微博网络较大度值用户特征分析
基于电气介数的电力系统脆弱线路辨识
树形网络的平均介数*
关于动态电路阶数的讨论
基于电流介数的电力系统脆弱性评估
基于电气介数的继电保护定值在线校核