基于多重影响力矩阵的有向加权网络节点重要性评估方法-王雨.pdf

《基于多重影响力矩阵的有向加权网络节点重要性评估方法-王雨.pdf》由会员分享，可在线阅读，更多相关《基于多重影响力矩阵的有向加权网络节点重要性评估方法-王雨.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于多重影响力矩阵的有向加权网络节点重要性评估方法王雨郭进利Evaluation method of node importance in directed-weighted complex network based on multiple influ-ence matrixWang Yu Guo Jin-Li引用信息Citation: Acta Physica Sinica , 66, 050201 (2017) DOI: 10.7498/aps.66.050201在线阅读View online: http:/dx.doi.org/10.7498/aps.66.050201当期内容View

2、 table of contents: http:/ you may be interested in基于最小刚性图代数特性的无线网络拓扑优化算法Topology optimization algorithm for wireless networks based on the algebraic properties of minimum rigidgraph物理学报.2016, 65(24): 240201 http:/dx.doi.org/10.7498/aps.65.240201基于复杂网络理论的多元混合空管技术保障系统网络特征分析Analysis on network propert

3、ies of multivariate mixed air traffic management technical support systembased on complex network theory物理学报.2016, 65(14): 140203 http:/dx.doi.org/10.7498/aps.65.140203无标度网络中基于能量的混合路由策略Energy-based hybrid routing strategy for scale-free networks物理学报.2016, 65(24): 248901 http:/dx.doi.org/10.7498/aps.

4、65.248901一种有效的基于三角结构的复杂网络节点影响力度量模型An efficient node influence metric based on triangle in complex networks物理学报.2016, 65(16): 168901 http:/dx.doi.org/10.7498/aps.65.168901花簇分形无标度网络中节点影响力的区分度Discriminability of node influence in flower fractal scale-free networks物理学报.2015, 64(20): 208901 http:/dx.doi.

5、org/10.7498/aps.64.208901万方数据物理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201基于多重影响力矩阵的有向加权网络节点重要性评估方法 王雨郭进利y(上海理工大学管理学院,上海200093)(2016年10月15日收到; 2016年11月23日收到修改稿)本文基于有向加权网络模型,构建了三个影响力矩阵,并利用层次分析法对其赋权求和,形成多重影响力矩阵,从而提出了一种基于该矩阵的节点重要性评价方法.该方法通过新定义的交叉强度指标,来表征节点的局部重要性;利用全网节点对待评估节点的重要性影响总值,来表征节点在全网中的相对重要性.

6、在分析影响节点对待评估节点的影响比例时,既考虑到节点间的距离因素,又引入了最短路径条数因素;既考虑了该影响节点对网络中其他节点的影响关系,又考虑了网络中其他节点对该待评估节点的影响关系,使得评价方法更加全面.将算法运用于ARPA网络,结果表明,该方法能有效地区分各节点之间的差异.最后,对实验结果进行连锁故障的仿真对比实验,进一步验证了方法的有效性.关键词:有向加权网络,节点重要性,多重影响力矩阵,最短路径条数PACS: 02.10.Ox, 89.75.Hc, 89.75.Fb DOI: 10.7498/aps.66.0502011引言复杂网络具有非同质的拓扑结构,这决定了网络中的每个节点不可能

7、具有完全相同的重要程度1.因此,采用定量方法挖掘出网络中的关键节点,并对其性质进行针对性的分析和利用具有十分重要的意义2,它有助于提高整个网络的可靠性与抗毁性3;4.目前,节点重要性评估的研究多集中在无向或无权网络上5 12,然而,现实世界中的网络多数是有向加权网络,不仅要考虑节点之间相互作用的强弱12,还要考虑其方向5.将节点重要性评估的研究拓展到有向加权网络,对于推动复杂网络的发展具有更为重要的实用价值.国内外学者从不同角度提出了多种有价值的评价方法. “中心性”常用来衡量节点的重要性,常见的指标有度、接近中心性、介数、累计提名等.例如Jeong等13利用度指标研究了蛋白质网络.然而,度相

