[發明專利]一種基于動態閾值搜索算法的內生系統關鍵節點識別方法

在審

• 申請號: 202310046778.5
• 申請日: 2023-01-31
• 公開（公告）號: CN116128054A
• 公開（公告）日: 2023-05-16
• 發明（設計）人: 孫雯;王鑄清;李文龍;胡愛群;陳超凡;吳自豪
• 申請（專利權）人: 東南大學
• 主分類號: G06N5/01
• 分類號: G06N5/01
• 代理公司: 南京眾聯專利代理有限公司 32206
• 代理人: 葉涓涓

本發明提供了一種基于動態閾值搜索算法的內生系統關鍵節點識別方法，包括：通過約簡規則簡化問題；貪心構造初始解；利用局部搜索優化初始解；采用擾動方法，跳出局部最優區域；執行恢復程序獲取完整反饋頂點集。本發明將內生系統關鍵節點識別抽象為最小反饋頂點集問題，即給定一個有向圖，去掉反饋頂點集后可以使圖無環；采用三種精確的約簡規則來簡化原圖，通過貪婪的初始化來生成初始的無環子圖，采用動態閾值局部搜索來減少無環子圖的大小，以及一種基于學習的擾動來重新考慮被錯誤地劃分進反饋頂點集的頂點。本發明運行快速，性能優異，在運行時間和性能上取得了良好的平衡。

技術領域

本發明屬于人工智能技術領域，涉及組合優化方案中解決最小反饋頂點集問題的相關技術，具體涉及一種基于動態閾值搜索算法的內生系統關鍵節點識別方法。

背景技術

為了確保內生系統安全，就必須重點保護那些一旦遭到攻擊就可能對系統造成重大損失的關鍵節點或關鍵節點的集合。基于節點移除與收縮的節點重要性方法常被用于識別這些關鍵節點，該方法將節點的重要性等同于移除節點對網絡造成的破壞性，認為移除節點后對網絡造成的破壞程度越大則該節點越關鍵。

在真實網絡中，網絡功能往往是由網絡的連通性決定的，當具有顯著連通性特征的節點被攻擊時，整個網絡將被迅速拆解，遭受極大的破壞，因此亟需研究針對網絡拆解攻擊的防御方案，保護與連通性關聯緊密的關鍵節點，降低攻擊危害。目前，最普遍的拆解思路為：先將一個網絡拆解為一個森林結構，再對森林中的樹進行拆解。其中，如何通過移除頂點的方式將網絡變成樹狀結構這一問題可建模為反饋頂點集合問題。因此我們將反饋頂點集合識別為關鍵頂點集合，實行重點防護，以提高網絡的抗毀性和穩定性。

反饋頂點集合問題一直在學界和工業界受到廣泛關注，許多研究者致力于開發精確算法或啟發式算法。但是，現有的算法在處理反饋頂點集合問題上依然存在以下兩個問題：

(1)精確算法存在不可避免的指數時間復雜度問題。現有的精確算法僅能在特定的小規模圖上進行反饋頂點集合識別，隨著網絡規模擴大，時間復雜度將會指數級地增長，難以有效適用于中大規模網絡。

(2)啟發式算法未設計學習機制以合理地利用歷史信息。將啟發式算法與學習機制有機整合，可以有效地從歷史搜索信息中獲得反饋，以指導之后的搜索路徑，使算法具備靈活的可擴展性和良好的穩定性。

自反饋頂點集合問題被提出以來，相關的研究不斷取得進展。然而，很少有算法能夠在運行時間和性能上取得一個良好的平衡。

發明內容

本發明解決的最小反饋頂點集問題可以定義為：給定一個有向圖G＝V,E，其中V表示頂點的集合，E表示邊的集合。反饋頂點集(FVS)是一個頂點子集將其去掉可得到一個無環圖。反饋點集問題(FVSP)的目的是識別一個最小基數的反饋點集問題。換句話說，我們想要移除最少的頂點，使圖成為無環的。基于此，本發明提供一種基于動態閾值搜索算法的內生系統關鍵節點識別方法。

為了達到上述目的，本發明提供如下技術方案：

一些基本符號表示，包括如下定義：

定義1，關鍵頂點

G的關鍵頂點是屬于FVS的頂點。我們用C來表示已經檢測到的關鍵頂點的集合。只有當FVS的所有頂點都被檢測到時，C才是一個FVS。

定義2，非關鍵頂點

非關鍵頂點是不屬于FVS的頂點。用U表示非關鍵頂點集，V＝C∪U,

定義3，冗余頂點