發(fā)布時間：2024-07-08 18:30

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

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

【學位級別】：碩士

【部分圖文】：

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

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

圖３－１：?—個路徑復用的例子??

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

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

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

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

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

本文編號：4003694