8、同的节点在网络中的重要度未必相同.另外,度指标仅利用了节点最局部的邻居信息,并没有考虑节点在网络中的位置,其应用非常有限.Freeman14于1977年在研究社会网络时提出介数指标.但该指标需要计算网络中任意节点对之间的最短路径,其算法的时间复杂度较高,对于大规模网络并不适用.近年来,有学者开始基于信息扩散的视角识别网络中的关键节点.例如Kitsak等15提出利用k-核(ks)分解法来挖掘中心节点.该方法认为ks指标越大的节点越重要.然而,在BA网络和树形网络中,所有的节点具有相同的ks值,同层的节点无法比较其重要性.另外,该方法也不能直接运用于有向网络、加权网络. L等16提出了Leader

9、Rank算法,该算法没有参数,相比经典的PageRank算法17更加精准.但是,标准的LeaderRank算法中背景节点和所有节点的连接都一样,不切合实际且不能直接运用到加权网络.目前有向加权网络节点重要度评估的研究国家自然科学基金(批准号: 71571119)资助的课题.通信作者. E-mail: 2017中国物理学会Chinese Physical Society http:/050201-1万方数据物理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201还相对较少. Xu等18借鉴PageRank算法,提出一个有向加权网络节点重要性的评价指标DW

10、CN-NodeRank.但是,该算法不能同时获得较高的评估精度和较快的收敛速度. Liu等5充分利用网络的拓扑结构特征和邻居节点的重要性,提出了一种基于交互信息的节点重要性评价方法,该方法将节点所包含的信息量作为其重要性的衡量指标.节点所包含的信息越多,就越重要,这在一定程度上能区分节点间的差异.但该方法仅考虑了网络的有向性,而没有对加权网络进行讨论,王班等19对其进行改进,使其适用于有向加权网络.但是,文献5, 19均只考虑了邻居节点之间的交互信息,而忽略了那些非直接相邻的节点之间也可能沿着某路径进行信息交互,不够全面.周漩等20结合节点的效率和度值,提出了节点重要度贡献矩阵的概念,以此表示

11、节点之间的相互依赖关系,进而判断节点的重要度.但是,该方法将节点的重要度平均贡献给邻居节点,且认为这种重要性依赖关系仅仅存在于邻居节点之间,与现实不符.实际上,当网络具有较强的连通性,即所有节点之间的关系比较紧密时,非邻居节点之间的相互依赖关系就不能被忽略. Hu等21以及范文礼和刘志刚22分别提出了基于重要度贡献关联矩阵和网络传输效率矩阵的节点重要性评价方法.这两种方法不仅认为邻居节点之间存在相互作用,而且考虑到非邻居节点也可通过某种途径向待评估节点贡献自身的重要度,克服了重要度贡献只依赖邻居节点的不足.但是,传输效率矩阵在判断重要性贡献比例值时,仅考虑了节点间的最短路径长度这一因素,显然不

12、够全面.事实上,两节点间的相互影响程度还与二者之间的最短路径条数相关.基于以上考虑,本文通过新定义的交叉强度指标,来表征有向加权网络中节点的局部重要性.为研究节点在全网中的相对重要性,本文不仅同时考虑了最短路径长度和最短路径条数两个影响因素,还分别从影响节点和待评估节点两个角度构建了另外两个影响力矩阵,以此来表示全网节点之间的重要性影响关系,进而提出了基于多重影响力矩阵的综合评价算法.本文结构如下:在第二部分,引入交叉强度指标及其他相关指标.在第三部分,构建三种影响力矩阵,并运用层次分析法求得“多重影响力矩阵”,进而提出评价算法.在第四部分,将评价方法运用于几个具体的有向加权网络,并进行仿真实

