資源描述：
《馮顏-復雜網(wǎng)絡抗毀性優(yōu)化算法的設計.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)馮顏張琨黃奉孝鄒勇鑫南京理工大學計算機科學與技術學院南京理工大學計算機科學與技術學院目錄引言1復雜網(wǎng)絡抗毀性優(yōu)化算法2算法分析與實現(xiàn)3實例分析4南京理工大學計算機科學與技術學院1.引言研究意義無尺度網(wǎng)絡的雙重特性：對隨機失效的魯棒性&對選擇性攻擊的脆弱性復雜網(wǎng)絡抗毀性優(yōu)化算法的設計與實現(xiàn)對提高現(xiàn)實世界中各種網(wǎng)絡的抗毀性有著更為重要的應用價值。兩個關鍵技術一、生成高度為K/2的最小生成樹：滿足網(wǎng)絡的節(jié)點間跳數(shù)不大于K的要求；二、對高度為K/2的最小生成樹進行優(yōu)化：滿足連通度為2的要求。南京理工大學計算機科學與
2、技術學院1.引言在現(xiàn)實應用中，幾乎所有的復雜系統(tǒng)都可以抽象為復雜網(wǎng)絡模型。隨著復雜網(wǎng)絡的小世界效應及無標度特性的發(fā)現(xiàn)，復雜網(wǎng)絡研究逐漸成為多個學科共同關注的前沿熱點。一旦網(wǎng)絡的某個關鍵節(jié)點發(fā)生故障，將會給網(wǎng)絡的用戶帶來不便，有時甚至會導致非常嚴重的后果。為了使在蓄意破壞的情況下，網(wǎng)絡故障帶給用戶的損失減到最小，必須采取一定的措施使網(wǎng)絡在發(fā)生故障后能夠繼續(xù)提供一定的服務。1.引言南京理工大學計算機科學與技術學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法2.1抗毀性優(yōu)化算法設計目標主要手段：在網(wǎng)絡中增加足夠多的備份鏈路和備份設備。設計目標：忽略網(wǎng)絡帶寬的因素，
3、用最少的成本建設一個最小連通度為2的網(wǎng)絡。該網(wǎng)絡中任意一條傳輸鏈路中斷后，任意兩個節(jié)點間的最大跳數(shù)仍不超過K。圖論表示：給定的無向圖G(V，E)以及每條邊的開銷Ce，尋找一個最小連通度為2的最小開銷子圖；去除子圖中任意一條邊后，子圖中任意兩個節(jié)點間的跳數(shù)不大于K。目前在國內這類算法主要有劉麗娟提出的優(yōu)化IE模型算法、Wang等提出的熵優(yōu)化模型算法以及劉嘯林提出的基于生成樹優(yōu)化算法等。南京理工大學計算機科學與技術學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法2.2算法思想考慮實際的建網(wǎng)開銷和網(wǎng)絡使用過程情況，抗毀性優(yōu)化后的網(wǎng)絡應至少符合以下四點要求：（1）連
4、通度為2；（2）網(wǎng)絡的節(jié)點間跳數(shù)不能大于K值；（3）建網(wǎng)總開銷值相對較?。唬?）網(wǎng)絡實際使用時，與網(wǎng)絡的一個節(jié)點vi相連的一條邊故障后，需通過另一條邊即備份鏈路進行通信，以保持網(wǎng)絡正常工作；同時還需要保證其他各點到vi的開銷和相對較小。基于上述四點要求，算法涉及的相關定義如下：南京理工大學計算機科學與技術學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義1網(wǎng)絡拓撲結構：用鄰接矩陣表示的無向圖G(V，E)；頂點集合V=(v1,v2,…,vn)，邊集合e=(e1,e2,…,en)，eij=；定義2旁親父節(jié)點：比節(jié)點vi的層次值?。醇墑e比vi高）
5、，且不在同一條枝上的所有其他節(jié)點。例如圖1(b)中節(jié)點v3的旁親父節(jié)點為v0，v1，v5。定義3最佳生成樹：滿足高度為K/2，且開銷和相對最小的生成樹。圖1(a)給定一個無向圖(b)根為v6時的最小生成樹南京理工大學計算機科學與技術學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義4節(jié)點vi的層次Qi：生成樹的根定義為第0層，與根節(jié)點直接連接的節(jié)點定義為第l層，依此類推生成樹的葉子節(jié)點為第D層Qd。對節(jié)點的優(yōu)化又分為下述兩種情況：(1)對葉子節(jié)點vd進行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件:①節(jié)點vj的層次Qj≤D-1；②節(jié)點vj與vd的公共父節(jié)點只
6、有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0。(2)對非葉子節(jié)點vi進行優(yōu)化，增加邊edj，節(jié)點vj要滿足下述條件:①若節(jié)點vi的層次Qi＝k，那么節(jié)點vj的層次Qj≤k，此條件保證不會由于與節(jié)點vj的連接而導致跳數(shù)超限；②節(jié)點vj與vi的公共父節(jié)點只有一個，而且僅是根節(jié)點v0，或vj就是根節(jié)點v0。南京理工大學計算機科學與技術學院2.復雜網(wǎng)絡抗毀性優(yōu)化算法定義5網(wǎng)絡開銷和addCost(G)：帶權無向圖G的各邊權值總和。如圖1(a)所代表的網(wǎng)絡開銷和為19。定義6節(jié)點vi的開銷和addCost(vi)：網(wǎng)絡中所有其他節(jié)點到vi節(jié)點的鏈
7、路開銷之和。例如，addCost(v3)=2+(1+2)+(1+2)+(1+1+2)+(1+1+2)+(2+1+2)=21定義7換路：當層次值Qi>K/2的節(jié)點與其父節(jié)點的連接斷開時，從原無向圖中重新選擇一條邊并連接，使得節(jié)點vi在新圖中的層次值Qi′∈[1,K/2]，并且保證這條新的邊是權值相對最小的一條。圖1(b)根為v6時的最小生成樹圖2換路后得到的圖南京理工大學計算機科學與技術學院3.算法分析與實現(xiàn)3.1求最佳生成樹的三種求法(1)“修改過的prim算法”算法思想：在prim生成樹的每步過程中判斷加入的節(jié)點的層次，如果大于K/2就停
8、止此步，通過其他的相對最小的邊連接此節(jié)點，并繼續(xù)判斷，直到結束。時間復雜度：O(N×N2)(2)“prim算法試探+換路”的方法”算法思想：對給出的一個完全圖MG，每個節(jié)點都作為
