張柏禮 楊 娟 呂建華 田 偉

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京 211189)(2東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室, 南京 211189)(3南京弘毅電氣自動(dòng)化有限公司, 南京 210039)

基于不確定圖的最可靠最大流的改進(jìn)算法

張柏禮1,2楊 娟1呂建華1,2田 偉3

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 南京 211189)(2東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室, 南京 211189)(3南京弘毅電氣自動(dòng)化有限公司, 南京 210039)

針對(duì)網(wǎng)絡(luò)規(guī)模和稠密度的增大最可靠最大流SDBA算法性能下降較快的不足,提出了基于概率和割集雙過濾的狀態(tài)空間劃分算法DF-SDBA.首先,在狀態(tài)空間劃分過程中使用概率約束,針對(duì)每一個(gè)待處理的區(qū)間,篩選掉下界分布概率值小于當(dāng)前最可靠最大流分布的未處理區(qū)間,有效地減少了算法迭代的次數(shù);然后,針對(duì)不確定的區(qū)間使用割集約束,即在區(qū)間上界對(duì)應(yīng)的子圖中求出最大流,同時(shí)求出最小割集,根據(jù)最小割集中的邊必須都出現(xiàn)在合格子區(qū)間上界向量中這一規(guī)則,對(duì)待劃分的子區(qū)間進(jìn)行篩選,從而進(jìn)一步減少了劃分區(qū)間的數(shù)量.實(shí)驗(yàn)結(jié)果表明,相對(duì)于SDBA算法,DF-SDBA算法有效地減少了需要?jiǎng)澐值膮^(qū)間,很大程度上克服了網(wǎng)絡(luò)規(guī)模和稠密度對(duì)算法性能的影響,具有顯著的性能優(yōu)勢(shì),有效地提高了算法的適用性.

不確定圖;最大流;流可靠性;最小割

不確定性是系統(tǒng)的固有屬性,近年來研究人員對(duì)該問題進(jìn)行了深入的研究,提出了很多有價(jià)值的問題和解決方案[1-8].首先,對(duì)于不確定子圖,文獻(xiàn)[1-2]采用了路徑覆蓋、啟發(fā)式的貪心算法等解決了在不確定圖中挖掘最可靠子圖問題;鄒兆年等[3]、張碩等[4]針對(duì)挖掘模型構(gòu)建、降低子圖同構(gòu)的時(shí)間復(fù)雜度以及k極大頻繁模式挖掘等問題分別提出了高效算法;Yuan等[5]通過采用過濾-驗(yàn)證的思想研究了子圖相似性查詢,先利用概率矩陣索引最大化的過濾候選集,再通過取樣算法驗(yàn)證相似性.對(duì)于不確定圖上的k近鄰問題,張海杰等[6]基于“可靠期望距離”建立了高效的近鄰關(guān)系圖索引,將近鄰查詢等價(jià)地轉(zhuǎn)化為近鄰關(guān)系圖上的團(tuán)查詢問題;張應(yīng)龍等[7]基于SimRank度量的方法提出了求解不確定圖的k-NN查詢;而文獻(xiàn)[8]在不確定圖上拓展了最短路徑問題, 并給出了解決思路和算法.

