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

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

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