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

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

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

【部分圖文】：

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

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

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

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

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

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

圖３－３：隨機(jī)圖的平均誤差隨／的變化?

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

本文編號(hào)：4003694