文档

图算法

更新时间:

图计算服务GraphCompute新增图算法分析功能,提供分析查询一体化解决方案,方便用户快速进行全图数据分析。

功能介绍

图计算服务GraphCompute新增图算法功能,基于当前服务的数据进行算法执行,方便用户快速进行全图数据的分析。只需要开通图计算服务实例,即可同时拥有高性能图数据的查询分析一体化引擎。相比业界方案,图计算服务方案更便捷,无需额外自运维数据链路,让数据流转更高效。

image.png

本期重点开放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,分别表示算法需要的启动初始点的表中的字段名和对应的值。

image.png

2)联通子图

只需要进行边集选择,选中图中已关闭【索引优化】的边表可进行算法分析;无需额外配置权重字段。

image.png

3)PageRank

确定边集选择,选中图中已关闭【索引优化】的边表可进行算法分析;

PageRank算法,需要填写的扩展参数为maxIteration,表示PageRank算法的最大迭代轮数

image.png

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倍以上

扩展:实体合并(挖掘或识别利益共同体、同一对象),如同名户、集团客户等等,都可进行聚合。

计费规则

当前图算法功能处于公测期,可免费使用。后续正式上线后将根据数据量级进行资源评估,按照算法消耗的资源情况进行按量计费。