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

有效

• 申請號: 202011623372.1
• 申請日: 2020-12-30
• 公開（公告）號: CN112667402B
• 公開（公告）日: 2021-09-21
• 發明（設計）人: 王越
• 申請（專利權）人: 深圳計算科學研究院
• 主分類號: G06F9/50
• 分類號: G06F9/50;G06F16/901;G06F16/903
• 代理公司: 深圳市智勝聯合知識產權代理有限公司 44368
• 代理人: 齊文劍

1.一種分布式計算SimRank單源節點相似度的方法，用于計算圖數據中SimRank單源節點相似度，其中，一個大圖G被分割并散布在不同的機器中，每一個計算節點存有大圖G的一個子圖；由于森林中的節點由圖G中的節點的構成，而圖G被分配到不同的機器，森林中的節點所在的機器就是相對應圖G中的節點所在的機器，其特征在于，包括：

獲取有向圖G，并生成對應于所述有向圖G的節點集；具體地，將所述有向圖G平均分割成的若干個節點，并依據所述節點生成所述節點集；對所述節點集進行采樣，獲取所述節點集內每個節點的采樣結果，并依據所述采樣結果生成對應于所述節點集的森林模型，其中，對所述節點集中的每個節點進行采樣生成所述每個節點對應的每個節點軌跡；根據所述每個節點軌跡對應的每個葉子結點生成所述森林模型；

對所述森林模型進行隨機采樣，確定對應于所述節點集內每個節點的第一入鄰居節點和第二入鄰居節點；

依據所述第一入鄰居節點和所述第二入鄰居節點確定所述節點集內每個節點對應的值，其中，所述值為對角校正矩陣中使用的每個值的對應節點的一個值；

依據所述節點集內每個節點對應的值生成目標節點的相似度值，其中，所述相似度值為任意節點u與所述有向圖G中其余節點的相似度的值。

2.根據權利要求1所述的方法，其特征在于，所述對所述節點集中的每個節點進行采樣生成所述每個節點對應的每個節點軌跡的步驟，包括：

在所述節點內獲取當前采樣節點m；

在所述當前采樣節點m對應的入鄰居節點集合中隨機采樣對應于所述當前采樣節點m的一個入鄰居節點m₁，并將所述入鄰居節點m₁確定為所述當前采樣節點m的父節點；

在所述父節點對應的入鄰居節點集合中持續進行隨機采樣，直至所述入鄰居節點集合為空集時，生成所述當前采樣節點m的節點軌跡。

3.根據權利要求1所述的方法，其特征在于，所述依據所述第一入鄰居節點和所述第二入鄰居節點確定所述節點集內每個節點對應的值的步驟，包括：

在所述節點集內每個節點中獲取一個節點v_n，根據所述節點v_n對應的第一入鄰居節點和第二入鄰居節點，依據所述第一入鄰居節點和所述第二入鄰居節點確定所述節點v_n的值；

當在所述節點集內每個節點中的所有節點均確定時，生成所述節點集內每個節點對應的值。

4.根據權利要求3所述的方法，其特征在于，所述在所述節點集內每個節點中獲取一個節點v_n，根據所述節點v_n對應的第一入鄰居節點和第二入鄰居節點，依據所述第一入鄰居節點和所述第二入鄰居節點確定所述節點v_n的值的步驟，包括：

依據所述節點v_n獲取V.cnt值，其中，在初始時，所述V.cnt值為0；

對所述節點v_n進行N輪隨機采樣，在所述N輪隨機采樣的每一輪隨機采樣中，通過在所述節點v_n對應的入鄰居節點集合中隨機采樣得到第一入鄰居節點和第二入鄰居節點；

獲取所述第一入鄰居節點對應的第一ID信息以及獲取所述第二入鄰居節點對應的第二ID信息；其中，在所述第一ID信息與所述第二ID信息相同時，所述節點v_n對應的所述V.cnt值增加1；

當所述節點v_n完成N輪隨機采樣時，依據所述V.cnt值生成所述節點v_n對應的值。

5.根據權利要求1所述的方法，其特征在于，所述依據所述節點集內每個節點對應的值生成目標節點的相似度值的步驟，包括：

依據所述節點集內每個節點對應的所述值生成對角校正矩陣D；

對所述對角校正矩陣D進行至少包括三次迭代運算生成所述目標節點的所述相似度值，其中，所述相似度值為所述目標節點與所述節點集內的其余節點之間的相似度值。