基于流量及可靠性的不確定圖邊關鍵度研究.pdf

1、不確定圖的關鍵邊是指相對于其他邊而言，能夠在更大程度上影響網(wǎng)絡結構與功能的一些特殊邊，一旦發(fā)生故障，將對整個系統(tǒng)產(chǎn)生巨大影響，甚至導致系統(tǒng)癱瘓。目前，網(wǎng)絡中關鍵邊挖掘因其廣泛的應用價值和理論研究意義，受到眾多研究人員的關注，各種針對特定應用需求的邊關鍵度評估方案不斷被提出。這些方法站在各自的立場，從不同角度為我們探索不同應用需求下節(jié)點的重要性提供可選的方案。本文提出適用于流網(wǎng)絡的關鍵邊評價模型，針對網(wǎng)絡中邊損毀（故障）后對流量和可靠性產(chǎn)

2、生的相對損失來綜合衡量關鍵邊，重點在于如何在動態(tài)變化的網(wǎng)絡環(huán)境中對最大流和可靠性進行快速計算，從而實現(xiàn)動態(tài)流網(wǎng)絡中邊關鍵度既準確又快速的評估。論文主要包括以下幾個方面:
　　(1)從邊損毀（故障）后對流量和容量可靠性產(chǎn)生的相對損失這一角度，構建了一種基于流量和容量可靠性的關鍵邊衡量模型，對邊的關鍵度進行綜合評估。針對此模型，首先設計了一種基于最大流和容量可靠性重新計算的原始算法BASE_FCP，然后針對其性能存在的不足，提出基于流

3、量和容量可靠性的狀態(tài)區(qū)間緩存算法SCA_FCP，其首先將不確定圖的邊定性分類，然后根據(jù)不同的邊設計不同的計算方法以減少復雜度。最后，實驗分析表明，SCA_FCP相對于BASE_FCP雖然在空間復雜度有一定的增加，但在時間復雜度方面具有較大的優(yōu)勢。
　　(2)雖然基于流量和容量可靠性的模型對于關鍵邊的區(qū)分度較好，但不確定圖容量可靠性的計算過于復雜，而計算不確定圖分布可靠性只需要獲取其極小子圖即可，為此，本文重新構建了一種基于流量和分

4、布可靠性的關鍵邊模型。針對此模型，首先提出了基于流量和分布可靠性的狀態(tài)區(qū)間緩存算法SCA_FDP，但是考慮到其在狀態(tài)劃分過程中存在初始狀態(tài)劃分空間大的缺點，為此，提出一種基于確定邊過濾的優(yōu)化算法SCA_FEA，該算法使用割集邊和懸掛邊對于初始劃分集合剪枝，從而減少初始狀態(tài)劃分集合大小。實驗表明基于流量和分布可靠性的模型比基于流量和容量可靠性的模型，不管在時間還是空間性能上都有提升，相對于算法SCA_FDP，SCA_ FEA也使得時間性能

5、有了一定程度的提升。
　　(3)針對基于流量和分布可靠性的關鍵邊模型，使用算法SCA_FEA計算不確定圖（最可靠最大流）分布可靠性依然是一個NP-Hard問題，難以滿足對計算速度要求很高的實時環(huán)境中，為此，提出一種基于流量和分布可靠性的關鍵邊近似算法KEAA_FDP，該算法利用最大流分布的剩余圖，通過流量調整，選取最可靠簡單路徑進行增廣，實現(xiàn)（最可靠最大流）分布可靠性快速計算，并給出了近似算法獲取的關鍵邊序列解和精確算法解的相似性