13、验分析,以此验证算法的有效性.在最后一部分,给出本文的总结.2理论基础有向加权复杂网络模型G = (V;E;W).其中V = fv1;v2; ;vng为节点集合, E =fe1;e2; ;emg为边集合, (vi;vj) 2 E,表示从节点vi到vj的一条有向边.网络节点数目为n = jVj,边数为m = jEj.邻接矩阵记为An n = (aij),当且仅当存在一条从节点vi指向vj的有向边时aij = 1,否则aij = 0. W表示有向边的权重矩阵, wij表示有向边(vi;vj)的权值.有向加权网络的权重矩阵一般不对称,即wij = wji.在有向加权网络中,每个节点的强度可以分为入强

14、度和出强度23.强度指标将入强度和出强度简单相加,无法有效区分两者之间的差异.针对这一问题,本文把有向加权网络中入强度和出强度的概念相结合,提出节点交叉强度的概念.定义1交叉强度.为了综合考虑节点的入强度和出强度,本文将节点vi的交叉强度定义如下:Sci = Sini + (1 )Souti ; (1)其中, 是一常数,它满足0 0:5时,节点的入强度被认为对节点的重要性影响程度更大;当 2),由于(Ak)ij =nm1=1nm2=1nmk 2=1nmk 1=1aim1am1m2 amk 2mk 1amk 1j;所以, (Ak)ij表示了从节点vi到节点vj之间长度为050201-3万方数据物

15、理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201k的路径总数.本文假设节点优先通过最短路径向网络中其他节点传播自身的重要性,因此可利用该条性质计算从节点vi到节点vj之间的最短路径数,即长度为dij的路径总数(Adij)ij.当i = j或从vi到vj不存在路径时, dij ! 1, (Adij)ij = 0.需要特别强调的是,某节点vi(影响节点)对节点vj(待评估节点)的影响程度除了取决于两节点间的距离大小、最短路径条数,还取决于其他节点对vj的影响以及vi对其他节点的影响.比如,在其他条件不变时,如果网络中的其他节点均不对vj产生影响,那么v

16、i对vj的影响程度就会相对变大,反之就会变小;另一方面,在其他条件不变时,如果vi仅对vj产生影响,而不存在指向其他节点的连边那么vi对vj的影响程度也会相对变大,反之就会变小.因此,可以基于最短路径条数对这两种情况进行分析,分别构建以源节点,即影响节点为中心的影响力矩阵SIP (source node-centred in-uence power matrix)和以目标节点,即待评估节点为中心的影响力矩阵TIP (target node-centredinuence power matrix):SIP =0BBBBBBBBBBBBBB0 Ad1212Ad1211 +Ad1212 +Ad121

17、3 + +Ad121n Ad1n1nAd1n11 +Ad1n12 +Ad1n13 + +Ad1n1nAd2121Ad2121 +Ad2122 +Ad2123 + +Ad212n 0 Ad2n2nAd2n21 +Ad2n22 +Ad2n23 + +Ad2n2n. . . .Adn1n1Adn1n1 +Adn1n2 +Adn1n3 + +Adn1nnAdn2n2Adn2n1 +Adn2n2 +Adn2n3 + +Adn2nn 01CCCCCCCCCCCCCCA;(5)TIP =0BBBBBBBBBBBBBB0 Ad1212Ad1212 +Ad1222 +Ad1232 + +Ad12n2 Ad1n1

18、nAd1n1n +Ad1n2n +Ad1n3n + +Ad1nnnAd2121Ad2111 +Ad2121 +Ad2131 + +Ad21n1 0 Ad2n2nAd2n1n +Ad2n2n +Ad2n3n + +Ad2nnn. . . .Adn1n1Adn111 +Adn121 +Adn131 + +Adn1n1Adn2n2Adn212 +Adn222 +Adn232 + +Adn2n2 01CCCCCCCCCCCCCCA:(6)对于矩阵SIP,元素为Adijij/ nk=1Adijik (i;j =1; 2; ;n),其分子表示从节点vi到节点vj的最短路径数,即长度为dij的路径数,分母表

