一种计算机网络关键节点识别方法

刘勇

（商洛学院，陕西 商洛 726000）

近几年，计算机行业发展迅速，计算机用户逐渐增多，计算机网络日趋复杂，这给计算机网络安全带来了巨大压力。准确分析当前计算机网络结构，已然成为计算机安全领域研究的热点问题。

随着复杂性科学的快速发展，复杂网络理论在各个领域都得到了广泛应用，利用复杂网络理论对计算机网络的研究也成为计算机领域关注的热点。利用复杂网络理论不仅可以很好地展现计算机网络内部微观信息，同时也反映了其宏观特点。利用复杂网络理论可以探究计算机网络的内部拓扑结构，对熟悉和了解计算机网络都有着重要意义。

在对复杂网络研究的过程中，学者们发现网络中的少数节点往往起到关键作用[1]，它们甚至能够决定整个网络的结构和功能。例如，通过对关键节点进行完善，可以提高电网抗毁性[2]以及物联网的稳定性[3]，也可以蓄意攻击关键节点来摧毁相应的网络结构，防止传播疾病等[4]。同样，在计算机网络中，发现相似性结构[5]、识别少数关键节点状态的变化，将对当前网络结构造成巨大的影响，而如何对关键节点进行有效识别是该文要解决的核心问题。

在复杂网络关键节点识别的研究中，目前主要的方法是根据某种评估指标对网络的节点进行排序，例如度中心性[6]、接近中心性[7]等方法。但如果只使用某一种指标就显得较为单一，忽略了网络的整体特性，评价结果不够准确。为使得评价结果更加客观准确，现在学者通常采用多指标对关键节点进行识别。Wen选取网络信息量等全局指标，并结合最小二乘支持向量机（LS-SVM）给出航空网络关键节点快速识别方法[8-9]。Ren基于信息熵理论，对影响航路运行较大的节点（航路点）进行识别[10]。

该文以计算机网络中的个体为节点，个体之间能够建立通信联系，即为连边，构建计算机网络，分析网络中个体对整个网络的影响。针对计算机网络关键节点进行研究，并对其加以重点保护，可以有效遏制计算机网络病毒的传播和扩散，优化网络结构，使其具有更高的安全性和连通性。

1 计算机网络建模

计算机网络就是计算机通过互联网或者其他相应的媒介联接起来的网络结构G=(V,E)。节点V代表网络中的个体，而连边E则为联接个体之间的媒介，如图1所示。

图1 网络结构图

利用Matlab软件随机生成的一个模拟计算机网络G=(V,E)，该网络中包含24个节点，如图2所示。

图2 模拟计算机网络

对该网络的相关复杂网络指标的分析如下。各节点的节点度、点强、聚类系数、节点介数4类指标的得分情况如图3所示。

图3 各节点评价指标值

各指标从不同角度反映了节点的重要程度，但是上述指标主要从节点自身以及邻居节点属性进行分析，缺乏对网络整体性能的思考。

节点删除方法[11]是一种最典型的系统分析方法，它将节点从网络中删除后所造成的破坏程度定义为重要性，通过逆向思维避免了网络分析中由于属性和指标选择不合理而产生的一些问题。当一个节点被从网络中移除时，需要对网络性能进行评估，以便计算它造成的破坏程度[12-13]。网络整体性能的评估需要客观且全面，根据复杂网络中关键节点的现有识别方法和计算机网络的基本特征，选取网络效率、连接密度、最大连通子图和网络结构熵4个典型的整体性能指标作为评价指标体系。

1）网络效率（Network Efficient,NE）

网络效率是Latora提出的一个衡量网络信息交换性能的指标，假设网络内部信息传递的效率取决于节点对之间的最短路径长度[14]。网络效率是所有节点之间的最短路径倒数和取平均值得到的，根据以上定义，网络效率可以用公式表示为：

其中，n是当前网络节点的总数，dij为图测地线距离。它是由节点间路径距离的倒数来计算的，因此避免了非连通图中无意义的情况。此外，当考虑网络中的所有节点时，为全局效率；当取子图的效率值的平均值时，为局部效率。式中两个节点之间的距离是两节点之间的最少连边数，这也被称为测地线距离。网络效率可以反映网络信息交换的效率，NE越大，节点对之间的距离越近，计算机网络稳定性越高。

2）连接密度（Connection Density,CD）

在未加权网络中，连接密度是指网络中现有连边与可能存在的连边之间的比率。对于计算机网络，该文定义了加权连接密度，如式（2）：

当节点i和节点j之间有联接时，aij=1，否则aij=0。可以看出，CD越大，整体异构性越高，网络流量越大，网络结构越复杂。

