不確定圖上的最大流研究.pdf

1、近年來，在多種科學(xué)領(lǐng)域，大量數(shù)據(jù)都可以轉(zhuǎn)化為不確定圖，例如：社會網(wǎng)絡(luò)、蛋白質(zhì)交互網(wǎng)絡(luò)等。通過不確定圖，可以形象地看到信息間的結(jié)構(gòu)關(guān)系，也可以從節(jié)點獲得數(shù)據(jù)信息。如何從現(xiàn)有的圖數(shù)據(jù)結(jié)構(gòu)中挖掘出對象的結(jié)構(gòu)特征、整體趨勢、模式等知識，是一個有實際意義和學(xué)術(shù)價值的問題。在不確定圖數(shù)據(jù)挖掘領(lǐng)域中，已經(jīng)有了初步研究，包括頻繁子圖挖掘、最大團(tuán)挖掘、近鄰?fù)诰?、最短路徑、可達(dá)性等等，但是對于不確定圖的探索才剛剛開始，還有很多問題需要研究。本文的最大流問題

2、，就是在不確定圖的基礎(chǔ)上，引出的新問題。
　　本文提出了不確定圖上的兩個新問題：最大最大流概率和最大概率最大流。
　　1）對于最大最大流概率，本文提出了基于蘊含子圖空間分解計算模型的MMFP精確算法，并且給出了優(yōu)化算法，同時也證明了該問題是＃P-Hard的；然后基于切諾夫邊界提出了采樣近似算法，同時證明近該算法是無偏估計的。最后通過實驗對MMFP算法進(jìn)行時間比較，和對近似算法進(jìn)行誤差分析。
　　2）對于最大概率最大流，