19、示从节点vi到网络中所有节点长度为dij的路径数总和,二者的比值是从固定影响节点vi的角度,来分析其对vj的影响比例的;对于矩阵TIP,元素为Adijij/ nk=1Adijkj (i;j = 1;2; ;n),其分母表示网络中的所有节点到节点vj长度为dij的路径数总和,分子与分母的比值是从固定待评估节点vj的角度,来分析vi对其的影响比例的.由矩阵元素的分母表示还可以看出,这两个矩阵均考虑到了其他节点对在非自身最短路径上的信息传播对所研究节点对之间依赖程度的影响.123 546图1一个简单的拓扑结构Fig. 1. A simple topological structure.图1是含有5个

20、节点的简单拓扑结构,图2(a)和图2(b)分别是从某影响节点和待评估节点的角050201-4万方数据物理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201度提取的图1网络的部分拓扑结构.以此为例,利用上述3个矩阵,从不同角度比较各重要性影响比例值的大小.由于重要性影响比例是根据信息传输的路径来分析的,所以暂不考虑连边上的权重值.123 54(a)23 546(b)图2分别从某影响节点和待评估节点的角度提取的图1网络的部分拓扑结构(a)节点v1影响v3, v5的路径图; (b)节点v2, v4影响v6的路径图Fig. 2. Part topology e

21、xtracted from gure 1 from theperspective of acertain sourcenode and target node:(a) The path graph that v1 inuences v3 and v5;(b) the path graph that v2 and v4 inuence v6.根据(4)(6)式得:E =0BBBBBBBBBBB0 1 0:5 1 0:5 0:330:33 0 1 0:25 0:2 0:50:5 0:33 0 0:33 0:25 10:33 0:25 1 0 1 0:50:5 0:33 0:25 0:33 0 11

22、 0:5 0:33 0:5 0:33 01CCCCCCCCCCCA;SIP =0BBBBBBBBBBB0 0:5 0:67 0:5 0:33 11 0 1 0:5 0:33 11 0:5 0 0:5 0:33 11 0:5 0:5 0 0:5 11 0:5 0:67 0:5 0 11 0:5 0:67 0:5 0:33 11CCCCCCCCCCCA;TIP =0BBBBBBBBBBB0 1 1 1 1 10:33 0 0:5 0:33 0:33 0:330:5 0:5 0 0:5 0:5 0:50:67 0:67 0:5 0 1 0:670:5 0:5 0:5 0:5 0 0:51 1 1 1

23、 1 01CCCCCCCCCCCA:效率矩阵主要用于两节点间距离不相等时的影响比例比较,而矩阵SIP和TIP分别是从影响节点和待评估节点的角度,用于两节点间距离相等时的影响比例的比较.一般来讲,当比较重要性影响比例大小时,首先要考虑的就是节点间的距离,然后再考虑距离相同时, SIP和TIP中元素的大小.从节点间的效率角度,由于d13 = 2 e16,所以节点v1对v3的影响比例要大于v1对v6的影响比例.从SIP的角度,比较同行元素.以v1对v3,v5的影响为例,图2(a)给出v1影响v3, v5的路径图.虽然e13 = e15 = 0:5,但是由于v1到v3的最短路径数2大于v1到v5的最短

24、路径数1,导致SIP13 = 0:67 SIP15 = 0:33.因此单从影响节点的角度,节点v1对v3的影响比例要大于v1对v5的影响比例.当然实际的影响比例还与v3, v5各自对应的TIP有关.从TIP的角度,比较同列元素.以v2, v4对v6的影响为例,图2(b)给出v2, v4影响v6的路径图.虽然e26 = e46 = 0:5,但是由于v4到v6的最短路径数2大于v2到v6的最短路径数1,导致TIP46 = 0:67 TIP26 = 0:33.因此单从待评估节点的角度,节点v4对v6的影响比例要大于v2对v6的影响比例.当然实际的影响比例还与v2, v4各自对应的SIP有关.3.3构