此外,不確定圖最大流問題是傳統(tǒng)最大流問題在不確定圖上的自然延伸,用于衡量網(wǎng)絡(luò)的承載能力,產(chǎn)生了很多有價(jià)值的問題,其中隨機(jī)流網(wǎng)絡(luò)的可靠性和最可靠最大流是其中2個(gè)相互聯(lián)系又有區(qū)別的問題.隨機(jī)流網(wǎng)絡(luò)可靠性研究的是:對(duì)于存在多種不確定因素的網(wǎng)絡(luò),如何評(píng)價(jià)其傳遞最大流或額定流量的可靠性.該問題已經(jīng)被證明為NP-hard問題[9],近年來一些研究人員提出了很多相關(guān)算法[10-13],包括針對(duì)小規(guī)模圖的完全枚舉狀態(tài)空間算法、狀態(tài)空間劃分等精確算法以及針對(duì)大規(guī)模圖的蒙特卡洛仿真、機(jī)器學(xué)習(xí)等近似算法.而蔡偉等[14]提出的最可靠最大流問題,主要研究最大流量可能對(duì)應(yīng)多個(gè)最大流分布,在多個(gè)最大流分布中,存在著可靠性最高的分布,而將可靠性最高的分布作為流傳遞的首選方案,保證可靠性傳輸,進(jìn)而有效地解決可靠性網(wǎng)絡(luò)的構(gòu)建、可靠傳輸路徑選擇等一系列實(shí)際問題.SDBA算法[14]是現(xiàn)有解決最可靠最大流的一種有效算法,該算法使用狀態(tài)空間劃分得到所有滿足最大流的閉合區(qū)間,然后尋找區(qū)間下界概率值最大的可能子圖,即得到最可靠最大流分布.然而,隨著網(wǎng)絡(luò)規(guī)模的變大,頂點(diǎn)的增加導(dǎo)致子圖維度空間變大,使得SDBA算法處理單個(gè)區(qū)間的時(shí)間變長(zhǎng),稠密度增加又使待劃分區(qū)間的數(shù)量急劇增長(zhǎng),導(dǎo)致算法的時(shí)間開銷也隨之迅速增加,很大程度上影響了算法的適用性.

為此,本文對(duì)SDBA算法進(jìn)行改進(jìn),提出基于概率和割集雙過濾的狀態(tài)空間劃分算法DF-SDBA,以解決網(wǎng)絡(luò)規(guī)模的增加和稠密度的增大對(duì)SDBA算法性能的不利影響.DF-SDBA算法首先在狀態(tài)空間劃分過程中使用概率約束,篩選掉區(qū)間下界分布概率值小于當(dāng)前最可靠最大流分布的未處理區(qū)間,有效地減少了算法迭代的次數(shù);然后,對(duì)待劃分區(qū)間使用割集約束,即在其區(qū)間上界對(duì)應(yīng)的子圖中求出最大流,同時(shí)求出最小割集,而最小割集中的邊必須全部出現(xiàn)在合格子區(qū)間上界對(duì)應(yīng)的可能子圖中,進(jìn)一步篩選劃分得到的子區(qū)間,再一次減少了劃分區(qū)間的數(shù)量,從而有效地提高算法的效率.

1 DF-SDBA算法

1.1 DF-SDBA算法思路

與隨機(jī)流網(wǎng)絡(luò)的可靠性問題類似,狀態(tài)空間劃分方法也是解決最可靠最大流問題的基本算法,利用一系列的劃分規(guī)則對(duì)不確定圖所蘊(yùn)含的子圖空間進(jìn)行劃分,得到滿足最大流的區(qū)間、不滿足最大流的區(qū)間和待劃分的區(qū)間.滿足最大流的區(qū)間加入到候選集中,不滿足最大流的區(qū)間丟棄,而待劃分的區(qū)間需要進(jìn)一步劃分,直到不存在待劃分的區(qū)間為止.最終,計(jì)算候選集中所有區(qū)間下界對(duì)應(yīng)可能子圖的概率值,找到最大概率值的下界子圖,從而得到最可靠最大流.

