基于聚類的關鍵節點識別

朱瑾　俞璐

摘? 要： 網絡對抗是現代戰爭的關鍵因素，對抗手段主要是攻擊節點，攻擊關鍵節點能夠用最少的資源最大程度地破壞敵方通信系統。現有研究大多通過挖掘節點在網絡拓撲中的地位來分析節點的重要程度。這種方法往往計算復雜，不適用于大規模網絡。提出通過聚類算法進行關鍵節點識別，對節點進行密度峰值聚類，得到以局部密度和與更高密度點的距離為坐標的決策圖，將決策圖中各節點間的距離作為權值矩陣進行譜聚類得到網絡的關鍵節點。

關鍵詞： 跳頻通信; 密度峰值聚類; 譜聚類; 關鍵節點識別

中圖分類號：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