[發明專利]一種圖計算方法及引擎

在審

• 申請號: 201410324671.3
• 申請日: 2014-07-09
• 公開（公告）號: CN104063507A
• 公開（公告）日: 2014-09-24
• 發明（設計）人: 王緒剛;吳桐;宋磊;張銳
• 申請（專利權）人: 時趣互動（北京）科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京方韜法業專利代理事務所 11303
• 代理人: 遆俊臣

技術領域

本發明涉及圖計算領域，尤其是涉及一種圖計算方法及引擎。

背景技術

圖計算(graph computation)對于關系構建、用戶群分析和發現、屬性傳播等有很重要的作用。在大數據時代，圖的規模大到一定程度后，單機就很難解決大規模的圖計算了。因此，進行大規模數據的圖算法開發和調試具有重要意義。目前比較成熟的方案有Graphx和GraphLab。其中GraphLab項目的一個分支是GraphChi，該框架能夠在單機上完成大數據的圖計算。

GraphChi可以在個人計算機上高效的進行大規模的圖計算，它有自己原創的從硬盤獲取圖數據的優化算法，并且支持流圖(streaming graph)更新以及在計算中改變圖的結構。

GraphChi在進行大規模圖計算的時候，將圖分成了不同的分片，這些分片可以在內存中并行處理，分片的數據更新通過連續寫入來實現，以最小化硬盤上的隨機操作，合理使用機器內存。

GraphChi利用個人計算機上的海量硬盤，將圖數據存儲在硬盤上，為提升硬盤的數據存取效率，GraphChi使用了PSW(Parallel Sliding Window)算法來解決這一關鍵的性能提升問題。PSW通過source shards對1個分片中所有的vertex進行排序，這樣每個分片本質上都被分割成由vertex組成的塊，同時這些vertex又會與其它分片關聯。

GraphChi和GraphLab一樣也是基于vertex-centric模型來實現的，并行且異步(邊上數據發生的變化對后續計算是立即可見的)。

GraphChi通過vertex拆分來實現并行，設置一個master vertex，多個mirror vertex，各mirror vertex處理自己分內的數據，最終由master vertex進行匯總，然后master vertex將匯總后的數據對mirror vertex進行更新，同時也更新相關邊上的數據。

GraphChi的執行模型為“Gather-Apply-Scatter”，具體介紹如下：

每個vertex每一輪迭代經過“Gather-Apply-Scatter”三個階段。

(1)Gather階段

計算相關的vertex從鄰接vertex和自身收集數據，這一階段，vertex和邊上的數據都是只讀的。

(2)Apply階段

mirror vertex將Gather階段計算的結果發給master vertex，由其進行匯總及進一步的計算，然后更新master vertex的數據，并同步到mirror vertex中。這一階段，vertex的數據可以修改，邊上的數據不可以修改。

(3)Scatter階段

vertex數據更新完成之后，更新邊上的數據，這一階段，邊上的數據是可寫的，vertex上的數據是只讀的。

并行計算的同步通過master vertex和mirror vertex來實現，mirror vertex相當于每個vertex對外的一個接口人，這樣就把數據通信抽象成了vertex的數據交換行為。

雖然GraphChi能夠實現在個人計算機上進行大規模的圖計算，但仍存在一些不足和缺陷：如GraphChi無建立索引模塊，不支持自定義圖計算的拓撲圖，不支持插件的熱插拔等。因此，上述現有的圖計算方法及引擎在使用上仍存在有不便與缺陷，而亟待加以進一步改進。

發明內容

本發明的目的是提供一種可以獲得去流行、強關系的結果的圖計算方法。

為實現上述目的，本發明采用如下技術方案：

一種圖計算方法，主要包括以下步驟：A.對圖的原始關系數據進行索引，獲得索引數據，所述圖的頂點和邊上對應所述的索引數據；B.選擇所述圖的一個或多個頂點為起始節點，進行廣度優先或深度優先的多步游走，獲得包括用于候選的多個結束節點的游走拓撲圖，基于廣度優先或深度優先的圖游走算法、根據游走路徑中參與的頂點和邊對應的索引數據計算所述起始節點到達所述結束節點的到達概率；C.對計算出的所述到達概率進行排序。

進一步地，所述步驟B中對到達概率的計算包括兩次取對數方式的降權操作。

進一步地，所述到達概率reach_prob的計算公式為：