基于聚類的關(guān)鍵節(jié)點(diǎn)識別

朱瑾　俞璐

摘? 要： 網(wǎng)絡(luò)對抗是現(xiàn)代戰(zhàn)爭的關(guān)鍵因素，對抗手段主要是攻擊節(jié)點(diǎn)，攻擊關(guān)鍵節(jié)點(diǎn)能夠用最少的資源最大程度地破壞敵方通信系統(tǒng)?，F(xiàn)有研究大多通過挖掘節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械牡匚粊矸治龉?jié)點(diǎn)的重要程度。這種方法往往計(jì)算復(fù)雜，不適用于大規(guī)模網(wǎng)絡(luò)。提出通過聚類算法進(jìn)行關(guān)鍵節(jié)點(diǎn)識別，對節(jié)點(diǎn)進(jìn)行密度峰值聚類，得到以局部密度和與更高密度點(diǎn)的距離為坐標(biāo)的決策圖，將決策圖中各節(jié)點(diǎn)間的距離作為權(quán)值矩陣進(jìn)行譜聚類得到網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。

關(guān)鍵詞： 跳頻通信; 密度峰值聚類; 譜聚類; 關(guān)鍵節(jié)點(diǎn)識別

中圖分類號：TP3-0? ? ? ? ? 文獻(xiàn)標(biāo)識碼：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 引言

當(dāng)今無線通信技術(shù)快速發(fā)展，無線通信設(shè)備多種多樣。其用在現(xiàn)代戰(zhàn)爭中，無線通信設(shè)備間的相互通信會產(chǎn)生數(shù)量龐大、種類繁多、不斷變化的信號，增加了電磁環(huán)境的復(fù)雜性，將阻礙作戰(zhàn)過程的順利進(jìn)行[1]。

作戰(zhàn)過程中，我方不但希望擾亂敵方作戰(zhàn)計(jì)劃，掌握戰(zhàn)場主動權(quán)，還希望通過最少的攻擊資源，迅速且精準(zhǔn)地破壞敵方通信網(wǎng)絡(luò)。要想實(shí)現(xiàn)該目標(biāo)，識別戰(zhàn)場通信網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)顯得十分重要。倘若可以發(fā)現(xiàn)敵方通信網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)，便能集中力量攻擊其關(guān)鍵節(jié)點(diǎn)，不但可以避免人力物力的不必要消耗，還可以嚴(yán)重打擊到敵方。

文獻(xiàn)[2]給出基于幾點(diǎn)間最短路徑的網(wǎng)絡(luò)連通性的定義，結(jié)合節(jié)點(diǎn)刪除法，計(jì)算節(jié)點(diǎn)刪除后對網(wǎng)絡(luò)連通性造成的影響大小，從而判斷該節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)拓?fù)渲械闹匾潭?。但是該方法沒有考慮到節(jié)點(diǎn)刪除后的網(wǎng)絡(luò)可能變得不再連通，在網(wǎng)絡(luò)不連通的情況下，節(jié)點(diǎn)刪除法往往無法判定節(jié)點(diǎn)的關(guān)鍵程度。文獻(xiàn)[3]計(jì)算網(wǎng)絡(luò)中與節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的個(gè)數(shù)，將其作為判斷該節(jié)點(diǎn)關(guān)鍵性程度的指標(biāo)。該方法是衡量節(jié)點(diǎn)重要程度最直觀簡單的方法，但是這種評估方法比較片面，有些節(jié)點(diǎn)雖然沒有很多鄰接節(jié)點(diǎn)，但是卻處于核心地位，例如連接兩個(gè)子網(wǎng)絡(luò)的節(jié)點(diǎn)。文獻(xiàn)[4]給出網(wǎng)絡(luò)凝聚度和節(jié)點(diǎn)收縮的概念，將節(jié)點(diǎn)收縮后網(wǎng)絡(luò)凝聚度的變化作為衡量節(jié)點(diǎn)重要度的指標(biāo)，節(jié)點(diǎn)收縮后網(wǎng)絡(luò)凝聚度越高節(jié)點(diǎn)重要度越大。但是，如果有多個(gè)節(jié)點(diǎn)在節(jié)點(diǎn)收縮后的網(wǎng)絡(luò)拓?fù)涠际窍嗤模敲磳⒑茈y區(qū)分這些節(jié)點(diǎn)的重要程度。

