用于复杂网络节点重要度评估的离心率算法改进研究

陆年生 严广乐

摘 要：复杂网络中的节点重要度评估一直备受关注。鉴于离心率中心性只考虑节点最大最短路径存在一定局限性，通过计算处理节点的平均最短路径，考虑离心率数值与平均最短路径的差值，提出改进后的新方法。在具有代表性的APAR网络上进行计算实现，并与其它节点重要性评估方法进行对比，发现该方法较离心率中心性方法，对于节点的粗略划分更加精细、有效;在SI模型的模拟对照中，发现该方法在最终第10个单位时间时，准确性相较于离心率中心性提升了15%。

关键词：复杂网络;离心率算法;节点重要度评估;最短路径

0 引言

现实生活中的许多系统都可简化成网络的形式加以研究[1]，例如交通网络、电力网络、科研网络、交际网络等。随着复杂网络研究的兴起，节点重要性评估越来越受到国内外学者的关注。复杂网络中的节点重要度评估十分重要，通过识别并保护这些节点，可有效提高网络的鲁棒性与可靠性[2]。例如，在交通网络中，某一个交通枢纽城市因突发事件导致交通瘫痪，与该城市相邻的其它城市交通也极有可能严重受阻，使得城市间的运输途径中断继而引发大规模交通问题。研究发现，有效保护交通网络中的重要节点，可以避免其在受到外界干扰时造成航线大面积延误甚至导致网络瘫痪，保证交通运输安全高效运营[3]。

最早的节点重要性评估方法其实就是度中心性[4]，度中心性将节点连接边的数量作为节点重要性评估指标。基于度信息，Newman等[5]研究了电子邮件网络，Magoni[6]研究了英特网，Jeong等[7]研究了蛋白质网络。但是节点度仅反映节点自身信息，对于节点在网络中的位置及其对网络全局的影响并没有很好地描述。因此，Freeman[8]引入了介数的概念，介数中心性是以节点之间的最短路径为基础，计算经过每个节点的最短路径数量，但在复杂网络节点众多、结构复杂的情况下，该方法的时间复杂度较高。Per Hage等[9]提出了离心率中心性算法，将一节点距离其它所有节点的最短路径中最长的一条作为该节点重要度评估指标;Kitsak等[10]将度与节点在网络中的位置相结合，提出利用k-shell算法判断节点重要性，该方法认为ks值越大的节点越重要，但该指标存在一定缺陷，在某些特定的复杂网络中会出现多个节点ks值相同的情况;邓凯旋等[11]对k-shell算法进行了改进，利用该算法分解过程中节点被删除时的迭代层数，进一步识别节点重要性，从而提出一种新的评价指标EKsd。同样是在k-shell算法基础上，Liu等[12]考虑目标节点与ks值最大的节点集之间的最短路径，从而提出一种改进的节点重要性排序方法;周漩等[13]提出通过定义节点效率和节点重要度评价矩阵确定复杂网络中的节点重要性，利用节点度值和效率值表征其对相邻节点的重要度贡献，该方法在大型网络上表现较好;阮逸润[14]等在度和邻居节点拓扑重合度的基础上，通过获取节点二跳内的邻居信息计算节点重要性;韩忠明[15]等基于ListNet排序法并融合多个度量指标，构建了一个能够综合评价面向结构洞节点的重要节点排序方法;王雨[16]等通过分析节点的局部重要性以及网络中所有节点间的连接关系，提出一种基于多重影响力矩阵的节点重要性评估方法;汪宏[17]等基于标签传播动力学，将每个节点接收到不同标签的数量作为节点重要性评估指标。此外，孔江涛[18]等基于复杂网络动力学模型，建立偏离均值和基于偏离均值的方差兩级评估标准，进而提出了两种新的节点重要性评估方法。

综上所述，每个节点重要性排序方法都有其针对性，虽然都能在一定程度上判断出不同节点的重要性，但它们都存在一定的局限性。其中，离心率中心性方法对节点重要性识别较为准确且较容易实现，但该方法也存在不足，以节点最短路径最大值为指标时，一些中心节点会因为存在个别数值较大的最短路径而被标识为非重要节点，并且网络中会出现部分节点离心率值相同的情况而无法对节点作出精确判断。因此，只有对方法进行一定程度的改进，才能实现对节点重要度更为准确的判断。本文在最短路径基础上，对离心率中心性算法进行改进并将平均路径加入方法中，该方法将节点全局属性及网络位置考虑进去，相较于离心率方法能够更有效地对复杂网络中的节点重要度进行排序。

