复杂网络中节点重要度的一个评估指标

蒋丰景，陈玥琪

(西安电子科技大学理学院，陕西西安710071)

复杂网络中节点重要度的一个评估指标

蒋丰景，陈玥琪

(西安电子科技大学理学院，陕西西安710071)

为了简单而有效地评估网络拓扑结构中各节点重要性，本文基于节点的连接度和局部连通性，定义了一个节点重要度函数.该重要度函数指标实质上与网络中的平均最短距离指标是一致的，通过该重要度函数指标值的大小可以得到网络中各节点的重要度排序.理论分析与实例表明，对于小型网络，该方法的计算比较简单，且直观、有效、合理.

节点重要度;邻居节点;节点删除;平均最短距离

随着信息技术飞速发展，互联网已成为社会舆论传播的主要载体之一，无论是现实生活还是系统科学，都与网络密切相关.特别是很多实际网络所抽象出来的复杂网络，表现出了与以往网络理论不同的特性［1］，如小世界特性、无尺度特性等.如何在复杂网络环境下，保证网络的可靠性和抗毁性［2］成为复杂网络研究的重要课题.研究表明，在选择性打击下，即优先攻击网络中“核心节点”，无标度网络异常脆弱，网络基本处于瘫痪状态.因此，找出网络中的“核心节点”并将它们保护起来对维持整个网络的可靠性具有重要作用;同时，“核心节点”的保障和维护对实现网络信息流通和降低网络信息交换成本，提高信息流通效率有重要意义.网络节点的重要度指标的度量方法有节点的度、接近度、介数、信息、特征向量和累计提名等.其中最简单的方法是以节点的度作为节点重要性的衡量标准，认为节点的度越大则该节点越重要，但一个节点的度仅仅描述了该节点对于其他节点的直接影响力，因此有很大的片面性;文献［3］提出了一种基于生成树数目的节点删除法，如果多个节点的删除都使得网络不连通，那么这些节点的重要度将是一致的，从而使得评估不精确;文献［4］提出的介数能很好地衡量节点重要度，但计算节点的介数非常复杂，不仅要计算各个节点对之间的最短路径长度，还要记录这些最短路径的路线.

本文利用网络的连通性来反映系统某种功能的完整性，通过度量节点删除对网络连通的破坏程度来反映网络节点(集)的重要性，即“破坏性等价于重要性”.从这种思想出发构造了一个和平均最短路径指标具有等价性的节点重要度函数指标I(vi)，利用该函数可以有效地判定网络中各节点重要程度的大小，并且无需复杂的计算，实例计算也验证了该方法的合理性.

1 节点重要度评估模型

本文所研究的复杂网络均为无向、无权、无重边网络，用图G=(V，E)表示，其中V={v1，v2，…，vn}表示网络G中节点的集合，E={e1，e2，…，em}为G中边的集合.

定义1节点vi的度是指与它相关联的边的条数，记为ki.

定义2节点vi的邻居节点是指与vi直接有边相连的那些节点，这些节点的集合构成vi的邻居节点集.

定义3把vi和vj之间跳数最少的路径称为它们的最短路径，显然，vi和vj之间的最短路径可能不止一条.

定义5定义li为删除节点vi后，网络中vi的邻居节点集中保持连通的节点对数目.根据网络中节点与边的关系，有li为介于0与ki(ki-1)/2的正整数.当li比较大时，表明删除节点vi后，网络的连通性仍然很好，即节点vi自身的重要性相对比较小，这个指标可以有效地反映节点的局部连通情况，因此可以用它来考虑网络中节点的重要性.

定义6称I(vi)=［ki(ki-1)］/［2(li+1)］为节点vi的重要度函数，考虑到叶子节点的li为0的情况，定义分母为li+1.该指标从节点自身的连接度和节点的局部连通性考虑了节点的重要性.同等条件下，连接度越大的节点收缩以后，网络中节点和边的数目就越少，因此该节点相对越重要.而处于关键位置的节点重要度也相对而言比较高，因为很多节点对之间的最短路径都要经过该节点，该节点收缩后将减少网络的平均最短距离，因此该节点比较重要.

2 节点重要性指标

网络节点之间进行通信的路径首选最短路径，如果某个节点被许多最短路径经过，则表明该节点在整个网络中的作用和影响力是比较大的.因此，把网络中平均最短路径作为节点重要性指标是比较合理的，但是它的计算式比较复杂，因为不仅要计算出每个节点对之间的最短路径长度，并且还要记录这些最短路径.下面分析说明本文定义的节点重要度函数指标与网络中平均最短路径指标具有一致性，只是放大的显著性程度有所差别.

