[發(fā)明專利]一種分布式計算SimRank單源節(jié)點相似度的方法和裝置

有效

• 申請?zhí)枺?/td>: 202011623372.1
• 申請日: 2020-12-30
• 公開（公告）號: CN112667402B
• 公開（公告）日: 2021-09-21
• 發(fā)明（設(shè)計）人: 王越
• 申請（專利權(quán)）人: 深圳計算科學研究院
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F16/901;G06F16/903
• 代理公司: 深圳市智勝聯(lián)合知識產(chǎn)權(quán)代理有限公司 44368
• 代理人: 齊文劍

本申請?zhí)峁┝艘环N分布式計算SimRank單源節(jié)點相似度的方法和裝置，所述方法包括：獲取有向圖G，并生成對應于所述有向圖G的節(jié)點集；對所述節(jié)點集進行采樣，獲取所述節(jié)點集內(nèi)每個節(jié)點的采樣結(jié)果，并依據(jù)所述采樣結(jié)果生成對應于所述節(jié)點集的森林模型；對所述森林模型進行隨機采樣，確定對應于所述節(jié)點集內(nèi)每個節(jié)點的第一入鄰居節(jié)點和第二入鄰居節(jié)點；依據(jù)所述第一入鄰居節(jié)點和所述第二入鄰居節(jié)點確定所述節(jié)點集內(nèi)每個節(jié)點對應的值；依據(jù)所述節(jié)點集內(nèi)每個節(jié)點對應的值生成目標節(jié)點的相似度值；通過采用分布式的方式建立森林，從而計算離線索引，每一輪的森林在計算過后可以刪除，并不需要離線保存；通過本方法的設(shè)置可以保證計算結(jié)果精度。

技術(shù)領(lǐng)域

本申請涉及數(shù)據(jù)處理領(lǐng)域，特別是一種分布式計算SimRank單源節(jié)點相似度的方法和裝置。

背景技術(shù)

一個有向圖由G(V,E)表示，其中V表示結(jié)點的集合，E表示邊的集合。對于任意節(jié)點u∈V，I_u表示任意節(jié)點u的入鄰居的集合，即 I_u＝{u:(u,u)∈E,u∈V}，O_u表示點u的出鄰居的集合，即O_u＝{u:(u,u)∈E,u∈V}。

SimRank是一種在圖中計算節(jié)點相似度的一種度量方式，SimRank是一種基于網(wǎng)頁鏈接結(jié)構(gòu)來評估圖中任意兩個對象(結(jié)點)之間的相似度模型，其背后的思想為：

每個節(jié)點與其自身的相似度為1；

兩個節(jié)點的節(jié)點的相似度取決去它們鄰居節(jié)點的相似度。

SimRank的定義是遞歸的，任意兩個節(jié)點u和v的相似度定義如下：

其中，參數(shù)c∈(0,1)為衰減因子(通常設(shè)置為0.6或0.8)，用來控制節(jié)點u和節(jié)點v的相似度取決于其鄰居相似度的程度。

基于SimRank的節(jié)點相似度度量方式，其中一個重要問題就是計算單源節(jié)點相似度，即計算節(jié)點u和圖中剩余節(jié)點(Vu)的相似度。

該問題定義如下：

給定一個節(jié)點u∈V和容錯值ε，計算節(jié)點u到其余節(jié)點的相似度，使得對于任意節(jié)點v∈V，

其中，表示算法給出的估計值，s(u,v)表示SimRank的真實值。也就是說，計算給出的估計值與真實值的誤差在ε的范圍內(nèi)。

而最接近現(xiàn)有技術(shù)方案為基于Spark計算系統(tǒng)，數(shù)據(jù)用RDD(ResilientDistributed Dataset，彈性分布式數(shù)據(jù)集)進行存儲和計算。Spark是專為大規(guī)模數(shù)據(jù)處理而設(shè)計的快速通用的計算引擎；該方案有兩個階段：離線索引和在線查詢。在離線索引階段中，建立索引。在查詢過程中，利用已經(jīng)建立好的索引來進行對任意節(jié)點的SimRank單源相似度的查詢。在離線階段，該方案首先構(gòu)建一個線性系統(tǒng)，然后通過迭代的方式解該線性系統(tǒng)，該線性系統(tǒng)的解作為離線索引，這個線性系統(tǒng)的構(gòu)建是近似的。在在線階段，利用該索引，該方案使用Spark來模擬隨機游走，最終得到單源節(jié)點相似度。但并不能保證計算結(jié)果的精確性和正確性，即給定容錯值ε，該方案并不能保證計算相似度的結(jié)果與真實值的誤差在ε之內(nèi)，因此影響基于相似度的應用(推薦系統(tǒng)，鏈路預測等)的結(jié)果質(zhì)量；雖然該方案是分布式算法，但方案并不能保證并行可擴展性，即該方案的計算開銷并不能隨著計算資源的上升而減少，降低了其可用性，即該方案的分布式計算并不能保證效率上的提升。

針對該問題，我們研究在分布式環(huán)境中(shared-nothing，即不同的機器不能共享內(nèi)存)的計算方法，即一個大圖不能被單機所處理，而被分割在集群中不同的機器中的情況，提出一種分布式計算SimRank單源節(jié)點相似度的方法和裝置。

發(fā)明內(nèi)容