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

在審

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

本發明提供一種基于圖信號分析的關鍵節點識別方法及裝置，所述方法包括：計算網絡中所有節點的圖信號的數值；根據節點的圖信號的數值，對網絡中所有節點進行分組，形成兩個分組子網絡；求取分組子網絡之間的邊界網絡；求取所述邊界網絡的最小割集作為關鍵節點集合。根據本發明的方案，能夠實現失效后造成網絡割裂的關鍵節點識別。

技術領域

本發明涉及計算機網絡領域，尤其涉及一種基于圖信號分析的關鍵節點識別方法與裝置。

背景技術

網絡的很多機制和功能通常會受到小部分節點的極大影響，這些節點通常被定義為關鍵節點。相關研究表明，當網絡遭受到蓄意攻擊時，5%的關鍵節點被摧毀，網絡就會幾乎癱瘓。對關鍵節點進行識別，將有助于進一步減小監測負擔，也有助于提高網絡安全防護能力。

關鍵節點識別問題又被稱為關鍵節點檢測問題（Critical Node DetectionProblem，CNDP），該問題是一個尋找對網絡性能發揮存在重要影響的節點集問題。目前，針對關鍵節點識別的相關研究主要涉及社會網絡、生物網絡、通信網絡、電力網絡和交通網絡等多個領域，相關識別方法主要分為兩類，一類是將節點的重要性等價于節點的關鍵性，通過設定重要性衡量指標求取網絡中所有節點的重要性度量值，進而根據度量值的排序結果完成關鍵節點的識別，相關算法根據衡量指標是區域性指標或是全局性指標，分為基于局部特征的識別方法和基于全局特征的識別方法；另一類是將節點被刪除后對網絡產生的破壞性等價于節點的關鍵性，通過設定網絡魯棒性評估指標衡量節點被刪除后網絡魯棒性的變化值大小，進而根據變化值大小的排序結果完成關鍵節點的識別，變化值越大意味著節點越關鍵。代表方法主要包括節點刪除法和節點收縮法。網絡魯棒性是指網絡在其部分受損（故障）時仍能正常工作的能力，根據在研究過程中是否對網絡負載的再分配進行考慮，網絡的魯棒性主要分為靜態魯棒性和動態魯棒性，其中，靜態魯棒性是指節點被刪除后網絡仍能保持連通的能力，沒有考慮負載的再分配問題。

基于局部特征的識別方法主要通過對節點的鄰居節點或者跳內鄰居節點的重要性進行評價來識別關鍵節點，代表算法主要包括度中心性（Degree Centrality），基于局部信息的中心性、-殼分解法等?；诰植刻卣鞯淖R別方法的優點是計算復雜度低，能夠反映節點在局部網絡中的重要性，體現了節點與周圍鄰居節點的連通狀態，但是沒有考慮周圍鄰居節點自身的重要性。

基于全局特征的識別方法，主要對網絡拓撲結構進行分析，從信息傳輸路徑的角度對節點關鍵性進行評價或者綜合考慮周圍鄰居重要性對節點的關鍵性進行評價，具有代表性的衡量指標包括介數中心性（Betweenness Centrality）、接近中心性（ClosenessCentrality）、離心中心性（Eccentricity Centrality）、特征向量中心性（EigenvectorCentrality）和PageRank算法等。

基于重要性等價于關鍵性的識別方法，最終篩選的關鍵節點的好壞主要取決于衡量指標的好壞，如果選取的衡量指標有片面性，最終篩選的關鍵節點可能只是局部性關鍵節點。

節點刪除法，在衡量節點的過程中，假設節點失效，通過比較節點失效前后網絡魯棒性的變化來評估節點的重要性。其缺點是，如果網絡中存在多個節點失效后都能導致網絡不連通，則這些節點的重要程度相同，無法進行區分。節點收縮法，將一個節點和其連接的鄰居節點收縮為一個新節點，原有的與鄰居節點連接的邊都與新節點連接，進而求取節點收縮前后網絡凝聚度的變化，使用節點重要度的大小完成節點重要程度的衡量。越重要的節點收縮后，網絡的凝聚度值越大。節點收縮法的缺點是運算復雜度比較大，為，并不適用于規模較大的網絡。

基于破壞性等價于關鍵性的識別方法，避免了由于衡量指標選擇不合理給關鍵節點識別帶來的一些問題，但是，對網絡魯棒性衡量指標的選取又提出了較高要求，衡量指標的不合理將直接影響識別結果的好壞。

總結來看，目前大多數關鍵節點識別方法并沒有針對特定破壞性影響（例如網絡出現割裂或者癱瘓）進行關鍵節點識別。

發明內容