当节点vi被删除或者收缩后网络中平均最短路径变化情况如下：

如果节点vi不在最短路径上，则一部分节点的最短路径不经过vi.因此，当节点vi被删除或者收缩后对这些节点的最短路径无影响，从而对整个网络的平均最短路径也没有影响.如果节点间的最短路径经过vi，则删除节点vi后这些节点间的最短路径将会发生变化.假设被删除节点的li比较小，即节点vi的邻居节点的连通性比较差，则最短路径中经过vi的邻居节点的概率比较小.相对而言，经过vi的最短路径的概率就比较大，这与li减小，I(vi)增大是一致的.因此，节点的I(vi)越大，表明删除节点vi后，通过vi的最大路径变大，从而网络的平均最短路径变大.也就是，节点vi的I(vi)越大，删除vi后网络的平均最短距离变大.因此，本文定义的节点重要度函数指标与网络中平均最短路径指标具有一致性.

3 实例分析

设某网络的拓扑结构如图1，用文献［3］与文献［5］得到节点4与节点6的重要度是一样的，使用本文的方法有：节点4的度k4=4，l4为删除节点4后，节点4的邻居节点中保持连通的节点对数目，显然l4=1，因此I(v4)=3.同样很容易计算l(v6)=6.因此节点4的重要性程度比节点6要小.从直观上也可以发现，当删除节点4，节点1，2，3的连通性比删除节点6后节点7，8，9的连通性要好，因此，节点4的重要性比节点6的重要性要小.

由表1知，本文使用节点重要度函数指标得到的节点重要度排序结果与文献［7］中的方法得到的节点重要度排序结果是一致的，并且与实际结果是一致的.但是对于小型网络，本文中计算节点重要度的方法更为简单.此外，若通过文献［3］的方法，即考虑删除节点后网络的生成树变化数目的变化情况，则节点4～7的重要度是一样的.然而从直观上看，网络中这几个节点的重要度是有差别的.因此本文的方法是合理有效的.

表1 节点重要度评估结果

图1 含有9个节点的网络拓扑图

图2 网络拓扑结构

4 结束语

评估网络中的节点重要性一直是社会网络分析领域和系统科学研究领域的一个热点，本文基于“破坏性等价于重要性”这一思想，构造了一个节点重要度函数，从而使这一思想得到了精细的量化.对于小型网络，该方法避免了复杂的计算，实例分析也验证了该方法的合理性、有效性和优越性.

［1］汪小帆，李翔，陈光荣.复杂网络理论及其应用［M］.北京：清华大学出版社，2006.

［2］饶育萍.林竞焉，月东方.网络抗毁度和节点重要性评价方法［J］.计算机工程，2009，35(6)：14-16.

［3］陈勇，胡爱群.通信网络中最重要节点确定方法［J］.高技术通讯，2004(1)：573-575.

［4］FREEMAN L C.A set of measures of centrality based upon betweenness［J］.Sociometry，1977，40(1)：35-41.

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

［6］陈勇，胡爱群，胡啸.通信网中节点重要性的评价方法［J］.通信学报，2004，25(8)：129-134.

［7］陈静，孙林夫.复杂网络中节点重要度评估［J］.西南交通大学学报，2009，44(3)：426-429.

［8］孙睿，罗万伯.网络舆论中节点重要性评估方案综述［J］.计算机应用研究，2012，29(10)：3 606-3 608.

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

［9］李鹏翔，任玉晴，席酉民.网络节点(集)重要性的一种度量指标［J］.系统工程，2004，22(4)：13-20.

An evaluation index of node importance in complex networks

JIANG Feng-jing，CHEN Yue-qi

(College of Science，Xidian University，Xi'an 710071，China)

To simply and effectively evaluate the importance of each node in network topology structure，a node importance function based on the node connectivity degree and local connectivity is defined.The index of the node importance function is substantially consistent with the index of the average shortest path in networks，the importance of each node in the network can be sorted by the size of the index value.For small networks，it is relatively simple in calculation，the method is vertified more intuitive，effective and reasonable by theoretical analysis and practical examples.

node importance;neighbor node;node removal;average shortest distance

C 934

A

1674-649X(2014)01-0140-03

编辑：：武晖;校对：孟超

2013-04-15

蒋丰景(1989-)，男，江苏省淮安市人，西安电子科技大学硕士研究生.E-mail：727729909@qq.com