张惠玲, 张　蒙

(西安航空学院 理学院， 陕西 西安 710077)

网络节点重要性的多指标综合评价方法

张惠玲, 张蒙

(西安航空学院 理学院， 陕西 西安 710077)

摘要:给出了网络节点重要性的一种多指标综合评价方法。从网络的备选路由数、网络被分割的程度和网络性能三方面考虑节点的重要性，分别引入“改进的生成树数目”、“改进的网络连通性”和“改进的剩余节点对距离和的增量”三个指标，并根据变异系数法，确定其权重，以其线性加权值作为节点重要性的测度。最后，利用该方法对一个无向图的节点重要性进行分析，并与节点删除法进行比较，该方法可行有效。

关键词:网络；节点重要性；变异系数法

网络节点重要性分析方法主要有两大类。社会网络分析方法通常不破坏网络的连通性，通过分析网络节点的一些静态属性，如度、中心度、介数等，来判断节点的重要性，即“显著性等价于重要性”。系统科学分析方法通常破坏网络的连通性，通过删除网络中的节点，给出一些度量网络破坏程度的指标来反映节点的重要性，即“破坏性等价于重要性”[1]。研究通信网络的抗毁性能，就必须评价节点的重要程度，为确定通信网络节点被移除的顺序提供参考。

通过删除节点，可以比较网络性能变化，进而确定网络节点的重要性。删除节点后生成树数目的多少反映了通信网络中任意两节点的相对重要性[2]。定义网络的连通性指标，可以讨论移除节点导致网络被分割的情况[3]。基于“逼近理想排序法”的多属性决策方法，可以权衡影响节点重要性的多种因素，以确定节点的重要程度[4]。利用基于最短路径介数的方法，也可确定网络中的重要性节点[5]。利用节点收缩的方法，通过删除待分析节点的邻接点来判断节点的重要度，能够简化计算复杂度[6]，但容易忽略节点删除后所导致的网络结构变化，从而引起节点重要性的变化。定义相关指标，利用线性运算将指标结合起来，即可定义节点的重要性[7]。将节点的度平均分配到各个相邻节点后，又结合介数构造重要度评价矩阵，由此可以给出节点重要度评价方法[8]。在若节点被删除后网络仍然是连通的情况下，定义“剩余节点对最短距离和增量”指标，可以给出网络节点的相对重要性[9]。

单一指标的提出一般都只是针对网络的某种性能，难以整体上有效评价网络节点的重要性。网络中节点的重要程度需要从不同的角度来考虑，利用节点的多个重要性指标来进行综合评价。多指标综合评价方法是将所选择的有代表性的若干指标综合成一个指数[10]，从而对网络节点的重要性做出综合评价。此过程需要解决两个问题，一是指标的归一化，二是综合时权重的确定。尤其对于指标权重的确定，仅凭主观因素是缺乏科学性的，不具说服力。

本文拟从网络的备选路由数、网络被分割的程度和网络性能三方面考虑节点的重要性，分别引入“改进的生成树数目”、“改进的网络连通性”和“改进的剩余节点对距离和的增量”三个指标，然后将它们归一化，再利用变异系数法，给出三个指标相应的权重，从而得出一种判断网络节点重要性的方法，以求更加合理地反映删除节点对网络性能的影响。

1评价指标的归一化

1.1生成树数目指标

生成树的数目可以作为评价节点重要性的一个指标[2]。为了与其他指标进行综合，将其归一化。确定图G中节点vi的重要性指标为

其中G-vi表示去掉节点vi以及与其相连的边之后得到的子图，τ(G)表示图G的生成树数目。

1.2改进的网络连通性指标

为表示删除节点vi后，网络中不连通的节点对数目，可设

则删除vi后网络中不连通的节点对数目为

它越大，节点vi越重要。对此指标归一化，得

1.3改进的剩余节点对最短距离和增量指标

设节点vi被删除前后,节点vj和vk之间的最短距离分别为Djk和dij,则节点vi未被删除前,原网络中除节点vi外所有节点对之间的最短距离之和

节点vi被删除后,网络中剩余节点对之间的最短距离之和

节点vi被删除前后，除去节点vi剩余节点对最短距离和的增量

δi=SG-vi-SG(vi)。

此增量越大，表明节点vi越重要。对此指标归一化，得

该指标考虑的是节点被删除后网络仍然连通的情形，若节点vi被删除后网络不连通，可直接令

Δi=1。

2变异系数法与指标权重

2.1变异系数法

在评价体系中，指标取值的变异系数越大，说明该指标的个体取值差异越大，所含的信息量越大。越能反映被评价个体差距的指标，越应该予以重视，越应给予较大的权重。变异系数越小，指标所含的信息量越小，指标反映的个体差异越小，权重应该越小。

设σj是第j项指标的标准差，μj是第j项指标的平均数。定义标准差与平均数的比值为变异系数，即第j项指标的变异系数

于是第j项指标的权重为

2.2综合指标

考虑“改进的生成树数目指标”Ti，“改进的网络连通性指标”Li，“改进的剩余节点对最短距离和增量指标”Δi三个指标,可得节点vi的重要性评价综合指标为

Mi=W1Ti+W2Li+W3Δi。

3分析验证

将综合指标分别应用于评价简单网络和复杂网络，并与已有算法的评价结果进行比较。

3.1简单网络

针对如图1所示的简单网络，分别去掉节点vi(i=1,2,…,7)后，相应的各指标值如表1所示。

图1　简单网络

