Graph Compute：圖演算法

功能介紹

圖計算服務GraphCompute新增圖演算法功能，基於當前服務的資料進行演算法執行，方便使用者快速進行全圖資料的分析。只需要開通圖計算服務執行個體，即可同時擁有高效能圖資料的查詢分析一體化引擎。相比業界方案，圖計算服務方案更便捷，無需額外自營運資料鏈路，讓資料流轉更高效。

本期重點開放3個核心圖演算法，其他經典圖演算法持續開放中。

演算法介紹

1）中心性演算法 PageRank

PageRank演算法是計算網頁排名的經典演算法。輸入是一個有向圖G，其中頂點表示網頁。如果存在網頁A到網頁B的連結，則存在串連A到B的邊。

演算法的基本原理如下：

• 初始化：點值表示PageRank的rank值（DOUBLE類型）。初始時，所有點取值為1/TotalNumVertices。

• 迭代公式：PageRank(i)=0.15/TotalNumVertices+0.85*sum。其中sum為所有指向i點的點（設為j）PageRank(j)/out_degree(j)的累加值。

2) 社區發現 Weakly Connected Components

弱連通分量（WCC）演算法在有向圖和無向圖中尋找連通節點集。如果兩個節點之間存在路徑，則表示兩個節點已串連。相互串連的所有節點的集合形成一個組件。與強串連組件（SCC）相反，不考慮兩個節點之間路徑上的關係方向。例如，在有向圖（a）→（b）中，即使沒有向關係（b）→（a）， a和b也會在同一個分量中。

本演算法計算每個點的連通分量成員，最後輸出頂點值中包含最小頂點ID的連通分量。將最小頂點ID沿著邊傳播到連通分量的所有頂點。

3）路徑尋找 Single Source Shortest Path(Unweighted、Weighted)

單源最短距離是指給定圖中一個源點，計算源點到其它所有節點的最短距離。Dijkstra演算法是求解有向圖中單源最短距離SSSP（Single Source Shortest Path）的經典演算法。

Dijkstra演算法是通過點去更新最短距離值，每個點維護到源點的當前最短距離值，當這個值發生變化時，將新值加上邊的權值，發送訊息通知其鄰接點。下一輪迭代時，鄰接點根據收到的訊息，更新其當前最短距離值，當所有點的當前最短距離值不再變化時，迭代結束。

• 初始化：源點s到s自身的距離為0（d[s]=0），其他點u到s的距離為無窮（d[u]=∞）。

• 迭代：如果存在一條從u到v的邊，則從s到v的最短距離更新為d[v]=min(d[v], d[u]+weight(u, v))，直到所有的點到s的距離不再發生變化時，迭代結束。

操作指南

準備工作

在進行全圖分析之前，我們需要建立圖計算執行個體和建立圖配置，並完成圖資料的大量匯入或者API資料寫入。

1）建立圖計算服務執行個體，點擊連結進行執行個體開通，早起測試階段可選用【獨享分析型】規格進行功能驗證。

2）建立圖配置，可參考最佳實務基於GraphCompute快速搭建好友推薦圖應用進行業務資料和配置接入。

圖演算法配置

準備工作完成後可進行圖演算法任務配置，下面將基於好友關係的來源資料進行最短路徑、聯通子圖、PageRank三個演算法的驗證和配置解釋。進入【執行個體詳情】-【圖演算法】-【演算法分析】頁面建立和編輯演算法配置，如需周期調度任務，可通過定時配置進行按天調度。

1）最短路徑

確定邊集選擇，選中圖中已關閉【索引最佳化】的邊表可進行演算法分析。支援選擇多條邊，對於部分可以用到邊的權重欄位的演算法，可以選擇邊的權重欄位，比如單源最短距離時可以用邊的score欄位表示邊的長度，如果不選擇權重欄位，則邊的長度預設為1

單源最短距離，需要填寫的擴充參數為sourceIdLabel和sourceIdValue，分別表示演算法需要的啟動初始點的表中的欄位名和對應的值。

2）聯通子圖

只需要進行邊集選擇，選中圖中已關閉【索引最佳化】的邊表可進行演算法分析；無需額外配置權重欄位。

3）PageRank

確定邊集選擇，選中圖中已關閉【索引最佳化】的邊表可進行演算法分析；

PageRank演算法，需要填寫的擴充參數為maxIteration，表示PageRank演算法的最大迭代輪數

4）任務運行

點擊圖演算法配置的"運行"按鈕，彈窗提示計費之後點擊確認即可運行，任務運行記錄可以點擊配置的“歷史任務“進行查看；當前產品功能屬於公測期間，暫不額外收費。

5）結果產出

點擊“儲存配置”成功建立圖演算法配置之後，會在圖中自動建立出一個新的點，點的名稱為填寫的表格最下方的匯出結果，後續運行圖演算法任務成功之後，任務結果會自動迴流到該結果點，迴流完成之後即可線上查詢

查詢分析結果

1）最短路徑

該演算法結果點為KV類型，distance欄位表示源點到該點的最短距離，當該值為Long.MaxValue(2^63-1)時表示不存在源點到該點之間的路徑，可根據ID查詢點：g("user_relation_graph").V("user#-9222864281912809073").hasLabel("sssp_1011_new_result")

2）聯通子圖

該演算法結果點為倒排類型，componentId欄位表示聯通子圖ID：

可根據ID查詢點：g("user_relation_graph").V("user#-1328036738095129493").hasLabel("填寫結果配置的表名")

使用倒排查詢的文法查詢指定componentId下面的所有點：g("user_relation_graph").V().hasLabel("填寫結果配置的表名").indexQuery("{\"match\":{\"component_id\":\"user#-1000713713241257875\"}}")

3）PageRank

該演算法對應的結果點為KV類型，score欄位表示pagerank分數，可根據ID查詢點：g("user_relation_graph").V("user#-9222864281912809073").hasLabel("填寫結果配置的表名")

應用情境

1）PageRank – 提高搜尋覆蓋率

訴求：搜尋是服務平台中重要的一環，通過深化服務搜尋能力，讓使用者可以直接搜尋到服務內部的子服務，實現功能直達；在提升搜尋整體體驗的同時也為各行業帶來更多轉化價值。

問題：長尾關鍵詞搜尋結果少或無結果，純文字匹配無結果。

方案：升級為圖演算法PageRank，引入更豐富的item資訊和使用者點擊行為等資訊，提升召回的多樣性。

效果：全域搜尋PVCTR提升2%以上（推薦結果點擊數/推薦結果曝光數），全域搜尋無結果率累計下降20%以上。

2）Weakly Connected Components - 帳號融合

訴求：同一個人可能會註冊多個電商帳號，通過非正常手段擷取利益。

方案：使用預設的規則建立帳號間的強聯絡，比如使用同一個電話的帳號極大可能屬於同一個人

演算法：強\弱連通分量演算法

成效：取代原先的GraphX、spark系統，時間效率可提升10倍以上

擴充：實體合并（挖掘或識別利益共同體、同一對象），如同名戶、集團客戶等等，都可進行彙總。

計費規則

當前圖演算法功能處於公測期，可免費使用。後續正式上線後將根據資料量級進行資源評估，按照演算法消耗的資源情況進行隨用隨付。