通用图算法

全图 K 邻查询

全图 K 邻查询,即对图中所有点进行 K 邻计算,返回所有点的第 K 步 nodes 的数量,并支持将统计结果回写到点属性 #khop_all 当中。

全图 K 邻查询将会以任务的方式启动

全图 K 邻算法的 [命令] 为:algo(khop_all)

全图 K 邻算法的 [配置] 为:

名称 类型 规范 描述
depth int > 0,必填 K 的值,也就是深度
direction string left, right 路径中边的方向,不设置表示不限制方向

注 1:Ultipa 图计算对 K-hop 查询做了高并发性能优化,在大多数图数据集中,每秒钟可以完成几万到几十万级别的 K 邻查询操作。

注 2:全图 K-hop 查询可能会消耗大量系统资源,尤其是在大图(超过千万-亿顶点及边)和存在很多热点的图当中,建议避免进行深度的全图 K-hop 查询。举例:在一个(边数量/点数量)=100 的图中,如果查询 1 个顶点的 5-hop 需要的理论计算量是 100 的五次方(100 亿量级的计算复杂度),耗时 100ms,那么 1 千万个顶点的图中查询完毕需要 100万秒 = 12天!!!

示例:计算全图 2 步 K 邻的数量

algo(khop_all).params({ depth: 2 });

在 Ultipa-CLI 中我们可以运行和查看运行信息与结果

示例:算法任务运行信息:

通过查看 age=20 的 3 个点的信息来观察 khop 结果(在最新版中字段名为 #khop_all):

连通分量计算(Connected Component)

连通分量,即统计当前图集中能连通的极大子图的个数,若当前图集为全连通图,那么连通分量为 1。

该算法返回每个节点所属的连通分量的 id 号,且支持将计算结果回写到点属性 #connected_component 中。

计算连通分量的 [命令] 为:algo(connected_component)

计算连通分量的 [配置] 项:

名称 类型 规范 描述
cc_type int 1 | 2,必填 1:wcc 弱连通图 , 2:scc 强连通图

示例:计算全图的弱连通分量:

algo(connected_component).params({ cc_type: 1 });

三角形计算(Triangle Counting)

计算全图的三角形数量,并返回构成每个三角的点或边。

在图论中,计算三角形的数量有着广泛的用途,比如社交网络发现,社区识别,紧密度分析,稳定性分析等。三角形计算分为两种方式,1)按照边组装三角形,2)按照点组装三角形。其中,按边组装的三角形数量可能会多于按点组装的三角形数量。

通常通过边的三角形计算更能体现出图的特性。

计算三角形的 [命令] 为:algo(triangle_counting)

计算三角形的 [配置] 为:

名称 类型 规范 描述
type int 1 | 2,必填 1:按边计算三角形
2:按点计算三角形
limit int >0或-1,必填 需要返回的结果的条数,-1表示仅返回三角形的总数而不返回点或边的信息

示例:按照边计算全图三角形数量:

algo(triangle_counting).params({type: 1, limit: -1})

示例:按照点计算全图三角形,并返回4个三角形:

algo(triangle_counting).params({type: 2, limit: 4})

共同邻居数计算(Common Neighbours)

计算两个点的共同邻居数量:

共同邻居数计算的 [命令] 为:algo(common_neighbours)

共同邻居数计算的 [配置] 为:

名称 类型 规范 描述
node_id1 int >0,必填 /
node_id2 int >0,必填 /

子图拼接(subgraph)

计算由若干点组成的诱导子图(induced subgraph),即给定若干个点,由它们生成的最大子图。

子图拼接的[命令]algo(subgraph)

子图拼接的[配置] 为:

名称 类型 规范 描述
node_ids []int 必填 需要组装的点(数组)