25、建多重影响力矩阵由以上分析可知,节点之间的影响程度同时受到节点间的距离、最短路径数以及影响节点对网络中所有节点的影响比例、网络中所有节点对待评估节点的影响比例的多重制约.因此,要想全面反映节点间的影响比例大小,就需要对矩阵E、矩阵SIP和TIP进行赋权加总,构建多重影响力矩阵.各矩阵权重的计算使用改进的层次分析法29得出,步骤如下:第一步,采用(0, 1, 2)三标度法对每一个矩阵进行两两比较,建立比较矩阵;第二步,利用极差法将比较矩阵转化为判断矩阵,并进行一致性检验,最后得到矩阵权重.具体的计算方法参见文献29.表1列出了按照(7)式三标度法构造的比较矩阵B中的元素值.050201-5万方数

26、据物理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201表1 (0, 1, 2)三标度法构建各矩阵重要性的比较值Table 1. Importance comparison of matrix with (0, 1,2) three-demarcation method.B E SIP TIPE 1 2 2SIP 0 1 1TIP 0 1 1表1中的比较矩阵B = (bij) =8:2;矩阵i比矩阵j重要;1;矩阵i与矩阵j同等重要;0;矩阵j比矩阵i重要:(7)比较矩阵B的构建是基于以下考虑:效率矩阵E通过距离直接体现了节点间的亲疏关系,而且在比较节

27、点间的影响比例值大小时,首先要考虑的是两节点之间的距离,然后再去考虑当距离相同时,最短路径数对比例值的影响.因此可认为效率矩阵E比其他两个矩阵更加重要;而矩阵SIP和TIP都是基于最短路径数来研究节点间的相互影响的,区别仅在于侧重点不同, SIP考虑到影响节点对网络中所有待评估节点的影响, TIP考虑到网络中所有影响节点对待评估节点的影响,这两种情况都需要考虑在内,无法比较其好坏,因此认为这两个矩阵具有同等的重要性.经一致性检验,得到各矩阵的权重值分别为wE = 0:82, wSIP = 0:09, wTIP = 0:09.对各矩阵加权求和,便得多重影响力矩阵M:M = (mij)n n= 0

28、:82E + 0:09SIP + 0:09TIP: (8)M中的元素mij表示考虑各因素后,节点vi对vj的综合影响比例值.由于节点效率值能体现该节点对于整个拓扑网络信息传输的贡献,因此,选取节点效率作为其对整个网络节点重要性影响的初始值.那么每个节点对网络中其余节点的依赖程度值便可用矩阵P表示:P = (pij)n n =0BBBBBB0 I1m12 I1m1nI2m21 0 I2m2n. . . .Inmn1 Inmn2 01CCCCCCA:(9)矩阵P是多重影响力矩阵M的第i行中的数都乘以Ii得来的,其中pij = Iimij表示节点vi对vj的重要性综合影响值.在考虑全网节点对待评估节

29、点重要性影响值的基础上,结合待评估节点自身的局部重要性(交叉强度值),可以定义节点vi的重要度Di:Di = Sci nj=1;j=iIjmji; (10)其中nj=1;j=iIjmji表示节点vi在全网中的相对重要性,它是网络中所有节点对节点vi的重要性综合影响值之和,记作pi.归一化后,节点vi的重要度为Di = Di/ nk=1Dk: (11)3.4算法流程本文算法充分考虑了节点的局部重要性和其受网络其他节点的依赖程度.已知网络的邻接矩阵A和权重矩阵W,其具体的算法步骤如下:第一步,计算所有节点对之间的最短距离Dis = dij/有向网络的Floyd算法;第二步,根据权重矩阵和定义1,计

30、算出每个节点的交叉强度Sci(i = 1; ;n);第三步,根据定义2,计算出每个节点的效率值Ii(i = 1; ;n)和所有节点对之间的效率值eij(i;j = 1; ;n),填入效率矩阵E;第四步,根据各节点对之间的距离dij,计算所有涉及的矩阵Adij,并按式Adijij/ nk=1Adijik和Adijij/ nk=1Adijkj ,将各比例值分别填入矩阵SIP和TIP中;第五步,按照(8)式,确定多重影响矩阵M;将矩阵M的第i行中的数都乘以Ii,确定矩阵P;第六步,根据(10)式和(11)式,计算每个节点的重要度Di.第七步,将所有节点按照重要性值从大到小进行排序.考虑到有些节点仅存

