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