基于聚类的关键节点识别

朱瑾　俞璐

摘  要： 网络对抗是现代战争的关键因素，对抗手段主要是攻击节点，攻击关键节点能够用最少的资源最大程度地破坏敌方通信系统。现有研究大多通过挖掘节点在网络拓扑中的地位来分析节点的重要程度。这种方法往往计算复杂，不适用于大规模网络。提出通过聚类算法进行关键节点识别，对节点进行密度峰值聚类，得到以局部密度和与更高密度点的距离为坐标的决策图，将决策图中各节点间的距离作为权值矩阵进行谱聚类得到网络的关键节点。

关键词： 跳频通信; 密度峰值聚类; 谱聚类; 关键节点识别

中图分类号：TP3-0          文献标识码：A    文章编号：1006-8228（2022）04-05-04

Key node identification based on clustering

Zhu Jin Yu Lu

（College of Communication Engineering， Army Engineering University of PLA， Nanjing， Jiangsu 210000， China）

Abstract： Network confrontation is the key factor of modern war. The main means of confrontation is attack node. Attacking critical nodes can maximize the destruction of enemy's communication systems with minimal resources. Most of the existing researches have analyzed the importance of nodes by mining their status in the network topology. This method is often computationally complex and is not suitable for large-scale networks. In this paper， a clustering algorithm is proposed to identify key nodes. By clustering nodes with density peaks， a decision graph with local density and distance from higher density points as coordinates is obtained. The key nodes of the network are obtained by spectral clustering using the distance between each node in the decision graph as a weight matrix.

Key words： frequency-hopping communication; peak density clustering; sspectral clustering; identification of key nodes

0 引言

當今无线通信技术快速发展，无线通信设备多种多样。其用在现代战争中，无线通信设备间的相互通信会产生数量庞大、种类繁多、不断变化的信号，增加了电磁环境的复杂性，将阻碍作战过程的顺利进行[1]。

作战过程中，我方不但希望扰乱敌方作战计划，掌握战场主动权，还希望通过最少的攻击资源，迅速且精准地破坏敌方通信网络。要想实现该目标，识别战场通信网络中的关键节点显得十分重要。倘若可以发现敌方通信网络的关键节点，便能集中力量攻击其关键节点，不但可以避免人力物力的不必要消耗，还可以严重打击到敌方。

文献[2]给出基于几点间最短路径的网络连通性的定义，结合节点删除法，计算节点删除后对网络连通性造成的影响大小，从而判断该节点在整个网络拓扑中的重要程度。但是该方法没有考虑到节点删除后的网络可能变得不再连通，在网络不连通的情况下，节点删除法往往无法判定节点的关键程度。文献[3]计算网络中与节点直接相连的节点的个数，将其作为判断该节点关键性程度的指标。该方法是衡量节点重要程度最直观简单的方法，但是这种评估方法比较片面，有些节点虽然没有很多邻接节点，但是却处于核心地位，例如连接两个子网络的节点。文献[4]给出网络凝聚度和节点收缩的概念，将节点收缩后网络凝聚度的变化作为衡量节点重要度的指标，节点收缩后网络凝聚度越高节点重要度越大。但是，如果有多个节点在节点收缩后的网络拓扑都是相同的，那么将很难区分这些节点的重要程度。

针对以上问题，本文提出一种基于聚类的通信网络关键节点识别方法，求得的聚类中心即为通信网络拓扑的关键节点。本文的方法不需要删除或者收缩节点导致网络拓扑结构发生变化，也不会只是片面地根据单个指标确定节点的关键程度。本文基于密度峰值聚类和谱聚类，结合节点的聚类系数和边的权重，能够高效地解决大型网络的关键节点识别问题。

1 理论基础

假设将网络抽象为G（V，E），V表示网络中所有节点的集合，记为V={v₁，v₂，...，v_n}，其中，n表示节点的个数，E表示节点间所有边的集合，记为E={e₁，e₂，...，e_m}，其中，m表示边的个数。根据连接节点的边是否具有方向性，网络被分为无向网络和有向网络，如图1和图2所示。7EE6135F-5969-4040-B423-C71BAC5849A2

目前，衡量网络节点重要程度的指标有很多，大体可以分为两种方法：第一种方法无需改变网络的拓扑结构，通过节点在网络拓扑中的显著性反映节点的重要程度，例如度、距离、介数、聚类系数、特征向量法等;第二种方法需要改变网络拓扑结构，通过节点失效后对网络连通性影响的大小来反映节点的重要程度，例如节点删除法、节点收缩法等。本文利用聚类系数对通信网络关键节点进行识别。

聚类系数是衡量一个网络中节点聚集程度的指标。假设一个网络中共有N个节点，节点i有k_i个直接相连的邻居节点，这些相邻节点之间最多可以有k_i（k_i-1）/2条边，也就是任意两个点之间都有边且仅有一条边。将节点i的聚类系数表示为c_i，则

其中，n_i为与节点i直接相连的节点之间实际存在边的数目。

