功能介紹

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

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

算法介紹

1）中心性算法 PageRank

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

算法的基本原理如下：

• 初始化：點(diǎn)值表示PageRank的rank值（DOUBLE類型）。初始時(shí)，所有點(diǎn)取值為1/TotalNumVertices。

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

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

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

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

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

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

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

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

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

操作指南

準(zhǔn)備工作

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

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

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

圖算法配置

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

1）最短路徑

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

單源最短距離，需要填寫的擴(kuò)展參數(shù)為sourceIdLabel和sourceIdValue，分別表示算法需要的啟動(dòng)初始點(diǎn)的表中的字段名和對(duì)應(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ù)運(yùn)行

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

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

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

查詢分析結(jié)果

1）最短路徑

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

2）聯(lián)通子圖

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

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

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

3）PageRank

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

應(yīng)用場(chǎng)景

1）PageRank – 提高搜索覆蓋率

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

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

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

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

2）Weakly Connected Components - 賬號(hào)融合

訴求：同一個(gè)人可能會(huì)注冊(cè)多個(gè)電商賬號(hào)，通過非正常手段獲取利益。

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

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

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

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

計(jì)費(fèi)規(guī)則

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