概述
全图 K 邻算法可以为每个节点计算其第 K 步邻居的数量,并返回这些邻居。该算法广泛应用于关系发现、影响力预测、好友推荐等场景。
全图 K 邻可以看作是 UQL 命令 khop()
的批量执行。尽管 Ultipa 的全图 K 邻算法经过了高并发性能优化,在大图(超过千万顶点及边)或有很多超级节点的图中运行此算法仍会消耗大量系统资源。因此,建议避免进行过深的全图 K 邻居计算。
在一个
边数量/点数量 = 100
的图中,查询 1 个顶点的 5-hop 邻居,理论上计算量是 100 的 5 次方(100 亿量级的计算复杂度),耗时 100 毫秒;那么,在一个有 1 千万顶点的图中查询完毕,则需要 100 万秒(12 天)。
基本概念
BFS
BFS(Broad-First Search)是宽度优先遍历的缩写,与深度优先遍历(DFS,Depth-First Search)一起构成最基本的两种遍历原则。K 邻查找使用的就是 BFS 原则,具体是指以图中某一节点为起点遍历全图时,先遍历当前节点所有尚未遍历的邻居节点,再依次对这些邻居节点遍历它们尚未遍历的邻居节点。
以红色节点为起点,按照 BFS 原则进行遍历,会先后找到黄色节点、绿色节点、蓝色节点。这些节点的颜色分类是基于它们与起点之间的距离,即从起点到它们的最短路径的边数。这个距离就是 K 邻查询中 K
的含义,表示起点的第 K
层邻居。
给定起点后,图中其它节点的 K 值也将随之确定。即,如果一个节点是起点的第 5 层邻居,那么它就不可能在第 4、6 或其它层中出现。
K 邻方向
在有向图中进行 K 邻查询时,可以指定邻居所在的边的方向。此时,不是所有节点都会出现在遍历结果中,即有些节点的 K 值不存在。
在上面左侧的有向图中,从红色节点开始,分别按照出边、入边的方向进行遍历;可以发现两种遍历结果截然不同,并且在沿入边遍历时,紫色节点不属于任何一个层次,其 K 值不存在。
特殊处理
孤点、不连通图
孤点不会出现在 K 邻查询的结果中。
对于不连通图,只有起点所在的连通分量中的节点会出现在 K 邻查询的结果中,其余的点均不会被遍历到。
自环边
K 邻查询中每个节点仅被遍历一次,因此可以认为节点的自环边无效。
有向边
在不规定边的方向时进行 K 邻查询,边的方向将被忽略,此时起点所在连通分量中的所有节点都可计算出确定的 K 值。
结果和统计值
以下面的银行卡转账图为例,卡的颜色代表其等级,针对所有点运行全图 K 邻算法:
算法结果:计算每个点的一步邻居,并统计结果中银行卡的最高等级,根据算法执行方式,返回 _id
、value
两列或 _uuid
、value
两列,其中 value
列依次显示聚合统计结果和邻居数
_uuid | _id | value |
---|---|---|
1 | Card1 | 3, 3 |
2 | Card2 | 3, 3 |
3 | Card3 | 2, 3 |
4 | Card4 | 3, 1 |
5 | Card5 | 2, 2 |
6 | Card6 | , 0 |
算法统计值:无
命令和参数配置
- 命令:
algo(khop_all)
params()
参数配置项如下:
名称 |
类型 | 默认值 |
规范 | 描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | / | 待计算节点的 ID 或 UUID;忽略表示计算全部点 |
k_start | int | 1 | >= 1 | 寻找 K 邻的最小深度值,算法搜索 K 邻的范围是 [k_start , k_end ],k_end ≥ k_start |
k_end | int | 1 | >= 1 | 寻找 K 邻的最大深度值,算法搜索 K 邻的范围是 [k_start , k_end ],k_end ≥ k_start |
src_include | int | 0 | 0 或 1 | 是否将起点包含在结果中,1 代表包含,0 或忽略代表不包含 |
direction | string | / | in/out,大小写均可 | 路径中边的方向;忽略表示忽略方向 |
node_property | []@<schema>?.<property> |
/ | 数值类的点属性,需LTE | 要进行聚合统计的点属性,带不带 schema 均可,必须与 aggregate_opt 一起使用,如果填多个属性,aggregate_opt 也需对应填写多种聚合统计方式;无该属性的结果不参与聚合统计 |
aggregate_opt | []string | / | max 或 min 或 mean 或 sum 或 var 或 dev,大小写不敏感 | 结果的每个指定属性的聚合统计方式,必须与 node_property 参数一起使用且一一对应;max 表示最大值,min 表示最小值, mean 表示平均值, sum 表示总和,var 表示方差,dev 表示标准差 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
示例:计算所有点出方向两步邻居的数量
algo(khop_all).params({
k_start: 2,
k_end: 2,
direction: "out"
}) as k2
return k2
示例:计算点 UUID = 3,4,5 的两步和三步邻居并统计结果中 @card.level 属性的最大值和 @card.balance 属性的总和,同时在每个节点的结果中包含起点(UUID = 3,4,5)
algo(khop_all).params({
uuids: [3,4,5],
k_start: 2,
k_end: 3,
src_include: 1,
node_property: [@card.level, @card.balance],
aggregate_opt: ["max", "sum"]
}) as k2
return k2
算法执行
任务回写
1. 文件回写
配置项 |
各列数据 | 备注 |
---|---|---|
filename_ids | _id ,_id |
每个结果占一行,每行第一个 _id 是计算的点,第二个 _id 为该点邻居 |
filename | _id ,aggregate_result1 ,...,aggregate_resultN ,count |
_id 代表计算的点,接着是一个或多个聚合统计结果(aggregate_result1 ~ aggregate_resultN ),最后的 count 是邻居总数 |
示例:计算所有点的三步邻居并统计结果中 @card.level 属性的最大值和 @card.balance 属性的总和,将每个点和其邻居的 ID 回写至名为 neighbors 的文件,将每个点的聚合统计结果和邻居数量回写至名为 counts 的文件
algo(khop_all).params({
k_start: 3,
k_end: 3,
node_property: [@card.level, @card.balance],
aggregate_opt: ["max", "sum"]
}).write({
file:{
filename_ids: "neighbors",
filename: "counts"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | 邻居数 | 点属性 | double |
示例:计算所有点的两步邻居,将邻居数回写至名为 khop2 的点属性
algo(khop_all).params({
k_start: 2,
k_end: 2
}).write({
db:{
property: "khop2"
}
})
3. 统计回写
算法无统计值。
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其聚合统计结果和邻居数 | _uuid , value |
示例:计算所有点的三步邻居并统计结果中 @card.level 属性的最大值和 @card.balance 属性的总和,将算法结果定义为别名 nei 并返回
algo(khop_all).params({
k_start: 3,
k_end: 3,
node_property: [@card.level, @card.balance],
aggregate_opt: ["max", "sum"]
}) as nei
return nei
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其聚合统计结果和邻居数 | _uuid , value |
示例:计算点 UUID = 3 的一步到三步邻居并统计结果中 @card.level 属性的最大值,仅返回聚合统计结果和邻居数量
algo(khop_all).params({
uuids: [3],
k_start: 1,
k_end: 3,
node_property: @card.level,
aggregate_opt: max
}).stream() as results
return results.value
实时统计
算法无统计值。