将该网络节点的平均聚类系数表示为c，则

2 通信网络拓扑关键节点发现

2.1 条件假设

由于现实环境过于复杂，很难达到，为了使研究更具有针对性，本文做出如下假设。

假设1：电台间的通信方式为跳频通信。

假设2：电台采用停止等待ARQ协议进行通信。

假设3：跳频通信过程中，发送方发送数据帧和接收方回复ACK均在一次跳频周期内完成。

假设4：信号在传播过程中不受任何障碍物的影响，沿直线传播。

假设5：在频谱监测过程中，监测站和电台的位置都不发生变化。

2.2 数据预处理

设频谱监测数据集为X={x₁，x₂，...，x_i，...，v_n}，其中x_i={roll_i，T_roll，t_i，f_i，b_i，p_i}，其中，roll_i表示轮询次数，T_roll表示轮询周期，t_i表示以0s为开始扫描时间，轮询到第i次的时间，f_i表示第i次轮询周期内信号的中心频率，b_i表示第i次轮询周期内信号的带宽，p_i表示第i次轮询周期内信号的功率。

按照频率对频谱监测数据集X进行聚类得到聚类集Y={y₁，y₂，...，y_i，...，y_ny}，n_y表示聚类簇的个数。对聚类簇y_i中频谱监测数据的当前时间进行升序排序，得到yt_i={yt₁，yt₂，...，yt_nyt}，其中n_yt为聚类簇y_i中频谱监测数据的个数，则yi的跳频周期T_i=yt_nyt-yt₁。根据功率p对聚类簇y_i进行聚类得到聚类集Z={z₁，z₂，...，z_j，...，z_nz}，n_z表示聚类簇的个数。计算z_j的中心频点F_j、平均功率P_j、平均带宽B_j、信号开始时间t_beginj、信号结束时间t_endj。

根据以上分析，可以得到预处理后的频谱数据集D={d₁，d₂，...，d_i，...，d_n}，其中，d_i={F_i，B_i，P_i，T_i，t_begini，t_endi}，n为频谱数据个数。

2.3 通信网络关键节点识别

本文是对电台通信网络进行关键节点识别，用G（V，E）表示电台通信网络，将电台当作网络的节点，用V={v₁，v₂，...，v_i，...，v_n}，v_i={P_i，T_i}表示网络的节点集，其中，n为电台数目即节点数目，将电台间的通联关系抽象为网络的边，用E={e₁，e₂，...，e_m}表示网络的边集，其中，m为通联关系数目即边数目。

本文通过密度峰值聚類[5]和谱聚类[6]对通信网络拓扑进行关键节点识别。在进行密度峰值聚类时，需要确定节点的局部密度和与更高密度点的距离这两个特征，从而对聚类中心进行刻画。密度峰值聚类是将和节点i之间的距离小于截断距离的节点个数作为该节点的局部密度。这种方法虽然能够很好的体现出节点的密集程度，但是节点的密集程度大不代表节点在网络拓扑中处于关键的地位。倘若节点很密集，而相互之间却并没有直接的联系，也就是节点间没有相连接的边，那么当该节点因为遭到攻击而失效时，几乎不会影响到周围的节点。因此，在识别关键节点时不但要考虑节点的密集程度，还要考虑节点间的边，节点间的边主要包括节点间是否相连接和边的权重这两个特征。

从公式⑴可以看出，聚类系数是计算节点i的邻居节点之间真实存在的边的数目占可能存在的边的数目的比例，能够很好地反映出边连接的紧密程度。节点的密集程度越大，相当于周围节点离该节点的距离都比较近，因此，将节点间的距离作为边的权重。本文将对聚类系数进行改进，将聚类系数和边的权重相结合，从而更好地描述各节点的局部密度。7EE6135F-5969-4040-B423-C71BAC5849A2

2.3.1 改進的聚类系数

为了更好地描述节点的局部密度，本文对聚类系数进行改进，将聚类系数和节点间边的权重相结合，将这种加权聚类系数作为节点的局部密度。

节点i的局部密度记为w_i，则

其中，n为网络拓扑中节点总数，s和t都表示网络拓扑中的节点，d_st表示节点i的邻居节点间存在边的节点s和节点t之间的距离，[Dpq]表示节点i邻居节点中任意两个节点s和节点t之间的距离。

聚类系数是计算节点i邻居节点之间真实的边数目占所有可能的边数目的比例，本文提出的改进的聚类系数是将这些边的权重添加进去，计算节点i的邻居节点之间真实的边权重和占所有可能的边的权重和的比例，从而更好地描述节点的局部密度。

2.3.2 基于聚类的关键节点识别

根据公式⑶计算得到各节点的加权聚类系数，将其作为局部密度对节点进行密度峰值聚类，从而得到以节点局部密度ρ={ρ₁， ρ₂，...， ρ_n}为横坐标，与更高密度点的距离d={d₁，d₂，...，d_n}为纵坐标对应的决策图，其中，n为节点的总个数。在决策图中，局部密度和与更高密度点的距离都很大的点就是聚类中心。