31、在出边,而不存在入边,比如微博网络中的“僵尸用户”,引文网络中的从未被引用的文章等,这时它们的重要度指标Di050201-6万方数据物理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201都为0.为了增强此类节点的可比性,本文对此类节点的处理如下:当两个节点的Di值均为0时,比较二者的交叉强度值,值越大的节点,排序越靠前,节点越重要.4实证分析4.1算法有效性分析首先以图3所示的具有对称结构的有向加权网络19为例,运用本文所提算法计算每个节点的交叉强度Sci以及最终的重要性指标Di,并与文献19中的交互信息评价方法进行对比分析.注意,文献19是对文献5的

32、改进,使其评价方法能适用于有向加权网络(不妨令 = 0:8).计算得到各节点的重要性指标值和排序结果,列于表2.本文算法可以得出重要性的排序: v4和v7最重要,排在首位; v3和v8同等重要,仅次于v4, v7;v1和v9同等重要,次于v3, v8; v2和v10最不重要,排在末位.合理的解释为:从图3可以看出,节点v4和v7处于全局信息控制能力最大的位置,相当于两个“桥节点”,如果两个节点被删除,会直接导致网络不再连通,因此v4和v7的重要性最大;同样地, v3和v8的删除也会导致网络不连通,但相对于v4和v7,与v3和v8相关联的节点要少一些,因此重要性次之; v5和v6相互连接,但并没

33、有起到“桥梁”的作用,因此重要性稍差;节点v1, v9和v2, v10在网络中的位置相同,都处于网络的边缘且都没有入边,但相对于v1, v9,节点v2, v10的出强度更小一些,因此排序就更为靠后.另外,从表2还可以看出,本文算法可以得出与文献19完全一致的前4个重要节点,再次说明了本文算法的有效性.但是,本文算法与文献19在评价节点重要性上还是存在一定差异的,比如文献19认为节点v1, v9和v2, v10的重要性都要优先于v5和v6.为此表3给出了删除相应节点后网络的平均效率值的变化.由表3不难看出,删除节点v5后,网络的平均效率有所下降,这说明节点v5的删除在一定程度上减弱了网络的信息流

34、通;而删除节点v1后,网络的平均效率反而上升,这说明节点v1的删除使得网络的通讯冗余度减少,反而提高了整个网络的通信能力.那么可以认为,节点v5和v6的重要性要大于v1, v9和v2, v10.因此,本文方法在评价节点重要性上相对更加准确.表2图3所示网络的节点重要性排序结果Table 2. Importance ranking results of network nodesshown in Fig. 3.节点序号本文算法文献19Sci Di排序重要度排序1 0.6 0 7 0.5108 52 0.4 0 9 0.9163 73 4.6 0.1165 3 0.7340 34 5.2 0.37

35、14 1 2.0794 15 0.7 0.0121 5 1.3863 96 0.7 0.0121 5 1.3863 97 5.2 0.3714 1 2.0794 18 4.6 0.1165 3 0.7340 39 0.6 0 7 0.5108 510 0.4 0 9 0.9163 7表3删除相应节点前后图3网络的平均效率值Table 3. The average eciency of network shown ingure 3 before and after removing node.网络性质初始网络删除v5或v6删除v1或v2网络平均效率I 0.1926 0.1921 0.215331

36、23 45 67 892322 3230.50.51 110图3具有对称结构的有向加权网络拓扑Fig. 3. A directed weighted network topology with symmetric structure.050201-7万方数据物理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201从对图3网络的实验可以看出,本文算法对简单的有向加权网络进行节点重要性评估可以取得良好的结果.为了进一步验证本文方法的有效性,本文利用了美国的ARPA (advanced researchproject agency)网络拓扑进行研究. ARPA

