[發明專利]一種基于圖信號分析的關鍵節點識別方法及裝置

在審

• 申請號: 202110563477.0
• 申請日: 2021-05-24
• 公開（公告）號: CN113037572A
• 公開（公告）日: 2021-06-25
• 發明（設計）人: 王懷習;牛釗;馬春來;黃郡;常超;楊方;吳一塵;束妮娜
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L12/24
• 分類號: H04L12/24
• 代理公司: 中國和平利用軍工技術協會專利中心 11215
• 代理人: 劉光德

1.一種基于圖信號分析的關鍵節點識別方法，其特征在于，包括以下步驟：

步驟S101：計算網絡中所有節點的圖信號的數值；

步驟S102：根據節點的圖信號的數值，對網絡中所有節點進行分組，形成兩個分組子網絡；

步驟S103：求取分組子網絡之間的邊界網絡；

步驟S104：求取所述邊界網絡的最小割集作為關鍵節點集合。

2.如權利要求1所述的基于圖信號分析的關鍵節點識別方法，其特征在于，所述步驟S101：計算網絡中所有節點的圖信號的數值，包括：

計算網絡中節點度值矩陣D，鄰接矩陣A，所述節點度值矩陣D包括網絡中所有節點的節點度值，即網絡中節點的鄰居節點數量；所述鄰接矩陣A表示網絡中節點之間的鄰接關系，矩陣中的元素表征網絡中的頂點，如果節點i和j之間具有一條邊，則鄰接矩陣A中第i行第j列元素為1，否則為0，鄰接矩陣給出了網絡中頂點間的連接關系；

則網絡對應的拉普拉斯矩陣為L=D-A；對該拉普拉斯矩陣L進行特征分解：

L=UU^T （1）

其中，U為L特征向量組成的矩陣，U=[u₁,u₂,…,u_N], 為以L中特征值為對角線元素組成的對角矩陣，U^T表示U的轉置矩陣；對于第i個特征向量u_i對應的特征值λ_i，存在λ_iL=u_iL；，N為特征值的個數；

對求取得到的所有特征值按值的大小進行排序，選取第二小的特征值

λ_2min對應的特征向量u_2min作為網絡中所有節點的圖信號集合，每個節點k的圖信號對應于特征向量u_2min的第k個分量。

3.如權利要求2所述的基于圖信號分析的關鍵節點識別方法，其特征在于，所述步驟S102：根據節點的圖信號的數值，對網絡中所有節點進行分組，形成兩個分組子網絡，包括：

預設分組閾值，所述分組閾值為λ_2min對應的特征向量u_2min分量中的中位數，設置的標準或準則即以所述分組閾值劃分分組子網絡；

當節點的圖信號的數值大小小于所述分組閾值時，設定其對應標簽為1，否則為0，即滿足：

（2）

其中，g(i)為第i個節點對應的標簽，u_c為分組閾值， u_c取值為u_2min中所有圖信號的中位數；u_l(i)為節點的圖信號的數值；

在求取節點的標簽后，將標簽為1的節點放入A組，其余節點放入B組。