上述過程也是SDBA算法的基本思路,這與隨機(jī)流網(wǎng)絡(luò)可靠性經(jīng)典的算法過程類似,兩者的主要差別只是在最后階段,對(duì)候選集的處理方法不同,隨機(jī)流網(wǎng)絡(luò)可靠性問題是將候選集中所有區(qū)間對(duì)應(yīng)的概率值相加,而SDBA算法需要選擇概率值最大的閉合區(qū)間.這也是本文提出改進(jìn)算法的切入點(diǎn):隨機(jī)流網(wǎng)絡(luò)可靠性問題需要找到所有滿足最大流的閉合區(qū)間對(duì)應(yīng)的可能子圖的概率和,而最可靠最大流問題僅需要在所有滿足最大流的區(qū)間中找到區(qū)間下界對(duì)應(yīng)的可能子圖概率值中最大的一個(gè).因而,可以利用各種過濾手段,將那些不滿足要求的區(qū)間篩選掉,盡可能地減少待劃分的區(qū)間數(shù)量,從而提高算法的效率.為此,本文提出基于概率和割集雙過濾的狀態(tài)空間劃分改進(jìn)算法DF-SDBA,其具體的算法思路如下.

1) 在不確定圖G的最大子圖MSG(G)上運(yùn)行最大流算法,得到源點(diǎn)s到終點(diǎn)t最大流值Fmax.

2) 根據(jù)求得的最大流狀態(tài)向量對(duì)不確定圖G的子圖空間Ω進(jìn)行劃分,得到滿足最大流的區(qū)間、不滿足最大流的區(qū)間和待劃分的區(qū)間,分別進(jìn)行如下處理:

① 對(duì)于每個(gè)未處理的區(qū)間,若其區(qū)間下界對(duì)應(yīng)的概率值小于當(dāng)前最可靠最大流分布的概率值,則直接丟棄;

② 對(duì)于滿足最大流的區(qū)間,若其概率值大于當(dāng)前最可靠最大流分布的概率值,則更新最可靠最大流分布;

③ 對(duì)于待劃分的區(qū)間,需要進(jìn)一步劃分,從而得到若干子區(qū)間,必須保證最小割集中的邊在子區(qū)間上界向量中全部存在,否則該子區(qū)間不滿足最大流,也可以直接丟棄.

3) 在2)得到的概率值最大的區(qū)間下界對(duì)應(yīng)的子圖上運(yùn)行最大流算法,得到最可靠最大流分布.

1.2 過濾規(guī)則

規(guī)則1(概率過濾規(guī)則) 對(duì)于任一區(qū)間,若其區(qū)間下界的概率值小于當(dāng)前最可靠最大流分布的概率值,則該區(qū)間中不可能存在可靠性更高的最大流分布.

由前面分析可知,與隨機(jī)流網(wǎng)絡(luò)可靠性問題不同,隨機(jī)流網(wǎng)絡(luò)可靠性需要求出所有滿足最大流的區(qū)間并累加其概率值,而最可靠最大流問題只需找到具有最大概率值的區(qū)間,這就為概率篩選提供了基礎(chǔ).

設(shè)算法求解過程中,當(dāng)前可靠性最高的最大流分布的概率值為P(Vm),Vm為所對(duì)應(yīng)的分布.根據(jù)流分布概率的計(jì)算規(guī)則可知,在任一區(qū)間中,其下界向量所對(duì)應(yīng)的分布具有局部的最大概率值(無論能否滿足最大流),區(qū)間范圍內(nèi)不可能存在其他具有更高概率的最大流分布.因此,在算法執(zhí)行過程中,首先將區(qū)間下界向量的概率與P(Vm)相比較,若低于該值,說明該區(qū)間中不可能存在全局意義上最可靠最大流,可以不予考慮.

規(guī)則2(割集過濾規(guī)則) 設(shè)待劃分的區(qū)間上界子圖所對(duì)應(yīng)最小割集為c,則劃分后所有的合格子區(qū)間上界向量中都含有該最小割集c中的邊.

根據(jù)Ford-Fulkerson方法[15],從源點(diǎn)s到終點(diǎn)t可以傳輸?shù)淖畲罅髦礔max等于最小割集中邊的流量之和,若減少最小割集中邊的流量,其最大流也相應(yīng)降低.故對(duì)于待劃分區(qū)間劃分得到的子區(qū)間中,最小割集中的邊必須全部存在于合格子區(qū)間上界對(duì)應(yīng)的可能子圖中,該區(qū)間才可能存在滿足最大流的實(shí)例;否則,若至少有一條邊不存在于子區(qū)間上界中,則該區(qū)間上界子圖中必定存在一個(gè)割集的流量值小于Fmax,根據(jù)最大流最小割定理,其最大流小于Fmax,該子區(qū)間為不滿足最大流的區(qū)間,直接丟棄.