37、拓扑属于无向无权网络,为此,本文先对其进行边赋权30得到无向加权网络,在此基础上再进行边定向19得到有向加权网络,如图4所示.其中边的定向原则是:首先计算加权网络中每个节点的强度,然后比较边(vi;vj)的两个端点vi与vj的强度大小.当Si Sj时,确定边的方向为vi指向vj.当Si = Sj时,再比较vi和vj各自相邻节点的强度之和,当k2 (vi)Sk l2 (vj)Sl ( (vi), (vj)分别为节点vi和vj的邻居节点集合)时,确定边的方向为vi指向vj.当k2 (vi)Sk =l2 (vj)Sl时,节点vi与vj之间存在双向连边,并将无向边(vi;vj)上的权值平均分配给两条有

38、向边.由边赋权和边定向的定义原则可知,该有向加权网络与原无向无权网络中各节点的重要度相似.表4给出了本文所提算法以及文献19, 21, 22所述方法确定的节点重要性排序结果(不妨令= 0:8).表4加权定向后的ARPA网络节点重要性排序结果Table 4. Importance ranking results of nodes in directed weighted ARPA network.节点序号本文算法文献19文献21文献22pi Sci Di排序排序排序排序1 0 2.8 0 16 9 21 162(| ) 0.5691 35.2 0.3067 1 1 3 33(| ) 0.3778

39、 22.4 0.1296 3 6 1 14 0.1353 4.8 0.0099 12 20 7 115 0 2 0 19 7 11 146(|) 0.4099 14.4 0.0904 5 4 6 77 0.1817 4.4 0.0122 9 16 15 188 0.1870 4 0.0115 10 11 18 209() 1.6 0 21 5 20 2110 0.1870 4 0.0155 10 11 16 1911 0.1984 4.4 0.0134 8 11 12 1512( ) 0.3194 11.4 0.0558 6 10 4 513 0 2.8 0 16 14 8 1014(| )

40、0.4675 28.8 0.2062 2 2 2 215 0.1194 9.6 0.0175 7 19 9 616 0 3.2 0 14 18 19 1217 0 3.2 0 14 17 14 918 0 2.8 0 16 15 10 819(| ) 0.4951 16.8 0.1274 4 3 5 420 0.1194 4.4 0.0080 13 21 13 1321 0 2 0 19 7 17 17注:本文算法确定的前5个重要节点均用“|”标注,类似地,文献19、文献21及文献22分别用“”, “”, “ ”标注.050201-8万方数据物理学报Acta Phys. Sin. Vol. 6

41、6, No. 5 (2017) 050201812 53 4789610111213141516 17 18 19 20216128816 8 4 6644446968128886 646图4加权定向后的ARPA网络Fig. 4. Directed weighted network obtained by the ARPA network.首先从表4可以看出,本文的评价算法可以避免单纯地利用交叉强度Sci指标的不足,考虑到全局因素的重要性指标Di能更好地区分节点之间的差异.比如,节点Sc7 = Sc11 = Sc20 = 4:4,以此认为它们具有相同的重要性是太过片面的.考虑到节点在全网中的相

42、对重要性pi值(p7 = 0:1817,p11 = 0:1984, p20 = 0:1194),可见v20在整个网络中的相对重要性明显小于v7和v11,因此Di指标得到v20的重要性明显小于v7和v11.另外,从表4的节点标注还可以看出,本文算法确定的前5个重要节点为v2, v14, v3, v19, v6,同时它们也属于文献19, 21, 22确定的前5个重要节点集的并集里,这符合网络的中心性评估,反映了本文算法的有效性.然而,文献19排在第5位的重要节点v9在本文算法和文献22中却排在末位,在文献21中也排在倒数第二位.从图4可以直观看出,节点v9所处的位置及连边上的权重值均不占优势,其重

