功能介紹

圖計算服務(wù)GraphCompute新增圖算法功能，基于當(dāng)前服務(wù)的數(shù)據(jù)進(jìn)行算法執(zhí)行，方便用戶快速進(jìn)行全圖數(shù)據(jù)的分析。只需要開通圖計算服務(wù)實例，即可同時擁有高性能圖數(shù)據(jù)的查詢分析一體化引擎。相比業(yè)界方案，圖計算服務(wù)方案更便捷，無需額外自運維數(shù)據(jù)鏈路，讓數(shù)據(jù)流轉(zhuǎn)更高效。

本期重點開放3個核心圖算法，其他經(jīng)典圖算法持續(xù)開放中。

算法介紹

1）中心性算法 PageRank

PageRank算法是計算網(wǎng)頁排名的經(jīng)典算法。輸入是一個有向圖G，其中頂點表示網(wǎng)頁。如果存在網(wǎng)頁A到網(wǎng)頁B的鏈接，則存在連接A到B的邊。

算法的基本原理如下：

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

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

2) 社區(qū)發(fā)現(xiàn) Weakly Connected Components

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

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

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

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

Dijkstra算法是通過點去更新最短距離值，每個點維護(hù)到源點的當(dāng)前最短距離值，當(dāng)這個值發(fā)生變化時，將新值加上邊的權(quán)值，發(fā)送消息通知其鄰接點。下一輪迭代時，鄰接點根據(jù)收到的消息，更新其當(dāng)前最短距離值，當(dāng)所有點的當(dāng)前最短距離值不再變化時，迭代結(jié)束。

• 初始化：源點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的距離不再發(fā)生變化時，迭代結(jié)束。

操作指南

準(zhǔn)備工作

在進(jìn)行全圖分析之前，我們需要新建圖計算實例和創(chuàng)建圖配置，并完成圖數(shù)據(jù)的批量導(dǎo)入或者API數(shù)據(jù)寫入。

1）創(chuàng)建圖計算服務(wù)實例，點擊鏈接進(jìn)行實例開通，早期測試階段可選用【獨享分析型】規(guī)格進(jìn)行功能驗證。

2）創(chuàng)建圖配置，可參考最佳實踐基于GraphCompute快速搭建好友推薦圖應(yīng)用進(jìn)行業(yè)務(wù)數(shù)據(jù)和配置接入。

圖算法配置

準(zhǔn)備工作完成后可進(jìn)行圖算法任務(wù)配置，下面將基于好友關(guān)系的源數(shù)據(jù)進(jìn)行最短路徑、聯(lián)通子圖、PageRank三個算法的驗證和配置解釋。進(jìn)入【實例詳情】-【圖算法】-【算法分析】頁面新建和編輯算法配置，如需周期調(diào)度任務(wù)，可通過定時配置進(jìn)行按天調(diào)度。

1）最短路徑

確定邊集選擇，選中圖中已關(guān)閉【索引優(yōu)化】的邊表可進(jìn)行算法分析。支持選擇多條邊，對于部分可以用到邊的權(quán)重字段的算法，可以選擇邊的權(quán)重字段，比如單源最短距離時可以用邊的score字段表示邊的長度，如果不選擇權(quán)重字段，則邊的長度默認(rèn)為1

單源最短距離，需要填寫的擴(kuò)展參數(shù)為sourceIdLabel和sourceIdValue，分別表示算法需要的啟動初始點的表中的字段名和對應(yīng)的值。

2）聯(lián)通子圖

只需要進(jìn)行邊集選擇，選中圖中已關(guān)閉【索引優(yōu)化】的邊表可進(jìn)行算法分析；無需額外配置權(quán)重字段。

3）PageRank

確定邊集選擇，選中圖中已關(guān)閉【索引優(yōu)化】的邊表可進(jìn)行算法分析；

PageRank算法，需要填寫的擴(kuò)展參數(shù)為maxIteration，表示PageRank算法的最大迭代輪數(shù)

4）任務(wù)運行

點擊圖算法配置的"運行"按鈕，彈窗提示計費之后點擊確認(rèn)即可運行，任務(wù)運行記錄可以點擊配置的“歷史任務(wù)“進(jìn)行查看；當(dāng)前產(chǎn)品功能屬于公測期間，暫不額外收費。

5）結(jié)果產(chǎn)出

點擊“保存配置”成功創(chuàng)建圖算法配置之后，會在圖中自動創(chuàng)建出一個新的點，點的名稱為填寫的表格最下方的導(dǎo)出結(jié)果，后續(xù)運行圖算法任務(wù)成功之后，任務(wù)結(jié)果會自動回流到該結(jié)果點，回流完成之后即可在線查詢

查詢分析結(jié)果

1）最短路徑

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

2）聯(lián)通子圖

該算法結(jié)果點為倒排類型，componentId字段表示聯(lián)通子圖ID：

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

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

3）PageRank

該算法對應(yīng)的結(jié)果點為KV類型，score字段表示pagerank分?jǐn)?shù)，可根據(jù)ID查詢點：g("user_relation_graph").V("user#-9222864281912809073").hasLabel("填寫結(jié)果配置的表名")

應(yīng)用場景

1）PageRank – 提高搜索覆蓋率

訴求：搜索是服務(wù)平臺中重要的一環(huán)，通過深化服務(wù)搜索能力，讓用戶可以直接搜索到服務(wù)內(nèi)部的子服務(wù)，實現(xiàn)功能直達(dá)；在提升搜索整體體驗的同時也為各行業(yè)帶來更多轉(zhuǎn)化價值。

問題：長尾關(guān)鍵詞搜索結(jié)果少或無結(jié)果，純文本匹配無結(jié)果。

方案：升級為圖算法PageRank，引入更豐富的item信息和用戶點擊行為等信息，提升召回的多樣性。

效果：全局搜索PVCTR提升2%以上（推薦結(jié)果點擊數(shù)/推薦結(jié)果曝光數(shù)），全局搜索無結(jié)果率累計下降20%以上。

2）Weakly Connected Components - 賬號融合

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

方案：使用預(yù)設(shè)的規(guī)則建立賬號間的強(qiáng)聯(lián)系，比如使用同一個電話的賬號極大可能屬于同一個人

算法：強(qiáng)\弱連通分量算法

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

擴(kuò)展：實體合并（挖掘或識別利益共同體、同一對象），如同名戶、集團(tuán)客戶等等，都可進(jìn)行聚合。

計費規(guī)則

當(dāng)前圖算法功能處于公測期，可免費使用。后續(xù)正式上線后將根據(jù)數(shù)據(jù)量級進(jìn)行資源評估，按照算法消耗的資源情況進(jìn)行按量計費。