我們知道在網絡瓦解的總體進展中啟發(fā)式算法屬于其中的方法維度那么現(xiàn)在就開始具體展示啟發(fā)式算法在網絡瓦解問題中的效率問題總體來說啟發(fā)式算法就是用最小的代價去來去了解整個網絡的結構由此呢該算法會涉及到算法效率網絡韌性傳播動力學優(yōu)化控制等問題一、相關背景網絡瓦解通過移除部分和節(jié)點的邊來破壞網絡的結構削弱網絡的功能。啟發(fā)式算法化的神經網絡瓦解了我們通常是指在最小的代價也就是說通常因素最小的節(jié)點和邊的一個條件下是網絡的這個最大聯(lián)通子圖GCC能夠分散或者說縮小到了這樣的一個預設的這樣的一個閾值上面。網絡瓦解與網絡韌性的區(qū)別網絡瓦解越高韌性越低網絡瓦解主要研究系統(tǒng)在外部打擊或擾動情況下的功能失效程度或者說偏離其初始狀態(tài)的情況。研究的重點是如何有效地破壞網絡結構和功能通常會涉及到識別網絡中的關鍵節(jié)點或樞紐。網絡韌性:更關注整個網絡或系統(tǒng)的恢復能力或是維持原有功能的能力。韌性可以被視為一種持久性的特征。共同點在建模層面上二者都依賴于對整個網絡結構的整體理解和策略優(yōu)化。在算法方面我們在尋找最優(yōu)拆解方案時其實也在揭示整個網絡最脆弱的韌性結構。網絡瓦解算法的發(fā)展歷程從準確定位到模糊尋找的過程現(xiàn)在基本已經將這類網絡瓦解問題確切來說是組合優(yōu)化問題定義為NP-hard問題NP困難NP-hard問題是指一類計算復雜度極高的優(yōu)化或決策問題它們至少和NP類問題中最難的問題一樣難求解。通俗解釋P問題Polynomial【也就是說是一個非常容易的問題人腦或電腦能快速精確解決就算數(shù)據量變大10倍、100倍時間也不會爆炸。】能在多項式時間內比如O(n)、O(n2)、O(n3)等n是問題規(guī)模多項式時間 “實際可用的、比較快的時間”用確定性算法精確求解的問題。例如排序、找最短路徑普通圖上用Dijkstra算法等。規(guī)模變大時計算時間增長可控多項式時間的特點。NP問題Non-deterministic Polynomial【也就是說在規(guī)定時間內驗證容易但是找到卻很難】給定一個候選解能在多項式時間內驗證它是否正確的問題。但不一定能在多項式時間內找到這個解。經典例子旅行商問題TSP——給定路線能快速驗證總距離是否最優(yōu)但找最優(yōu)路線非常難。NP-hard問題【一般是非時間多項式2?】至少和NP中最難的問題一樣難。NP-hard問題分兩種屬于NP的NP-hard→ 叫NP-complete最有名的一類既難找也容易驗證不屬于NP的NP-hard→ 更難連驗證都難比如某些優(yōu)化問題涉及無限情況或超復雜驗證它不一定屬于NP即連驗證解是否正確都可能不是多項式時間實際可用的、比較快的時間有些NP-hard問題連驗證一個答案好不好都很慢或者驗證本身就很復雜。但如果能多項式時間解決一個NP-hard問題那么所有NP問題都能在多項式時間內解決即PNP這被認為是極不可能的。實際含義不存在已知的多項式時間精確算法問題規(guī)模稍大就無法在合理時間內精確求出最優(yōu)解。注意能在多項式時間內解決 → 認為是實際可高效解決的問題P類問題。做不到 → 就是難問題NP、NP-hard。為什么網絡瓦解Network Dismantling / Network Fragmentation是NP-hard網絡瓦解的目標通常是移除盡量少的節(jié)點/邊使整個網絡分裂成盡可能小的連通組件最小化最大組件大小或最大化碎片化程度。這屬于組合優(yōu)化問題需要從n個節(jié)點中選擇一個最優(yōu)子集來移除搜索空間是2?量級指數(shù)爆炸。已被理論證明是NP-hard可通過歸約從已知的NP-hard問題如Set Cover、Vertex Cover等規(guī)約而來。精確求解如整數(shù)規(guī)劃、分支定界只能處理很小的網絡幾十到幾百節(jié)點真實世界網絡成千上萬甚至百萬節(jié)點完全不可行。啟發(fā)式算法Heuristic的“中間位置”和啟發(fā)性這就是你提到的啟發(fā)式算法處于中間位置的原因精確算法Exact保證最優(yōu)解但時間爆炸NP-hard下不可行。隨機/窮舉完全盲目效率極低。啟發(fā)式算法不保證最優(yōu)解但能在可接受時間內給出“足夠好”的近似解。它的啟發(fā)性heuristic體現(xiàn)在利用領域知識或經驗規(guī)則快速做出決策而不是盲目搜索整個解空間。常見策略貪心選擇每次選當前“破壞力”最大的節(jié)點、局部搜索、進化算法、模擬退火、粒子群等。在網絡瓦解中典型的啟發(fā)式包括度中心性、介數(shù)中心性、集體影響力Collective Influence、核數(shù)k-core等指標或者更先進的如消息傳遞算法、強化學習等來指導節(jié)點選擇順序。犧牲最優(yōu)性換取高效性和可擴展性。在大規(guī)模網絡上啟發(fā)式往往能在幾秒到幾分鐘內給出接近最優(yōu)的結果?？偨YNP-hard意味著“精確最優(yōu)解在大型實例上不可能快速得到”所以實際應用中幾乎都依賴啟發(fā)式來提供實用解決方案。這也是為什么網絡瓦解、圖著色、旅行商、背包問題等經典問題都大量使用啟發(fā)式/元啟發(fā)式算法的原因。啟發(fā)式算法的優(yōu)劣優(yōu)勢首先它能夠在保證靈活性的前提下快速處理早期算法無法應對的大規(guī)模網絡。其次它具備較強的適應性。劣勢也相當明顯容易陷入局部最優(yōu)解。因此它對網絡結構的分布高度敏感泛化能力相對有限。本質上我們可以總結啟發(fā)式算法為它模擬了人類或自然進化過程中的經驗性智能。在算法的速度效率與最優(yōu)解之間尋求平衡。換句話說它能夠在可接受的時間內給出可接受的結果。 【是在模擬人類或者說自然進化過程中的這樣的一個經驗性的智能?！繂l(fā)式算法的發(fā)展歷程BPD實際上是一個基于自旋玻璃均場理論的啟發(fā)式算法。它通過構造最小反饋節(jié)點集旨在去除網絡中的環(huán)結構。該算法利用自信傳播或信念傳播的方法來估計每個節(jié)點對網絡聯(lián)通性的影響。隨后根據這些影響算法迭代地移除主動節(jié)點逐步消除網絡中的環(huán)結構最終將網絡轉變?yōu)闊o環(huán)圖。任小龍老師提出了“堅定”算法這是第一次將成本考慮納入其中。該算法基于復劃分區(qū)優(yōu)化旨在進行網絡分割。CI相關CoreHD相關DRC相關GND相關GND相關GDM相關流拆解相關代表論文解讀