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

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

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