3）最大连通子图（Largest Component,LC）

子图是网络的一部分，其中所有节点对之间有一条或多条路径。如果图是非连通的，它可以被分成两个或多个子图。在这些子图中，节点数最多的子图是最大连通子图S：

|S|是最大连通子图的大小。一般来说，最大连通子图中的节点越多，计算机网络的通联程度越高，网络整体性能越好。

4）网络结构熵（Network Structure Entropy,NS）

通常，节点重要度被表示为该节点的度与所有节点度之和的比值，如式（4）所示：

网络结构熵则用来衡量节点对计算机网络的影响程度是否均匀，是描述网络结构的宏观指标。

2 关键节点识别方法

不同的评价指标从不同角度提取节点重要度，该文将在现有的研究基础上，基于复杂网络理论，针对计算机网络特征，参考现有的节点重要度评价方法，综合考虑节点的各项性能指标，利用层析分析法（AHP）确定指标权重，并通过多属性决策的方法确定节点重要度，对计算机网络节点重要度进行排序，从中找出对网络结构影响较大的关键冲突点，为保护计算机网络安全提供对策，如图4所示。

图4 关键节点识别

根据各指标对网络整体性能的解释程度，可以给出判断矩阵：

利用AHP方法，求得评价指标权重为：

不同节点摧毁前后网络性能的变化显然是一个多属性决策问题，可由TOPSIS方法解决。

首先构造初始决策矩阵：

其中，cij为第i个节点的第j个指标的值。

由式（7）可知，第j个指标的权重为Hj(j=1,2,…,m)，∑Hj=1，因此加权矩阵:

基于TOPSIS方法，根据矩阵Y确定正理想方案A。A中的元素是Y中各列的最大值，按照A方案删除后，网络性能值下降最大：

然后计算各方案Ai到正理想方案A的距离：

Di越大，方案Ai与正理想方案A之间的距离越大，也就说明删除该节点后网络综合性能的变化越大，即对应的节点vi越重要。

计算机网络关键节点识别算法流程如图5所示，该文将节点的重要程度视为节点删除前后对网络的破坏程度，类似于计算机网络中节点破坏后对网络的影响程度。

图5 算法流程

3 仿真分析

3.1 关键节点识别

为验证方法的有效性，对模拟计算机网络进行分析。由第2节中的方法可得模拟计算机网络各节点的重要度值，并进行排序，如表1所示。

同时给出用度中心性、接近中心性和节点放缩法的节点重要度排序。此外，对表1中的关键节点（删除排名靠前的5个节点）进行攻击，攻击前后的网络结构对比如图6（a）和6（b）所示。

表1 关键节点排序

图6 关键节点删除前后网络结构对比

可以明显看出，当对关键节点进行攻击后，该网络几乎演变为两个独立的子网络。

3.2 结果分析

当根据节点删除方法、节点放缩法、接近中心性方法和度中心性方法的节点重要性排序从计算机网络中进行调配时，各评估指标的变化趋势如图7所示。

从图7中可以看出，随着关键节点在网络中逐一攻击的过程，模拟计算机网络的效率、连接密度、最大连通子图和网络结构熵持续下降。节点删除方法的曲线大部分都位于其他方法之下，即当攻击相同节点数时，节点删除方法对网络造成的影响更大。

图7 网络指标变化

为了进一步验证提出的关键节点识别方法的有效性，记录不同方法对原网络删除节点过程中的网络鲁棒性变化，如图8所示。

图8 鲁棒性分析

网络鲁棒性用于测量在移除任何节点之后保持网络中剩余节点之间的连通性能力的平均影响[15-16]。即删除任何节点后，网络中仍可联接的节点数与网络中节点总数之比的平均值。假设删除一个节点后，网络中剩余的节点集为Gk，网络鲁棒性NR的计算公式为：

从仿真结果可以看出，随着调配节点数量的增加，每种方法的整体网络性能稳步下降。然而，当根据节点删除方法进行调配时，整体性能明显下降得更快。因此，该方法能够准确识别计算机网络的关键节点。

4 结 论

基于复杂计算机网络模型，提出了一种节点删除方法来识别对网络结构影响较大的关键节点。为了验证该方法对关键节点的识别效果，将识别结果与其他方法进行比较，结果显示，提出的方法能够准确识别计算机网络中的关键节点。而识别构成计算机网络的关键节点有助于计算机网络安全保护，此外，在应急管理中，可以帮助管理人员有重点、有针对性地完成应急资源的分配，使计算机网络安全工作有条不紊地进行。