針對以上問題，本文提出一種基于聚類的通信網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別方法，求得的聚類中心即為通信網(wǎng)絡(luò)拓?fù)涞年P(guān)鍵節(jié)點(diǎn)。本文的方法不需要刪除或者收縮節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)生變化，也不會只是片面地根據(jù)單個(gè)指標(biāo)確定節(jié)點(diǎn)的關(guān)鍵程度。本文基于密度峰值聚類和譜聚類，結(jié)合節(jié)點(diǎn)的聚類系數(shù)和邊的權(quán)重，能夠高效地解決大型網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)識別問題。

1 理論基礎(chǔ)

假設(shè)將網(wǎng)絡(luò)抽象為G（V，E），V表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，記為V={v₁，v₂，...，v_n}，其中，n表示節(jié)點(diǎn)的個(gè)數(shù)，E表示節(jié)點(diǎn)間所有邊的集合，記為E={e₁，e₂，...，e_m}，其中，m表示邊的個(gè)數(shù)。根據(jù)連接節(jié)點(diǎn)的邊是否具有方向性，網(wǎng)絡(luò)被分為無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)，如圖1和圖2所示。7EE6135F-5969-4040-B423-C71BAC5849A2

目前，衡量網(wǎng)絡(luò)節(jié)點(diǎn)重要程度的指標(biāo)有很多，大體可以分為兩種方法：第一種方法無需改變網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，通過節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲械娘@著性反映節(jié)點(diǎn)的重要程度，例如度、距離、介數(shù)、聚類系數(shù)、特征向量法等;第二種方法需要改變網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，通過節(jié)點(diǎn)失效后對網(wǎng)絡(luò)連通性影響的大小來反映節(jié)點(diǎn)的重要程度，例如節(jié)點(diǎn)刪除法、節(jié)點(diǎn)收縮法等。本文利用聚類系數(shù)對通信網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)進(jìn)行識別。

聚類系數(shù)是衡量一個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)聚集程度的指標(biāo)。假設(shè)一個(gè)網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)i有k_i個(gè)直接相連的鄰居節(jié)點(diǎn)，這些相鄰節(jié)點(diǎn)之間最多可以有k_i（k_i-1）/2條邊，也就是任意兩個(gè)點(diǎn)之間都有邊且僅有一條邊。將節(jié)點(diǎn)i的聚類系數(shù)表示為c_i，則

其中，n_i為與節(jié)點(diǎn)i直接相連的節(jié)點(diǎn)之間實(shí)際存在邊的數(shù)目。

將該網(wǎng)絡(luò)節(jié)點(diǎn)的平均聚類系數(shù)表示為c，則

2 通信網(wǎng)絡(luò)拓?fù)潢P(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)

2.1 條件假設(shè)

由于現(xiàn)實(shí)環(huán)境過于復(fù)雜，很難達(dá)到，為了使研究更具有針對性，本文做出如下假設(shè)。

假設(shè)1：電臺間的通信方式為跳頻通信。

假設(shè)2：電臺采用停止等待ARQ協(xié)議進(jìn)行通信。

假設(shè)3：跳頻通信過程中，發(fā)送方發(fā)送數(shù)據(jù)幀和接收方回復(fù)ACK均在一次跳頻周期內(nèi)完成。

假設(shè)4：信號在傳播過程中不受任何障礙物的影響，沿直線傳播。

假設(shè)5：在頻譜監(jiān)測過程中，監(jiān)測站和電臺的位置都不發(fā)生變化。

2.2 數(shù)據(jù)預(yù)處理

設(shè)頻譜監(jiān)測數(shù)據(jù)集為X={x₁，x₂，...，x_i，...，v_n}，其中x_i={roll_i，T_roll，t_i，f_i，b_i，p_i}，其中，roll_i表示輪詢次數(shù)，T_roll表示輪詢周期，t_i表示以0s為開始掃描時(shí)間，輪詢到第i次的時(shí)間，f_i表示第i次輪詢周期內(nèi)信號的中心頻率，b_i表示第i次輪詢周期內(nèi)信號的帶寬，p_i表示第i次輪詢周期內(nèi)信號的功率。

