[發明專利]一種分布式計算圖節點相似度的方法

有效

• 申請號: 201410323742.8
• 申請日: 2014-07-09
• 公開（公告）號: CN104158840B
• 公開（公告）日: 2017-07-07
• 發明（設計）人: 申德榮;馮朔;寇月;聶鐵錚;王振華;于戈
• 申請（專利權）人: 東北大學
• 主分類號: H04L29/08
• 分類號: H04L29/08;G06F17/30;H04L12/58
• 代理公司: 沈陽東大知識產權代理有限公司21109
• 代理人: 梁焱

技術領域

本發明屬于計算機數據挖掘領域，具體涉及一種分布式計算圖節點相似度的方法。

背景技術

隨著圖結構的廣泛應用，計算兩節點相似度已經成為一種基本的圖操作方法。例如，針對一個社交網絡所建立的圖模型中，節點代表個人賬號，節點之間的邊代表個人賬號之間的關系，節點相似度可表述成為兩個賬號的關聯程度，其在探測相似人群以及朋友推薦中有重要應用；又如，針對引文網絡所建立的圖模型中，節點代表文章，節點之間的邊代表文章之間的引用關系，而節點相似度可應用于文章分類及相似文章推薦。

目前，已有多種計算節點相似度的方法，其中SimRank方法因具有高準確性而被廣泛應用。傳統SimRank方法計算復雜性很高，計算方法如下：對于給定的有向圖，令s(a，b)表示節點a和b之間的相似性，則這兩個節點的SimRank相似度如下：

1)若a＝b，則s(a，b)＝1；2)若a≠b，則s(a，b)的計算公式如下：

其中，C為衰減因子，是介于0，1之間的常數；|I(a)|和|I(b)|分別為節點a和b的入鄰居個數；I_i(a)表示節點a的第i個入鄰居，I_j(b)表示節點b的第j個入鄰居。

在初始化階段，若a≠b，則R₀(a，b)＝0，否則R₀(a，b)＝1，然后按下式進行迭代： 其中R_k+1(a，b)表示節點a和b之間的第k+1次迭代的SimRank相似度；在每次迭代過程中，依次算出所有節點對之間的相似度后進入下一次迭代，在迭代計算次后，可得R_k(a，b)為節點對(a，b)的SimRank相似度，其中ε為用戶所能容忍的誤差大小；

由公式可知，相同或相似節點的出鄰居節點也具有高相似性，在迭代計算節點對相似度時，需通過節點對的入鄰居的相似度對該節點對相似度進行更新，則s(a，b)＝lim_k→∞R_k(a，b)。可以看出，該方法計算復雜性過高，且在計算過程中需等待前一次迭代計算全部完成后才能進行下一次迭代計算。

為降低傳統SimRank計算復雜度，人們提出了多種SimRank優化計算方法，例如：基于局部和的SimRank優化計算方法、基于隨機游走的SimRank計算方法以及基于GPU的SimRank 并行計算方法等。其中基于隨機游走的SimRank優化計算方法中，節點a和b之間SimRank相似度計算公式為s(a，b)＝∑_{t：(a，b)→m}P[t]C^l(t)，其中t表示分別從節點a和b出發，沿入邊方向游走，經過相同步數，首次在節點m相遇的兩條路徑，P[t]表示該相遇發生的概率；l(t)表示路徑的長度；并稱這兩條路徑形成了一次從節點對(a，b)到節點m的首遇游歷(tour)，P[t]C^l(t)為游歷值，同樣稱l(t)為該游歷的長度；

上述的多種SimRank優化計算方法計算復雜性均達到o(Kn⁴)，其中K表示迭代計算次數，n表示圖中節點個數。對于大規模圖數據，如大型社交網絡、網頁數據以及引文信息網絡，這些網絡中節點的數量和邊的數量異常龐大，由于這些計算方法僅在單個計算機中進行處理，而單個計算機CPU計算能力有限，導致計算時間過長。據實驗測試，傳統單機方法在2.1GHz英特爾奔騰處理器且1G內存的實驗環境中，處理10000個節點的圖數據需要的計算時間大致46個小時。

基于隨機游走的SimRank優化計算方法在計算節點對(a，b)相似度時，需得到所有以(a，b)為端點的路徑，因此可在分布式環境中對其實現：以節點對為劃分單元對相似度計算任務進行劃分，每臺計算機處理計算多個節點對的相似度大小。然而這種計算方法復雜性過高，且需多次圖數據讀取操作。

發明內容

針對現有技術存在的不足，本發明提供一種分布式計算圖節點相似度(DcSimRank)的方法。

本發明的技術方案：

一種分布式計算圖節點相似度的方法，包括如下步驟：

步驟1：采用主從(master-slave)模式搭建分布式計算平臺；

搭建的分布式環境中共有N臺計算機，將其中一臺計算機作為主(master)計算機，其余N-1臺計算機均作為子(slave)計算機；

步驟2：主計算機讀入現有的對象數據，建立圖模型并發送給分布式計算平臺中的每臺子計算機；