過濾規(guī)則的具體步驟如下:

2) 概率過濾.在算法的計(jì)算過程中,假設(shè)當(dāng)前求得的最可靠最大流分布為Vm,其概率值為P(Vm).對(duì)于待劃分的區(qū)間C=[lC,uC],首先計(jì)算區(qū)間下界對(duì)應(yīng)的概率值P(lC),若P(lC)

1.3 算法的實(shí)現(xiàn)

依據(jù)上述算法的基本描述,DF-SDBA算法具體偽代碼，其實(shí)現(xiàn)過程如下.

算法1 DF-SDBA算法

輸入:不確定圖G,源點(diǎn)s,終點(diǎn)t.

輸出:s-t最可靠最大流值Fmax,最可靠最大流分布Vm及其概率R.

InitR=0,Vm={0}, stackS;

Fmax=getMaxFlow(MSG(G),s,t);

S.push({(0,0,…,0|E|), (1,1,…,1|E|),?,I=0,j=0});

WHILESis not empty,

Get the first collectionC=[lC,uC] from the top ofS;

IFi

IFP(lC)

ELSE computeF(uC) andF(lC) of collectionC;

IFF(uC)

ELSE IFF(lC)≥Fmax, calculateP(lC), IFP(lC)>R, replaceRandVm;

ELSE, compute max-flowf=(f1,f2,…,f|E|) and min-cutc=(c1,c2,…,c|E|), then computeIc′based on rule 2 to divideCintoC1,C2,…,C0;S.push ({lC,uC,(f1,f2,…,f|E|),IC′,|IC′|,j=1})&& calculate the possibility ofC0, IFP(C0)>R, replaceRandVm.

Return (R,Vm)

1.4 算法正確性的證明

定理1 假設(shè)不確定圖G中所有可以傳遞最大流Fmax的子圖空間概率過濾和割集過濾后,被劃分成r個(gè)互不相交的閉合區(qū)間C1,C2,…,Cr,其中Ci=[αi,βi],αi=(αi1,…,αi|E|)為區(qū)間下界所對(duì)應(yīng)的子圖,則這r個(gè)下界子圖中必存在不確定圖G的一個(gè)s-t的最可靠最大流.

證明 主要需要證明概率過濾和割集過濾不會(huì)丟失最可靠最大流分布.

1) 概率過濾的正確性證明.在區(qū)間劃分過程中,首先計(jì)算狀態(tài)區(qū)間下界分布的概率值,若其概率值小于當(dāng)前最可靠最大流分布的概率值,則該區(qū)間直接丟棄,因?yàn)樵搮^(qū)間滿足最大流的可能子圖實(shí)例的概率和小于當(dāng)前的最可靠最大流分布.假設(shè)狀態(tài)空間Cj=[lCj,uCj]為任一狀態(tài)空間,當(dāng)前求出的最可靠最大流分布為Vm,對(duì)應(yīng)的概率值為P(Vm).若P(lCj)P(Vm).由于P(lCj)P(Vm)相矛盾,即使用概率過濾的DF-SDBA算法可以求出最可靠最大流分布.

定理1表明使用概率過濾和割集過濾的算法DF-SDBA不會(huì)漏解,保證可以得到不確定圖G的s-t最可靠最大流分布,從理論上證明了算法的正確性.

2 實(shí)驗(yàn)