在决策图中，聚类中心和非聚类中心的点之间通常相隔较远，能明显地看出哪些点是聚类中心。但是有时候聚类中心点离非聚类中心点很近，难以区分，针对这种情况，本文提出利用谱聚类对决策图上的点进行分析，从而得到聚类中心。为了避免局部密度和与更高密度点的距离的量纲影响谱聚类结果，首先对这些数据做归一化处理，使得局部密度和与更高密度点的距离的范围都在0到1之间。计算决策图中各个节点之间的距离，令相同节点之间的距离为0，从而得到主对角线为0的对称矩阵w。由于，本文只需要找出聚类簇中心点，这样便只需要区分聚类簇中心点和非聚类簇中心点，也就是谱聚类的聚类个数为2。将对称矩阵w作为权值矩阵，2作为聚类个数，对节点进行谱聚类，从而得到网络节点的聚类中心点集k={k₁，k₂，...，k_m}，其中，m为聚类中心点的个数。

通过以上方法求得的结果是节点的聚类中心，而本文的目标是得到网络的关键节点，因此，有必要对聚类中心的特征进行分析，判断聚类中心是否可以作为网络的关键节点。按照上述方法求得的聚类中心有几个较为明显的特征：聚类中心的局部密度比周围节点的局部密度大，周围节点间的联系较为紧密;更高密度点间距离较远。在一个网络中，攻击聚类簇的聚类中心比攻击该聚类簇的其他任一节点对该网络造成的破环程度都大。因此，本文的求得的聚类中心可以作为网络的关键节点。

3 实验分析

3.1 实验数据

在宽度20km，纵深30km的区域内随即设置300部超短波电台，电台的通信方式为跳频通信。

通过数据预处理，得到信号的频率、功率、周期、开始时间等物理特征。通过文献[7]构建网络拓扑的方法可以得到网络节点在以功率和周期为坐标的二维平面中的位置。部分网络节点相关信息如表1所示。

3.2 仿真结果及其分析

对300个网络节点进行密度峰值聚类，可以得到以局部密度为横坐标，与更高密度点的距离为纵坐标对应的决策图，如图3所示。为了防止局部密度和与更高密度点的距离的量纲影响谱聚类结果，首先对这些数据点进行归一化处理，使得局部密度和与更高密度点的距离的范围都在0到1之间。计算图3中各个点之间的距离，相同的点之间的距离为0，得到对称矩阵w。由于只需要确定聚类中心和非聚类中心，因此聚类个数为2。基于权值矩阵w和聚类个数2，对图3的节点进行谱聚类，从而得到网络中的关键节点，如图4所示，其中紫色的点表示聚类中心，黄色的点表示非聚类中心。从图中可以看出，该网络共有3个聚类中心，也就是有3个关键节点。

4 结束语

本文通过文献[7]提供的方法对频谱监测数据进行分析，从而构建出通信网络拓扑。通过改进的加权聚类系数计算得到节点的局部密度。基于节点的局部密度，对通信网络拓扑中的节点进行密度峰值聚类得到以局部密度为横坐标，与更高密度点的距离为纵坐标的二维决策图。对决策图中的节点进行谱聚类，从而分析得到通信网络拓扑的聚类中心。聚类中心的密度大于周围节点且聚类中心和更高密度点之间的距离较大，攻击聚类中心对网络的影响是最大的，因此，本文求得的聚类中心即为通信网络的关键节点。

参考文献（References）：

[1] 潘婷，武欣嵘，姚昌华，等.基于聚类分析的通联关系研究[J].

通信技术，2019，52（10）：2441-2446

[2] 李鹏飞，雷迎科.动态Ad hoc网络关键节点识别[J].计算机

应用研究，2017，34（5）：1473-1475，1495

[3] PHILLIP BONACICH. Factoring and weighting approach-

es to status scores and clique identification[J]. The Journal of Mathematical Sociology，1972，2（1）：113-120

[4] 谭跃进，吴俊，邓宏钟.复杂网络中节点重要度评估的节点收

缩方法[J].系统工程理论与实践，2006，26（11）：79-83，102

[5] Yan Ming，Chen Yewang，Hu Xiaoliang，Cheng Dongdong，

Chen Yi，Du Jixiang. Corrigendum to Intrusion detection based on improved density peak clustering for imbalanced data on sensor-cloud systems Journal of Systems Architecture volume 118 （2021） 102212[J]. Journal of Systems Architecture，2021，119

[6] Ma Xu，Zhang Shengen，Pena Pena Karelia，Arce Gonzalo

R.. Fast Spectral Clustering Method Based on Graph Similarity Matrix Completion[J]. Signal Processing，2021（prepublish）

[7] Liu C， Wu X， Zhu L， et al. The Communication

Relationship Discovery Based on the Spectrum Monitoring Data by Improved DBSCAN[J]. IEEE Access，20197EE6135F-5969-4040-B423-C71BAC5849A2