圖作為一種表達對象與對象之間抽象關(guān)系的非線性數(shù)據(jù)結(jié)構(gòu),具有更加一般化的表達能力,在我們現(xiàn)實生活中扮演者重要的角色。近年來,隨著互聯(lián)網(wǎng)、云計算、物聯(lián)網(wǎng)等技術(shù)的高速發(fā)展,數(shù)據(jù)增長的規(guī)模正在以前所未有的速度增加,“大數(shù)據(jù)”給各行各業(yè)帶來了很大的機遇和挑戰(zhàn),同時圖數(shù)據(jù)的規(guī)模也隨著個性化推薦、信息檢索、社交網(wǎng)絡(luò)分析等應(yīng)用的蓬勃發(fā)展變得越來越大。隨著圖數(shù)據(jù)規(guī)模的增大,人們發(fā)現(xiàn)龐大的圖數(shù)據(jù)中蘊含著巨大的商業(yè)價值,基于圖結(jié)構(gòu)的各種互聯(lián)網(wǎng)應(yīng)用在近些年來層出不窮,在這些應(yīng)用中,最典型和最基本的一類任務(wù)就是計算對象和對象之間的相似度。SimRank是一種非常流行的基于圖拓?fù)浣Y(jié)構(gòu)信息來衡量任意兩個對象之間相似程度的模型,其核心的思想為:一個對象應(yīng)該與自身最相似,如果兩個對象都被相似的對象所引用,那么這兩個對象也相似。然而,由于SimRank定義的遞歸依賴性,導(dǎo)致了SimRank計算的時空復(fù)雜度很大,圖數(shù)據(jù)規(guī)模的增大在另一方面也使得問題更加突出。在本文中,我們主要針對單源節(jié)點SimRank的計算,即給定一個查詢頂點,返回該節(jié)點與所有其他節(jié)點間的相似度,提出并實現(xiàn)了一種稱之為ProbeWalk的高度并行的算法。我...

【文章頁數(shù)】：77 頁

【學(xué)位級別】：碩士

【部分圖文】：

圖２－１：?ＳｉｍＲａｎｋ算法總結(jié)??

第二章相關(guān)工作??．１?ＳｉｍＲａｎｋ計算方法現(xiàn)狀??ＳｉｍＲａｎｋ作為衡量對象間相似度的一種指標(biāo)首次在２００２年由Ｊｅｌｌ和Ｗｉｄｏｍ??授在文獻［８］提出來以后，隨著其在網(wǎng)頁排名、孤立點檢測、協(xié)同過濾、近??查詢處理、網(wǎng)絡(luò)圖聚類等領(lǐng)域的成功應(yīng)用，ＳｉｍＲａｎｋ的計算速度便成為....

圖３－１：?—個路徑復(fù)用的例子??

較大的情況下的一個好方法。??圖３－１：?—個路徑復(fù)用的例子??圖３－１是一個“路徑復(fù)用”的例子，頂點ａ為一個待查詢頂點，路徑??＜?＞為算法隨機的一條相遇長度為１的隨機路徑，路徑＜?ａ，Ｚ？，ｅ，ｃ，／，／ｚ?＞??為相遇長度為２的隨機路徑，路徑＜?＞為相遇長度為３的隨機路??....

圖３－２：從頂點ａ和ｊ出發(fā)的相遇長度為３的匹配路徑??

高查詢算法的可用性便成為了一個問題。“路徑復(fù)用”策略便是解決查詢集合??較大的情況下的一個好方法。??圖３－１：?—個路徑復(fù)用的例子??圖３－１是一個“路徑復(fù)用”的例子，頂點ａ為一個待查詢頂點，路徑??＜?＞為算法隨機的一條相遇長度為１的隨機路徑，路徑＜?ａ，Ｚ？，ｅ，ｃ，／，／....

圖３－３：隨機圖的平均誤差隨／的變化?

?３３??以誤差也就越大。同樣的，在圖３－３中有著跟人造圖一樣的規(guī)律，總體的平均??誤差是隨著／指數(shù)減小的，有所不同的是，這兩個真實圖的折線比較接近，這??是因為這兩個數(shù)據(jù)集頂點數(shù)和邊數(shù)都比較接近從而在相同條件下誤差結(jié)果比較??接近。??１０“??????ｆｒ?■?Ｒａｎｄｏｍ?....

本文編號：4003694