按照頻率對頻譜監(jiān)測數(shù)據(jù)集X進(jìn)行聚類得到聚類集Y={y₁，y₂，...，y_i，...，y_ny}，n_y表示聚類簇的個(gè)數(shù)。對聚類簇y_i中頻譜監(jiān)測數(shù)據(jù)的當(dāng)前時(shí)間進(jìn)行升序排序，得到y(tǒng)t_i={yt₁，yt₂，...，yt_nyt}，其中n_yt為聚類簇y_i中頻譜監(jiān)測數(shù)據(jù)的個(gè)數(shù)，則yi的跳頻周期T_i=yt_nyt-yt₁。根據(jù)功率p對聚類簇y_i進(jìn)行聚類得到聚類集Z={z₁，z₂，...，z_j，...，z_nz}，n_z表示聚類簇的個(gè)數(shù)。計(jì)算z_j的中心頻點(diǎn)F_j、平均功率P_j、平均帶寬B_j、信號開始時(shí)間t_beginj、信號結(jié)束時(shí)間t_endj。

根據(jù)以上分析，可以得到預(yù)處理后的頻譜數(shù)據(jù)集D={d₁，d₂，...，d_i，...，d_n}，其中，d_i={F_i，B_i，P_i，T_i，t_begini，t_endi}，n為頻譜數(shù)據(jù)個(gè)數(shù)。

2.3 通信網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別

本文是對電臺通信網(wǎng)絡(luò)進(jìn)行關(guān)鍵節(jié)點(diǎn)識別，用G（V，E）表示電臺通信網(wǎng)絡(luò)，將電臺當(dāng)作網(wǎng)絡(luò)的節(jié)點(diǎn)，用V={v₁，v₂，...，v_i，...，v_n}，v_i={P_i，T_i}表示網(wǎng)絡(luò)的節(jié)點(diǎn)集，其中，n為電臺數(shù)目即節(jié)點(diǎn)數(shù)目，將電臺間的通聯(lián)關(guān)系抽象為網(wǎng)絡(luò)的邊，用E={e₁，e₂，...，e_m}表示網(wǎng)絡(luò)的邊集，其中，m為通聯(lián)關(guān)系數(shù)目即邊數(shù)目。

本文通過密度峰值聚類[5]和譜聚類[6]對通信網(wǎng)絡(luò)拓?fù)溥M(jìn)行關(guān)鍵節(jié)點(diǎn)識別。在進(jìn)行密度峰值聚類時(shí)，需要確定節(jié)點(diǎn)的局部密度和與更高密度點(diǎn)的距離這兩個(gè)特征，從而對聚類中心進(jìn)行刻畫。密度峰值聚類是將和節(jié)點(diǎn)i之間的距離小于截?cái)嗑嚯x的節(jié)點(diǎn)個(gè)數(shù)作為該節(jié)點(diǎn)的局部密度。這種方法雖然能夠很好的體現(xiàn)出節(jié)點(diǎn)的密集程度，但是節(jié)點(diǎn)的密集程度大不代表節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲刑幱陉P(guān)鍵的地位。倘若節(jié)點(diǎn)很密集，而相互之間卻并沒有直接的聯(lián)系，也就是節(jié)點(diǎn)間沒有相連接的邊，那么當(dāng)該節(jié)點(diǎn)因?yàn)樵獾焦舳r(shí)，幾乎不會影響到周圍的節(jié)點(diǎn)。因此，在識別關(guān)鍵節(jié)點(diǎn)時(shí)不但要考慮節(jié)點(diǎn)的密集程度，還要考慮節(jié)點(diǎn)間的邊，節(jié)點(diǎn)間的邊主要包括節(jié)點(diǎn)間是否相連接和邊的權(quán)重這兩個(gè)特征。