3 结语

节点重要度评估一直是复杂网络中的研究热点，其在实际应用中具有重要意义。本文通过改进离心率中心性算法，构建评估节点重要性的新方法re（i），该方法引入了节点的平均最短路径并对其进行了简单处理，使其在节点重要性判断中能充分利用节点的全局属性，利用差值误差提高评估结果的准确性。实际网络APAR网的研究结果发现，本文方法与其它典型节点重要性判定指标，如度中心性方法、Pagerank算法的部分结果相同或相似，侧面说明了本文方法的合理性与有效性，并且对于离心率算法判断模糊的节点也能够更好地区分开来。最后在SI模型中，两个不同节点的对照实验也证明了本文方法在重要节点的判定上，相较于离心率中心性算法准确性有所提升。由于本文方法是基于节点的全局属性，在节点局部结构较为复杂的网络中，其评估准确性可能会有所降低。后续将继续研究网络节点的局部属性并与之结合，进一步增强节点重要性评估效果。

参考文献：

[1] BARABASI A L. Scale-free networks： a decade and beyond[J]. Science， 2009， 325（5939）： 412-415.

[2] 谭跃进，吴俊，邓宏钟， 等. 复杂网络抗毁性研究综述[J]. 系统工程， 2006，24（10）： 1-5.

[3] 任卓明，邵凤，刘建国，等. 基于度与集聚系数的网络节点重要性度量方法研究[J]. 物理学报， 2013， 62（12）： 1-4.

[4] PHILLIP BONACICH. Power and centrality： a family of measures[J].  American Journal of Sociology， 1987， 92（5）：1170-1182.

[5] NEWMAN M E J， FORREST S， BALTHROP A. Email networks and the spread of computer viruses[J]. Physical Review，2002，66（3）： 035101.

[6] DAMIEN MAGONI. Tearing down the Internet[J].  IEEE Journal on Selected Areas in Communications， 2003， 21（6）： 949-960.

[7] JEONG H，MASON S，BARABASI A L. Lethality and centrality in protein networks[J]. Nature，2001， 411（6883）： 41-43.

[8] FREEMAN L. A set of measures of centrality based upon betweenness[J].  Sociometry，1977， 40（1）： 35-41.

[9] PER HAGE， FRANK HARARY. Eccentricity and centrality in networks[J]. Social Networks，1995，17（1）：57-63.

[10] KITSAK M， GAILOS L K. HAVLIN S， et al. Identification of influential spreaders in complex networks[J].  Nature Physics， 2010（6）：888-893.

[11] 邓凯旋，陈鸿昶，黄瑞阳. 一种基于改进K-shell的节点重要性排序方法[J]. 计算机应用研究， 2017， 34（10）： 3017-3019， 3084.

[12] LIU J G， REN Z M， GUO Q. Ranking the spreading influence in complex networks[J].  Physica A， 2013， 392（18）：4154-4159.

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

[14] 阮逸润，老松杨，王竣德，等. 基于领域相似度的复杂网络节点重要度评估算法[J]. 物理学报， 2017， 66（3）： 1-8.

[15] 韩忠明，吴杨，谭旭升，等. 面向结构洞的复杂网络关键节点排序[J].  物理学报，2015， 64（5）： 1-8.

[16] 王雨， 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法[J]. 物理学报，2017， 66（5）： 1-11.

[17] 汪宏，鲍中奎，张海峰. 基于标签传播识别网络中的关键节点[J].  复杂系统与复杂性科学，2017，14（2）： 19-25.

[18] 孔江涛，黄健，龚建兴，等. 基于复杂网络动力学模型的无向加权网络节点重要性评估[J]. 物理学报， 2018， 67（9）： 1-16.

[19] 马睿，朱建冲，杨美玲. 基于抗毁性的军事通信网可靠性和节点重要性分析[J]. 兵工自动化，2012， 31（10）： 46-47.

[20] 张翼，刘玉华，许凯华，等. 一种基于互信息的复杂网络节点重要性评估方法[J].  计算机科学，2011，38（6）：88-89，109.

（责任编辑：孙 娟）