不確定圖上期望最短距離的研究與應(yīng)用.pdf

1、在現(xiàn)實(shí)世界中,許多領(lǐng)域中的數(shù)據(jù)都可以用“圖”來(lái)表示。與傳統(tǒng)的關(guān)系數(shù)據(jù)相比,圖數(shù)據(jù)有著更大的靈活性。而由于數(shù)據(jù)本身的不精確、獲取數(shù)據(jù)的實(shí)驗(yàn)手段的局限等因素的影響,不確定性是廣泛存在的,例如:蛋白質(zhì)交互網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等。以蛋白質(zhì)交互網(wǎng)絡(luò)為例,由于對(duì)蛋白質(zhì)之間交互的檢測(cè)不夠精確,在蛋白質(zhì)網(wǎng)絡(luò)中通常認(rèn)為交互是以一定概率存在的。
　　本文研究了不確定圖上的最短距離問(wèn)題,提出了期望最短距離的概念,證明了該問(wèn)題不存在多項(xiàng)式時(shí)間的算法。而為了解決

2、該問(wèn)題,本文使用了隨機(jī)采樣技術(shù)獲取不確定圖的一些可能世界,在每個(gè)可能世界上計(jì)算給定兩個(gè)頂點(diǎn)有窮的最短距離,最后根據(jù)多次隨機(jī)采樣的結(jié)果計(jì)算出平均值作為期望最短距離的估計(jì)值。為提高計(jì)算效率,本文使用了過(guò)濾條件來(lái)加快隨機(jī)采樣。在此基礎(chǔ)上,又提出了一種基于對(duì)稱(chēng)變量隨機(jī)采樣的近似算法,并證明了與直接隨機(jī)采樣相比,該方法在不增加時(shí)間開(kāi)銷(xiāo)的同時(shí)能減小采樣方差。通過(guò)真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)表明,本文提出的算法在時(shí)間開(kāi)銷(xiāo)和采樣方差上均明顯好于直接隨機(jī)采樣。