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

有效

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

1.一種分布式計算圖節點相似度的方法，其特征在于：包括如下步驟：

步驟1：采用主從模式搭建分布式計算平臺；

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

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

主計算機以對象為節點，對象間關系為節點之間的邊，建立圖模型并將該圖模型發送給分布式環境中每臺子計算機；

步驟3：以該圖模型的所有節點為任務劃分對象，主計算機進行任務劃分，并將劃分后的各子任務及迭代次數分配給各子計算機；子任務由所劃分的不同節點構成；子任務中的不同節點，稱作任務節點；

步驟4：根據接收的任務，子計算機計算其各任務節點分別傳遞給圖模型中的各個節點對的相似度增量計算值；相似度增量計算值為不考慮所得到的游歷是否為首遇游歷時，任務節點傳遞給對應節點對的相似度增量；

對于單個任務節點m，對應的子計算機首先構建該節點的相似度增量計算值矩陣，大小為n×n，并將其中每個元素初始化為0，該矩陣用于存放該節點傳遞給各相應節點對的相似度增量計算值；接下來采用廣度優先算法，以該節點m為根節點進行廣度優先搜索，將節點m在每一層所能到達的節點存儲在集合List_k(m)中，則有

List_k(m)＝{(j，P_k[m，j])}，k＝1，…，K (2)

其中List_k(m)表示以節點m為根節點，在第k層所能到達的圖節點；j代表圖中任意節點；P_k[m，j]表示從節點j出發，沿入邊方向，經k步游走到達節點m的概率，稱為節點m到節點j的路徑值；

以迭代方式計算該節點的相似度增量計算值，即List_k(m)根據List_k-1(m)計算得到，List_k(m)中每個元素根據式(3)進行更新，

P_k[m，j]＝∑_iP_k-1[m，I_i(j)]/|I(j)|，P₀[m，m]＝1，i＝1，2，…，|I(j)| (3)

根據公式(4)及集合List_k(m)，計算該節點m在各層傳遞給節點對(j，j′)的相似度增量計算值v′_m，k(j，j′)，其中j′為圖中任意節點；任務節點m所對應的子計算機將j′＝j時的相似度增量計算值v′_m，k(j，j′)發送給主計算機；將j′≠j時的相似度增量計算值v′_m，k(j，j′)通過公式(5)累加到相似度增量計算值矩陣中；

v′_m，k(j，j′)＝P_k[m，j]P_k[m，j′]C^k(4)

其中，v′_m，k(j，j′)表示節點m在第k層傳遞給節點對(j，j′)的相似度增量計算值，即節點對(j，j′)沿入邊方向經過k步游走，在節點m相遇的游歷值之和；C為衰減因子，是介于0，1之間的常數；

s′_m(j，j′)＝∑_kv′_m，k(j，j′)(5)

其中，s′_m(j，j′)表示該任務節點m帶給節點對(j，j′)的相似度增量計算值；

當迭代k＝K次以后，迭代停止，相似度增量計算值矩陣存放的即為節點m傳遞給各節點對的相似度增量計算值；

步驟5.主計算機計算各任務節點的偏移系數并分別發送給對應的各子計算機；偏移系數為用于對各任務節點的相似度增量計算值進行修正的系數；

在所有子計算機完成步驟4后，主計算機根據接收到的每個子計算機發送的其各任務節點傳遞給節點對(j，j′)，j′＝j時的相似度增量計算值v′_m，k(j，j′)，建立集合Set＝{({x′，k′，y′}，v′)}，其中x′和y′均表示任意圖節點，v′表示節點x′在第k′＝1，2，…，K次迭代對節點對(y′，y′)的相似度增量計算值v′_{x′，k′}(y′，y′)，并用Set(x′，k′，y′)表示集合Set對應的元素v′＝v′_x′，k′(y′，y′)；構建集合Sco＝{({x，k，y}，v)}，其中x和y均表示任意圖節點，v表示以節點x為起點，經過k步游走，在節點y發生首遇的游歷值之和v_x，k(y，y)，并用Sco(x，k，y)表示集合Sco對應的元素v＝v_x，k(y，y)；下面介紹集合Sco的更新方法：

以k＝1，2，…，K為迭代順序更新集合Sco，在第k-1次迭代計算Sco(x，k-1，y)全部完成后，才進行第k次迭代計算Sco(x，k，y)，其中單個元素Sco(x，k，y)計算方法如下：

A.若k＝1，則Sco(x，k，y)＝Set(x，k，y)，則轉去執行步驟C；否則執行步驟B；

B.Sco(x，k，y)通過從集合Sco中查找出元素Sco(x，k₁，p)與從集合Set中查找出元素Set(p，k₂，y)，且滿足k₁+k₂＝k，p為在集合Sco和集合Set中同時出現的節點，根據公式(6)計算得到偏差v″_x，k(y，y)，公式(6)如下：

$v_{x,k}^{\′\′}(y,y)=\underset{p}{\Σ}\underset{k_1+k_2=k}{\Σ}{v}_{x,k_1}(p,p)v_{p,k_2}^{\′}(y,y)---\left(6\right)$

再通過公式(7)計算得到Sco(x，k，y)，公式(7)如下：

$Sco(x,k,y)=\frac{\left(Set\right(x,k,y)-v_{x,k}^{\′\′}(y,y\left)\right)}{2}---\left(7\right)$

C.結束；

集合Sco更新完畢后，接下來通過公式(8)計算各個任務節點的偏移系數，

${\mathrm{\δ}}_y=\underset{x}{\Σ}\underset{k}{\Σ}Sco(x,k,y)---\left(8\right)$

δ_y為節點y的偏移系數，主計算機依據根節點的對應關系，將該偏移系數發送給相應的子計算機；

步驟6.子計算機接收到其各任務節點的偏移系數之后對本地各任務節點的相似度增量計算值進行修正，并將修正后的本地各任務節點的相似度增量進行求和后傳送給主計算機；

子計算機根據公式(9)對步驟4求得的本地相似度增量計算值進行修正，即

s(j，j′)＝∑_ys′_y(j，j′)(1-δ_y) (9)

其中s(j，j′)表示節點對(j，j′)的相似度，s_y′(j，j′)表示節點y傳遞給節點對(j，j′)的相似度增量計算值，其為不考慮所得到的游歷是否為首遇游歷的計算結果；δ_y表示任務節點y的偏移系數，其用于對任務節點y的相似度增量計算值進行修正；求和符號內s′_y(j，j′)(1-δ_y)整體表示節點y傳遞給節點對(j，j′)的相似度增量，為修正后的節點y對應矩陣中的記錄；

步驟7：根據從各子計算機接收的各節點的相似度增量，主計算機對圖模型中各節點對的相似度進行整合，最終得到圖模型中各個節點對的相似度；

主計算機接收到所有子計算機發送的各節點的相似度增量后，將對應節點對的相似度增量相加，得到每個節點對的相似度值，再將每個節點與其自身的相似度修正為1.0。