從公式⑴可以看出，聚類系數(shù)是計(jì)算節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)之間真實(shí)存在的邊的數(shù)目占可能存在的邊的數(shù)目的比例，能夠很好地反映出邊連接的緊密程度。節(jié)點(diǎn)的密集程度越大，相當(dāng)于周圍節(jié)點(diǎn)離該節(jié)點(diǎn)的距離都比較近，因此，將節(jié)點(diǎn)間的距離作為邊的權(quán)重。本文將對聚類系數(shù)進(jìn)行改進(jìn)，將聚類系數(shù)和邊的權(quán)重相結(jié)合，從而更好地描述各節(jié)點(diǎn)的局部密度。7EE6135F-5969-4040-B423-C71BAC5849A2

2.3.1 改進(jìn)的聚類系數(shù)

為了更好地描述節(jié)點(diǎn)的局部密度，本文對聚類系數(shù)進(jìn)行改進(jìn)，將聚類系數(shù)和節(jié)點(diǎn)間邊的權(quán)重相結(jié)合，將這種加權(quán)聚類系數(shù)作為節(jié)點(diǎn)的局部密度。

節(jié)點(diǎn)i的局部密度記為w_i，則

其中，n為網(wǎng)絡(luò)拓?fù)渲泄?jié)點(diǎn)總數(shù)，s和t都表示網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)，d_st表示節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)間存在邊的節(jié)點(diǎn)s和節(jié)點(diǎn)t之間的距離，[Dpq]表示節(jié)點(diǎn)i鄰居節(jié)點(diǎn)中任意兩個(gè)節(jié)點(diǎn)s和節(jié)點(diǎn)t之間的距離。

聚類系數(shù)是計(jì)算節(jié)點(diǎn)i鄰居節(jié)點(diǎn)之間真實(shí)的邊數(shù)目占所有可能的邊數(shù)目的比例，本文提出的改進(jìn)的聚類系數(shù)是將這些邊的權(quán)重添加進(jìn)去，計(jì)算節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)之間真實(shí)的邊權(quán)重和占所有可能的邊的權(quán)重和的比例，從而更好地描述節(jié)點(diǎn)的局部密度。

2.3.2 基于聚類的關(guān)鍵節(jié)點(diǎn)識別

根據(jù)公式⑶計(jì)算得到各節(jié)點(diǎn)的加權(quán)聚類系數(shù)，將其作為局部密度對節(jié)點(diǎn)進(jìn)行密度峰值聚類，從而得到以節(jié)點(diǎn)局部密度ρ={ρ₁， ρ₂，...， ρ_n}為橫坐標(biāo)，與更高密度點(diǎn)的距離d={d₁，d₂，...，d_n}為縱坐標(biāo)對應(yīng)的決策圖，其中，n為節(jié)點(diǎn)的總個(gè)數(shù)。在決策圖中，局部密度和與更高密度點(diǎn)的距離都很大的點(diǎn)就是聚類中心。

在決策圖中，聚類中心和非聚類中心的點(diǎn)之間通常相隔較遠(yuǎn)，能明顯地看出哪些點(diǎn)是聚類中心。但是有時(shí)候聚類中心點(diǎn)離非聚類中心點(diǎn)很近，難以區(qū)分，針對這種情況，本文提出利用譜聚類對決策圖上的點(diǎn)進(jìn)行分析，從而得到聚類中心。為了避免局部密度和與更高密度點(diǎn)的距離的量綱影響譜聚類結(jié)果，首先對這些數(shù)據(jù)做歸一化處理，使得局部密度和與更高密度點(diǎn)的距離的范圍都在0到1之間。計(jì)算決策圖中各個(gè)節(jié)點(diǎn)之間的距離，令相同節(jié)點(diǎn)之間的距離為0，從而得到主對角線為0的對稱矩陣w。由于，本文只需要找出聚類簇中心點(diǎn)，這樣便只需要區(qū)分聚類簇中心點(diǎn)和非聚類簇中心點(diǎn)，也就是譜聚類的聚類個(gè)數(shù)為2。將對稱矩陣w作為權(quán)值矩陣，2作為聚類個(gè)數(shù)，對節(jié)點(diǎn)進(jìn)行譜聚類，從而得到網(wǎng)絡(luò)節(jié)點(diǎn)的聚類中心點(diǎn)集k={k₁，k₂，...，k_m}，其中，m為聚類中心點(diǎn)的個(gè)數(shù)。