去掉节点指标Ti指标Li指标Δiv10.666700v20.666700v310.88891v4111v510.88891v60.666700v70.666700

根据表1中的数据，分别计算各指标的平均数μj和标准差σj(j=1,2,3),可得

μ1=0.396 8,σ1=0.496 3,

μ2=0.428 6,σ2=0.534 5,

μ3=0.809 5,σ3=0.178 2。

变异系数分别为

各项指标所占权重分别为

节点vi的重要性综合指标，及其与生成树法[2]和节点收缩法[11]所确定的节点重要性对比结果如表2所示。

表2　节点重要性评价结果及比较

三种算法得出的节点重要性排序略有差异。依据综合指标法，最重要的节点是v4,而v3和v5次之，v1,v2,v6,v7序后。与另两种方法相比，可以区别出节点v4比v3和v5更重要。造成这种差异的原因在于，生成树法删去节点v3或v4均导致剩余节点构成的网络图的生成树为0。另外，在按节点收缩法所得结果中，节点v4的重要性被排在节点v3和v5之后，显然跟实际不符。

3.2复杂网络

针对如图2所示复杂网络中各节点的重要性进行分析。这是一个ARPA网络拓扑，是分析网络节点重要性时普遍使用的网络拓扑。该网络由21个节点和23条边组成，大部分节点的度为2。

图2　ARPA网络拓扑

分别利用综合指标法、生成树法[2]和节点收缩法[11]进行分析，所得节点重要性排序结果如表3所示。

表3　ARPA网的节点重要性评价结果

生成树法考虑的是移除节点后生成树的数目变化，而节点收缩法考虑的是节点收缩后网络路径和顶点数的变化。根据生成树法，v7～v11这5个节点被认为重要性一致，没有区别，而根据综合指标法，这5个节点的重要性是有区别的，这与依据节点收缩法所得结果一致，更为精确。不同的时，依据节点收缩法，最重要节点是v6，而依据综合指标法，最重要节点是v3，这又与依据生成树法所得出的结果一致。

4结语

引入节点的“改进的生成树数目”、“改进的网络连通性”和“改进的剩余节点对最短距离和增量”三个指标，借助变异系数法确定其权重，利用综合指法分析节点在网络中的重要程度。就简单网络和ARPA复杂网络所进行的计算显示，这种分析方法是有效的，且能克服单一指标判断节点重要性的不足。

参考文献

[1]周漩，张凤鸣，李克武，等.利用重要度评价矩阵确定复杂网络关键节点[J]. 物理学报，2012，61(5)：1-7.

[2]陈勇，胡爱群，胡啸，等. 通信网中节点重要性的评价方法[J]. 通信学报，2004， 25(8)：129-131.

[3]余新，李艳和，郑小平，等. 基于网络性能变化梯度的通信网络节点重要程度评价方法[J]. 清华大学学报：自然科学版.2008，48(4)：541-544.

[4]于会，刘尊，李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法[J]. 物理学报，2013，62(2)：1-9.

[5]张珍，张振宇，宋蔓蔓. 一种基于最短路径介数的重要节点发现算法[J].计算机工程与应用，2013，49(21)98-100.

[6]谭跃进，吴俊，邓宏钟. 复杂网络中节点重要度评估的节点收缩方法[J]. 系统工程理论与实践，2006，26(11)：79-83.

[7]叶春森，汪传雷，刘宏伟. 网络节点重要度评价方法研究[J]. 统计与决策，2010，301(1)：22-24.

[8]赵毅寰，王祖林，郑晶，等. 利用重要性贡献矩阵确定通信网中最重要节点[J].北京航空航天大学学报，2009，35(9)：1076-1079.

[9]李琳，刘雅奇. 通信网节点重要性的多指标评价方法[J]. 海军工程大学学报，2010，22(5)：69-73.

[10] 钟霞，钟怀军. 多指标综合评价方法及其应用[J].内蒙古大学学报：人文社会科学版，2004，36(4)：107-111.

[11]WUJ,TANYJ.Findingthemostvitalnodebynodeconstractionincommunicationnetworks[C]//IEEEInternationalConferenceonCommunications.Changsha:IEEEPress, 2005:1283-1286.

[责任编辑:瑞金]

Multi-indexcomprehensiveevaluationmethodonnetworknodeimportance

ZHANGHuiling,ZHANGMeng

(SchoolofScience,Xi’anAerotechnicalUniversity,Xi’an710077,China)

Abstract:A multi-index comprehensive evaluation method for the importance of network nodes is proposed. The node importance is considered according to the three aspects of network: alternate routing number, the partition of the network degree and network performance. Three indexes, which are the number of spanning tree improved, improved network connectivity, and the increase of the sum of the distance improved between certain nodes, are introduced, and their weights are determined through the variation coefficient method. Then their linear weighted value is regarded as a measure of the importance of nodes. Finally, this method is used to analyze the importance of the nodes in an undirected graph, and compared to Node deletion method. Results show that this method is feasible and effective.

Keywords:network, node importance, variation coefficient method

doi:10.13682/j.issn.2095-6533.2016.01.007

收稿日期：2015-04-20

基金项目：国家自然科学基金资助项目(11171271)

作者简介：张惠玲(1979-)，女，博士，副教授，从事复杂网络研究。E-mail: huilingzhang0915@163.com 张蒙(1981-)，男，硕士，讲师，从事博弈论研究。 E-mail: 24042807@qq.com

中图分类号：TN915

文献标识码：A

文章编号：2095-6533(2016)01-0038-04