為了驗(yàn)證所提出算法的性能,本文進(jìn)行了一系列的實(shí)驗(yàn),實(shí)驗(yàn)平臺(tái)為一臺(tái)Intel Core的PC機(jī)(CPU i3-2120,3.3 GHz,內(nèi)存4 GB,64位Windows 7操作系統(tǒng)),算法采用Visual C++實(shí)現(xiàn).實(shí)驗(yàn)中采用文獻(xiàn)[14]中的數(shù)據(jù)集,具體分為以下2種情況:

1) 使用NETGEN生成器[16]產(chǎn)生V6A10,V8A14,V10A18,V12A22,V14A26,V16A34共6組有向圖,其中,VnAm表示有n個(gè)頂點(diǎn)、m條邊組成的圖,圖中邊的容量與對(duì)應(yīng)概率滿足均勻分布,選擇任意2點(diǎn)之間簡(jiǎn)單路徑數(shù)量最多的頂點(diǎn)作為起點(diǎn)和終點(diǎn),保證s到t有盡可能多的路徑方案.

3) 實(shí)驗(yàn)采用文獻(xiàn)[11]中中國(guó)臺(tái)灣電力傳輸網(wǎng)絡(luò)(TEPN)作為實(shí)際數(shù)據(jù)集.實(shí)驗(yàn)過程中,使用10個(gè)不同的隨機(jī)數(shù)種子從文獻(xiàn)[11]中的100個(gè)元件中隨機(jī)取得58個(gè)元件，構(gòu)成TEPN網(wǎng)絡(luò)中的1～58條邊.由于每個(gè)元件有多個(gè)容量狀態(tài),取其最大的容量狀態(tài)和其概率值作為邊的狀態(tài)信息,其源點(diǎn)s是屏東縣第三核電站,匯點(diǎn)t是臺(tái)北市.

實(shí)驗(yàn)1 圖的規(guī)模對(duì)算法的影響.

從圖1(a)中可以看出,隨著邊數(shù)的增加,2種算法的運(yùn)行時(shí)間增大,但增長(zhǎng)速率有較大差異.SDBA算法需要處理更多的子區(qū)間,導(dǎo)致其時(shí)間開銷隨著網(wǎng)絡(luò)規(guī)模增大急劇增長(zhǎng);而DF-SDBA算法有效地減少了劃分區(qū)間的數(shù)量,顯著地提高了算法的性能,其時(shí)間開銷隨著網(wǎng)絡(luò)規(guī)模的增加速度要緩慢很多.從圖1(b)中可以看出,隨著邊數(shù)的增加,2種算法需要的內(nèi)存消耗呈現(xiàn)出上升趨勢(shì);而DF-SDBA算法需要消耗的內(nèi)存略多,其需要存儲(chǔ)更多的概率值和割集等信息.從總體來看,通過空間換時(shí)間,DF-SDBA算法獲得了很好的時(shí)間性能,尤其隨著網(wǎng)絡(luò)規(guī)模的增大,算法時(shí)間性能更加凸顯.

(a) 運(yùn)行時(shí)間與邊數(shù)量的關(guān)系

(b) 內(nèi)存消耗與邊數(shù)量的關(guān)系

實(shí)驗(yàn)2 圖的稠密度對(duì)算法的影響.

從圖2中可以看出,隨著圖稠密度的增加,2種算法時(shí)間開銷也不斷增加,主要原因是圖的稠密度直接影響狀態(tài)空間的大小,圖稠密度越高,狀態(tài)空間越多,滿足最大流的分布數(shù)量越多,算法需要迭代的次數(shù)也隨之增加, 導(dǎo)致算法運(yùn)行時(shí)間t′變長(zhǎng);隨著稠密度的增加,DF-SDBA算法時(shí)間開銷的增長(zhǎng)速度明顯小于SDBA算法,這是由于DF-SDBA算法高效地過濾掉概率值較小的區(qū)間和不滿足最大流的區(qū)間,避免了不必要的劃分,減少了算法迭代的次數(shù),提升了算法的性能.

圖2 不同稠密度下2種算法的性能