通過以上方法求得的結(jié)果是節(jié)點(diǎn)的聚類中心，而本文的目標(biāo)是得到網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)，因此，有必要對聚類中心的特征進(jìn)行分析，判斷聚類中心是否可以作為網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。按照上述方法求得的聚類中心有幾個(gè)較為明顯的特征：聚類中心的局部密度比周圍節(jié)點(diǎn)的局部密度大，周圍節(jié)點(diǎn)間的聯(lián)系較為緊密;更高密度點(diǎn)間距離較遠(yuǎn)。在一個(gè)網(wǎng)絡(luò)中，攻擊聚類簇的聚類中心比攻擊該聚類簇的其他任一節(jié)點(diǎn)對該網(wǎng)絡(luò)造成的破環(huán)程度都大。因此，本文的求得的聚類中心可以作為網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

在寬度20km，縱深30km的區(qū)域內(nèi)隨即設(shè)置300部超短波電臺，電臺的通信方式為跳頻通信。

通過數(shù)據(jù)預(yù)處理，得到信號的頻率、功率、周期、開始時(shí)間等物理特征。通過文獻(xiàn)[7]構(gòu)建網(wǎng)絡(luò)拓?fù)涞姆椒梢缘玫骄W(wǎng)絡(luò)節(jié)點(diǎn)在以功率和周期為坐標(biāo)的二維平面中的位置。部分網(wǎng)絡(luò)節(jié)點(diǎn)相關(guān)信息如表1所示。

3.2 仿真結(jié)果及其分析

對300個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行密度峰值聚類，可以得到以局部密度為橫坐標(biāo)，與更高密度點(diǎn)的距離為縱坐標(biāo)對應(yīng)的決策圖，如圖3所示。為了防止局部密度和與更高密度點(diǎn)的距離的量綱影響譜聚類結(jié)果，首先對這些數(shù)據(jù)點(diǎn)進(jìn)行歸一化處理，使得局部密度和與更高密度點(diǎn)的距離的范圍都在0到1之間。計(jì)算圖3中各個(gè)點(diǎn)之間的距離，相同的點(diǎn)之間的距離為0，得到對稱矩陣w。由于只需要確定聚類中心和非聚類中心，因此聚類個(gè)數(shù)為2?；跈?quán)值矩陣w和聚類個(gè)數(shù)2，對圖3的節(jié)點(diǎn)進(jìn)行譜聚類，從而得到網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，如圖4所示，其中紫色的點(diǎn)表示聚類中心，黃色的點(diǎn)表示非聚類中心。從圖中可以看出，該網(wǎng)絡(luò)共有3個(gè)聚類中心，也就是有3個(gè)關(guān)鍵節(jié)點(diǎn)。

4 結(jié)束語

本文通過文獻(xiàn)[7]提供的方法對頻譜監(jiān)測數(shù)據(jù)進(jìn)行分析，從而構(gòu)建出通信網(wǎng)絡(luò)拓?fù)?。通過改進(jìn)的加權(quán)聚類系數(shù)計(jì)算得到節(jié)點(diǎn)的局部密度?；诠?jié)點(diǎn)的局部密度，對通信網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)進(jìn)行密度峰值聚類得到以局部密度為橫坐標(biāo)，與更高密度點(diǎn)的距離為縱坐標(biāo)的二維決策圖。對決策圖中的節(jié)點(diǎn)進(jìn)行譜聚類，從而分析得到通信網(wǎng)絡(luò)拓?fù)涞木垲愔行?。聚類中心的密度大于周圍?jié)點(diǎn)且聚類中心和更高密度點(diǎn)之間的距離較大，攻擊聚類中心對網(wǎng)絡(luò)的影響是最大的，因此，本文求得的聚類中心即為通信網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)。

參考文獻(xiàn)（References）：

[1] 潘婷，武欣嶸，姚昌華，等.基于聚類分析的通聯(lián)關(guān)系研究[J].

通信技術(shù)，2019，52（10）：2441-2446

[2] 李鵬飛，雷迎科.動態(tài)Ad hoc網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識別[J].計(jì)算機(jī)

應(yīng)用研究，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ìn)，吳俊，鄧宏鐘.復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要度評估的節(jié)點(diǎn)收

縮方法[J].系統(tǒng)工程理論與實(shí)踐，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