网络节点重要度的快速评估方法探索

□布英塔

一、领域研究的背景

对于网络节点重要度的快速评估的问题上，国内外大量专家学者做了大量的研究。分析社会网络时，认为节点的重要性与目标节点和剩余节点的连接而具有的显著性是可以等同认知的。随后又有学者提出研究网络核度与节点数、边数的关系的核度测量方法。之后的研究综合了多方面的因素，包括介数、节点度、邻接节点度数等，加权求得节点的重要度评估。当前关于复杂网络节点重要度的研究，还是集中在特定结构网络中重要性指标的选取上;在节点重要性内涵以及重要性影响因素等方面还没有形成一致的认知;而且对节点重要度的指标的信度测量方面的研究相对较少。

二、相关概念和理论

(一)复杂网络节点重要性分析与表示。网络是节点与节点相互连接形成的，所以节点也是网络的核心元素。节点的重要性主要体现在节点在网络中的所处的位置和连接方式体现。目前，对网络节点重要性的测度指标主要包括节点局部连接属性测度和节点全局位置属性测度。

(二)节点度。假设G = {V，L}，是一个无向连通的网络，V 代表网络中所有节点的集合;L 代表该网络中链接所有节点的边的集合，同时满足。节点度是指和该节点相关联的边的数量，记作k。其中节点的入度是指进入该节点的边的数量;节点的出度是指从该节点出发的边的数量。节点的度值能够直接反映节点的重要度的观点得到了广泛的认知，而且存在一定的规律:节点的度值越高，说明该店的重要程度越高。

(三)节点介数。节点介数是指网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例。主要用来描述网络节点重要性程度，可以给出网络之中通过某一节点的最短路径。目前，研究表明，节点的介数越大，其影响力和重要程度就会越大。

(四)阶邻居节点。邻居节点是相对于传输距离或传输跳数而言的，在一定范围内的就可以称之为邻居节点。一个复杂的网络，例如G={V，L}，对于其中的任意一个节点，它的1 阶邻居节点是与该节点距离为1 的节点，此类节点的集合就是1 阶邻居节点的集合。同理可以类推，与该节点距离为m 的节点称为m 阶邻居节点。

(五)最短路径。最短路径主要是用来计算一个节点到其他所有节点的距离中最近的路径。通常情况下，采用Dijkstra 算法算出最短路径的最优解，但是因为它计算的节点比较多，效率偏低。

(六)节点对数目。节点对数目是指删除任意节点后，网络中该节点的邻居节点集合中能保持连通的节点对数。依据在网络中节点和边的关系，此数值为正整数。当其数值比较大时，说明删除该节点后网络的连通性能依旧保持良好，则可以说明该节点自己本身的重要性很小。其主要反映了节点的局部联通情况，可以用来描述网络节点的重要性。

三、评估方法简述

(一)节点重要度评估方法。从另一个领域，空间自相关的方向上来讲，两个对象之间的距离越接近，其之间的依赖就会越强。所以可以认为:距离目标节点越近的节点对目标节点重要性的贡献就会越大。现在既有的研究发现，存在很大一部分的复杂系统的一些特性会随着距离的增加表现出衰减的趋势，基本上符合指数衰减的规律。本文也假设在节点的重要度评估过程中，其邻居节点的重要度贡献随距离的增加出现指数递减的走向。当只考虑节点单一性质对重要性的影响时，对于任意节点，引入相应的虫药都测评函数。所用的评价函数要综合考虑到节点本身和它的从1 到m 阶的邻居节点的重要度贡献，此外，距离节点越远，其重要度就会越小。一般来说，现实生活中评估目标的重要性时，基本上都会综合全方面的影响。但是，网络节点的重要性并不完完全全取决于节点的度、介数等特性指标，在涵盖这些因素后做出的重要程度评估才更为精准，据此可以定义重要度评价模型。模型要包括用来表示节点以及各阶邻居节点对目标节点重要性贡献程度的评估系数矩阵，包含节点和各阶邻居节点指标值的评估指标矩阵，以及权重矩阵。

(二)算法流程概述。考虑目标节点以及m 阶邻居节点对目标节点对节点的重要度贡献，才会得到较为准确的评价结果。评估最关键的是意识到目标节点的度值等相关信息对评估的重要性，度值甚至可以表现节点的重要性。所以，在已知网络，目标节点的邻居节点深度，评估的指标集和权重矩阵，采用了下面的算法:一是根据网络的结构关系，提取出节点的各阶邻居节点集。二是计算目标节点的邻居节点集的指标数值，然后确定目标节点的评估指标矩阵。三是根据评估指标矩阵中每一类指标做出归一化的处理，计算归一化处理后的评估指标矩阵。四是根据选取的公式，计算各个节点的重要度。

(三)评估算法的分析。节点重要度评估方法，评估指标以及另据节点的深度都是影响评价结果的重要因素。展开来说，如果邻居节点深度值太小，会出现过分依赖节点本身属性的评价过程，导致忽略网络位置信息对节点的影响，结果将会与传统连接度的方法没有太大差别。相反，取值太大的话，不仅会增加算法复杂程度，还会造成负面的影响。在评价指标的选择问题上，反映节点重要性最主要的两个参数分别为:节点的度和节点介数，本文也是以这两个参数为评价指标建立的整个评价模型。

(四)评价结果和模型分析讨论。经过详细的分析验证，基于度的评价结果和模型的角度，按节点的度值大小排列，也反映了节点的重要性。提出方案综合考虑了节点在网络中的整体和局部的重要性，目标节点和各阶邻居节点对节点的重要度贡献，方法具有较高的评估精度，做到了区分各节点的重要度差别。基于度和介数的评估结果和模型的角度，节点介数给出了网络中通过某节点的最短路径，体现了节点连通性能的聚集度。评估算法做到了有效评估网络节点重要度，同时精确提取关键节点的地步。

四、结语

在现实世界中，网络形式的系统无处不在，从因特网、社会网络到客户关系网络等，诸多的网络环境，能够尽可能地保证网络的稳定性和可靠性，对我们的生活带了颇多的益处。例如，当网络中有多个节点同时发生故障时，需要考虑如何确定维修的先后顺序，使网络遭受的损失最小;因此，本文从基本理论和评估方法的现状对快速评估网络节点重要度提出了自己的看法，希望对提高复杂网络中节点的可靠性和重要度有所帮助，也希望从业人员之间相互学习，共同成长。

［1］李海舰，董宏辉，张鹏飞．一种适用于道路交通的传感器网络节点语义编码设计［J］．中南大学学报(自然科学版)，2013，6

［2］董立珉，刘源，徐国栋．卫星系统网络节点的智能化设计［J］．光学精密工程，2013，4

［3］黄新波，罗兵，刘存孝．采用ZigBee 芯片的无线加速度传感器网络节点的实现［J］．高电压技术，2010，8

［4］韦相和，印杰，李千目．天地一体化网络节点的移动认证协议设计［J］．南京理工大学学报(自然科学版)，2010，4

［5］肖卫东，谭文堂，葛斌．网络节点重要度的快速评估方法［J］．系统工程理论与实践，2013，7