實(shí)驗(yàn)3 TEPN實(shí)驗(yàn)對(duì)比.

表1是SDBA和DF-SDBA算法在TEPN數(shù)據(jù)集上運(yùn)行的結(jié)果,平均時(shí)間是算法在10個(gè)不確定圖上運(yùn)行時(shí)間的平均值.從表1可以看出,DF-SDBA算法明顯優(yōu)于SDBA;但相對(duì)于稠密度較高的圖,TEPN數(shù)據(jù)集性能提升較少,這是由于TEPN為稀疏圖,割集中的邊較少,割集過濾效果并不明顯,導(dǎo)致性能提升較少.

表1 TEPN實(shí)驗(yàn)對(duì)比 ms

3 結(jié)語(yǔ)

本文提出了基于概率和割集雙過濾的狀態(tài)空間劃分改進(jìn)算法DF-SDBA,用于解決最可靠最大流問題.DF-SDBA算法使用概率過濾篩選掉區(qū)間下界分布的概率值小于當(dāng)前最可靠最大流分布的區(qū)間,使用割集過濾去掉不滿足最大流的區(qū)間,減少了劃分的區(qū)間數(shù)量和算法的迭代次數(shù).實(shí)驗(yàn)結(jié)果表明,相對(duì)于SDBA算法,DF-SDBA算法有效地減少了處理子區(qū)間的數(shù)量,加快了算法的收斂速度,具有顯著的性能優(yōu)勢(shì).

本文的下一步工作將嘗試使用多機(jī)并行機(jī)制,進(jìn)一步提高算法的性能,此外，研究實(shí)際應(yīng)用中可能出現(xiàn)的動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)渥兓葐栴}.

References)

[1]Hintanen P, Toivonen H, Sevon P. Fast discovery of reliable subnetworks [C]//InternationalConferenceonAdvancesinSocialNetworksAnalysisandMining. Odense, Denmark, 2010: 104-111.

[2]Hintsanen P. The most reliable subgraph problem [C]//EuropeanConferenceonPrinciplesandPracticeofKnowledgeDiscoveryinDatabases. Crete, Greece, 2007: 471-478.

[3]鄒兆年,李建中,高宏,等.從不確定圖中挖掘頻繁子圖模式[J].軟件學(xué)報(bào),2009,20(11):2965-2976. Zou Zhaonian, Li Jianzhong, Gao Hong, et al. Mining frequent subgraph patterns from uncertain graphs [J].JournalofSoftware, 2009, 20(11): 2965-2976. (in Chinese)

[4]張碩,高宏,李建中,等.不確定圖數(shù)據(jù)庫(kù)中高效查詢處理[J].計(jì)算機(jī)學(xué)報(bào),2009,32(10):2066-2079. Zhang Shuo, Gao Hong, Li Jianzhong, et al. Efficient query processing on uncertain graph databases [J].ChineseJournalofComputers, 2009, 32(10): 2066-2079. (in Chinese)

[5]Yuan Ye, Wang Guoren, Chen Lei, et al. Efficient subgraph similarity search on large probabilistic graph databases [C]//InternationalConferenceonVeryLargeDatabase. Istanbul, Turkey, 2012: 800-811.

[6]張海杰,姜守旭,鄒兆年.不確定圖上的高效top-k近鄰查詢處理算法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1885-1896. Zhang Haijie, Jiang Shouxu, Zou Zhaonian. An efficient algorithm for top-k proximity query on uncertain graphs [J].ChineseJournalofComputers, 2011, 34(10): 1885-1896. (in Chinese)

[7]張應(yīng)龍,李翠平,陳紅,等.不確定圖上的kNN查詢處理[J].計(jì)算機(jī)研究與發(fā)展,2011,48(10):1850-1858. Zhang Yinglong, Li Cuiping, Chen Hong, et al. K-nearest neighbors in uncertain graph [J].JournalofComputerResearchandDevelopment, 2011, 48(10): 1850-1858. (in Chinese)