43、要性相对较小.另外,文献19认为节点v8, v10, v11具有相同的重要性,而本文算法能将v11与v8, v10的重要性区别开来.经计算,删除节点v8后,网络的平均效率仅下降了0.5%,而删除节点v11后,网络的平均效率下降了4%.可以得出v11的重要性要大于v8,这与本文的评价结果相一致.因此,本文评价方法相对文献19更能细致地区分节点之间的差异.由于节点的移除会降低网络的连通性,造成的连通性越差,则对应的评价方法越好.因此,本文基于表4的评价结果,通过连续移除前5个重要节点,来对比本文与另外两种评价方法的准确性.网络的连通性可采用移除节点后的子图数目和最大子图规模两个指标来衡量,子图数目

44、越多,或最大子图所包含的节点数目越少,则说明网络连通性越差,对应的评价方法就越准确.实验结果如图5所示.由图5可以看出,在移除前5个重要节点后,文献21和文献22的评价方法均导致了6个子图,其中最大子图的节点数目均为10.而利用本文算法能够导致7个子图,其中最大子图的节点数目为7.此结果表明,无论是从子图数目,还是从最大子图规模的衡量上,本文算法的表现都要优于其他方法.因此,它在节点重要性评价上能取得良好的效果.0 5 10 15 5 21 22 $8;5 , 图5 (网刊彩色)移除前5个重要节点后ARPA网络连通性的变化Fig. 5. (color online) The connectiv

45、ity changes by re-moving the top 5 important nodes on the ARPA.4.2算法在连锁故障中的进一步验证为了验证算法的可靠性,本文对ARPA网络进行连锁故障仿真来分析网络的鲁棒性.这里鲁棒性可采用两个指标来衡量.一个是故障后的子图数目S,另一个是连锁故障前后,网络最大连通子图的规模之比G,其表达式为G = nmaxn ; (12)其中, nmax表示网络发生故障后最大连通子图的节点数目.连锁故障的过程如下:按照各方法得到的节点重要性先后顺序,依次移除网络中的重要节点.由于节点的移除影响着网络的鲁棒性21,因此可以根据不同移除方式下的网络鲁

46、棒性分析,来判050201-9万方数据物理学报Acta Phys. Sin. Vol. 66, No. 5 (2017) 050201断各评价方法的可靠性. G越小, S越大,说明网络鲁棒性越差,对应的评价方法就越可靠.本文及文献21,22对应的连锁故障仿真结果如图6所示.1 3 5 7 9 11 13 15 17 19 21G(B,52122(a)1 3 5 7 9 11 13 15 17 19 21S(B,52122(b)图6不同评价方法的连锁故障结果(a)移除节点对指标G的影响; (b)移除节点对指标S的影响Fig. 6. The results of cascading failure

47、s with dierentevaluation methods: (a) The eect of node removal onG; (b) the eect of node removal on S.从G的变化趋势可以看出,在整体水平上,随着移除节点数目的增加,本文算法能造成G更大幅度的下降.虽然在删除第2个节点时,表现暂时落后,在删除前4个节点时,三种算法的表现持平,但是在后续删除节点的过程中,本文算法对应的G值都要小于文献21, 22.特别地,当连续移除前5个节点后,本文算法对应的最大连通子图的规模比文献21, 22减少30%.此外,由S的变化趋势容易看出,本文算法对应的子图数目S上升

48、较快,数值大小相对其他方法一直领先.由以上实验结果可以得出,本文所提出的节点重要性评价方法相对更加可靠.5结论本文通过分析节点的局部重要性以及网络中所有节点之间的依赖关系,提出了一种基于多重影响力矩阵的节点重要性评价方法.将该方法应用于几个典型的有向加权网络,得出以下结论.相比其他方法,本文方法对ARPA网络节点重要性的区分更加细致.通过移除个别节点,本文方法得到的重要节点能造成网络平均效率更大程度的下降;通过连续移除前5个重要节点,计算网络连通性的变化,发现本文方法能造成更多的子图数目,以及更小的最大子图规模,这说明该方法具有一定的可靠性,其得到的重要节点能显著影响网络的连通性.进一步地,对网络进行连锁故障的仿真实验,结果表明该方法能造成G更大幅度的下降,对应的S值相对更大且上升更快,这再次验证了方法的适用性和可靠性.部分入度为0的节