[8]Rasteiro D D M L, Anjo A J B. Optimal paths in probabilistic networks [J].JournalofMathematicalSciences, 2004, 120(1): 974-987.

[9]Alexopoulos C. A note on state-space decomposition methods for analyzing stochastic flow networks[J].IEEETransactionsonReliability, 1995, 44(2): 354-357.

[10]Jane Chin-Chia, Laih Yih-Wenn. A practical algorithm for computing multi-state two-terminal reliability [J].IEEETransactionsonReliability, 2008, 57(2): 295-302.

[11]Jane Chin-Chia, Laih Yih-Wenn. Computing multi-state two-terminal reliability through critical arc states that interrupt demand [J].IEEETransactionsonReliability, 2010, 59(2): 338-345.

[12]Ramirez-Marquez J E, Coit D W. A monte-carlo simulation approach for approximating multi-state two terminals reliability [J].ReliabilityEngineering&SystemSafety, 2005, 87(2): 253-264.

[13]Rocco C M, Muselli M. Approximate multi-state reliability expressions using a new machine learning technique [J].ReliabilityEngineering&SystemSafety, 2005, 89(3): 261-270.

[14]蔡偉,張柏禮,呂建華.不確定圖最可靠最大流算法研究[J].計(jì)算機(jī)學(xué)報(bào),2012,35(11):2371-2380. Cai Wei, Zhang Baili, Lü Jianhua. Algorithms of the most reliable maximum flow on uncertain graph [J].ChineseJournalofComputers, 2012, 35(11): 2371-2380. (in Chinese)

[15]Ford L R, Fulkerson D R.Flowsinnetworks[M]. Princeton: Princeton University Press, 1962.

[16]Klingman D, Napier A, Stutz J. NETGEN: a program for generating large scale capacitated assignment, transportation and minimum cost flow network problems [J].ManagementScience, 1974, 20(5): 814-821.

Improved algorithm of most reliable maximum flow on uncertain graph

Zhang Baili1,2Yang Juan1Lü Jianhua1,2Tian Wei3

(1School of Computer Science and Engineering, Southeast University, Nanjing 211189, China)(2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China)(3Nanjing Hongyi Electric Automation Technology Co., Ltd, Nanjing 210039, China)

For the most reliable maximum flow problem (MRMF), the performance of the space decomposition-based algorithm (SDBA) decreases rapidly with the increase in size and density of the graph. The probability filter and the cut-set filter are therefore used to solve this problem and the double filter space decomposition-based algorithm (DF-SDBA) is proposed. First, the probability constraint is used to filter out all intervals in the process of space decomposition. For each interval to be processed, the DF-SDBA algorithm filters off the intervals of which the probability is smaller than the current maximum flow to effectively reduce the number of iterations. Then the cut-set constraint is applied to the unspecified intervals. It computes the maximum flow in the upper bound of the unspecified interval, meanwhile the minimum cut-sets are obtained. Based on the rule that all the edges in the cut-sets must exist in the upper bound of each interval, the unspecified intervals are filtered out. The experimental results show that the DF-SDBA algorithm can not only effectively reduce the number of the intervals in need of dividing, but also reduce the impact of network size and density compared with the SDBA algorithm. The DF-SDBA algorithm has significant performance advantages and improves the applicability of algorithms.

uncertain graph; maximum flow; flow reliability; minimum cut

10.3969/j.issn.1001-0505.2015.02.008

2014-09-17. 作者簡(jiǎn)介: 張柏禮(1970—)，男，博士，副教授，bailey_zhang@163.com.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61300200，61232007，61073059).

張柏禮,楊娟,呂建華,等.基于不確定圖的最可靠最大流的改進(jìn)算法[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2015,45(2):241-246.

10.3969/j.issn.1001-0505.2015.02.008

TP311

A

1001-0505(2015)02-0241-06