概述
随机游走(Random Walk),顾名思义,是指在图中从某个节点(任意或全部)出发,随机通过某条邻边到达另一节点,重复此过程直至遍历所有可触达的节点或达到遍历限定的深度或时间。“随机游走”这一概念是由英国数学家、生物统计学家 Karl Pearson 于 1905 年正式提出的:
- K. Pearson, The Problem of the Random Walk (1905)
基本概念
随机游走
随机游走(Random Walk,简写为 RW)是一种数学模型,每随机游走一次就形成一个轨迹,重复随机游走的每一个轨迹都是随机的。它用来表示不规则的变动形式,如同一个人酒后乱步所形成的轨迹的记录。
最简单的随机游走是一维随机游走:假设一个点从数轴的原点出发,每次以相同的概率向上或向下移动一个单位,一次 10 步随机游走的轨迹如下:
重复多次进行 100 步随机游走得到的轨迹序列如下:
图上的随机游走
在图中,随机游走是指从某个节点出发,按照限定的游走深度(即访问的节点数量)和过滤条件(一般可设定为一个或多个边属性)不断经过邻居节点,最终形成随机游走路径的过程。假设全图有 8 个顶点,如果进行 300 次深度为 30 个节点的随机游走,就会生成 2400 条路径,每条路径最多包含 30 个节点。
Ultipa 的完全随机游走算法是经典随机游走:默认不指定边权重(即所有边权重值为 1),每条边被经过的可能性相同;如果指定边权重,边被经过的概率与边权重大小成正比。随机游走也有其他多种形式,如 Node2Vec 游走、Struc2Vec 游走、GraphSAGE 采样等。
特殊处理
孤点、不连通图
孤点没有邻居节点,因此无法游走到其他节点;如果孤点有自环边,只能沿着自环边游走。非孤点的游走路径上不会出现孤点。
节点只会在自身所处的连通分量内游走。
自环边
节点可以沿自环边游走。
有向边
随机游走的结果与边的方向无关。
结果和统计值
在下图进行 2 次全图完全随机游走,每次游走深度为 6,所有边权重为 1:
算法结果:全图有 11 个节点,因此在返回的 walks
列下包含有 11*2 = 22 个节点数组
walks |
---|
[5, 6, 4, 3, 5, 6] |
[6, 5, 3, 5, 6, 5] |
[11] |
[10, 7, 8, 7, 10, 7] |
[8, 9, 9, 9, 9, 9] |
[7, 10, 7, 10, 7, 10] |
[2, 1, 2, 1, 2, 1] |
[9, 9, 9, 8, 7, 6] |
[1, 3, 4, 6, 4, 3] |
[3, 5, 3, 1, 3, 1] |
[4, 3, 4, 3, 4, 3] |
[5, 3, 4, 6, 5, 6] |
[6, 5, 6, 5, 6, 7] |
[11] |
[10, 7, 8, 7, 10, 7] |
[8, 9, 8, 7, 10, 7] |
[7, 10, 7, 6, 5, 6] |
[2, 1, 3, 4, 6, 4] |
[9, 8, 9, 9, 9, 9] |
[1, 3, 4, 3, 5, 6] |
[3, 4, 3, 4, 6, 7] |
[4, 3, 1, 3, 1, 2] |
算法统计值:无
命令和参数配置
- 命令:
algo(random_walk)
params()
参数配置如下:
名称 | 类型 | 默认值 |
规范 |
描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | / | 起点的 ID 或 UUID;忽略表示选择全部点 |
walk_length | int | 1 | >=1 | 每次游走的深度,即游走访问的节点数量 |
walk_num | int | 1 | >=1 | 游走次数 |
edge_schema_property | []@<schema>?.<property> |
/ | 数值类的边属性,需LTE | 边权重的一个或多个属性名称,带不带 schema 均可;节点只会沿着带有这些属性的边游走,且经过这些边的概率与边权重成正比;如果边带有多个指定属性,权重值为这些属性值的和;忽略表示所有边权重为 1 |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
示例:选择图中 UUID = 1,2,...,10 节点进行 2 次完全随机游走,每次游走深度为 6
algo(random_walk).params({
uuids: [1,2,3,4,5,6,7,8,9,10],
walk_length: 6,
walk_num: 2
}) as walks
return walks
算法执行
任务回写
1. 文件回写
配置项 |
各列数据 |
描述 |
---|---|---|
filename | _id ,_id ,... |
从起点出发随机游走依次经过的节点的 ID |
示例:选择图中 UUID = 1,2,...,10 节点进行 2 次完全随机游走,每次游走深度为 6,将算法结果回写至名为 paths 的文件
algo(random_walk).params({
uuids: [1,2,3,4,5,6,7,8,9,10],
walk_length: 6,
walk_num: 2
}).write({
file:{
filename: "path"
}})
2. 属性回写
算法不支持属性回写。
3. 统计回写
算法无统计值。
直接返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perWalk | 每次游走路径的所有节点的 UUID 构成的数组 | [_uuid, _uuid, ...] |
示例:在全图进行 3 次完全随机游走,每次游走深度为 5,将算法结果定义为别名 paths 并返回
algo(random_walk).params({
walk_length: 5,
walk_num: 3
}).write({
file:{
filename: "path"
}})
流式返回
别名序号 |
类型 |
描述 | 列名 |
---|---|---|---|
0 | []perWalk | 每次游走路径的所有节点的 UUID 构成的数组 | [_uuid, _uuid, ...] |
示例:在全图进行 3 次完全随机游走,每次游走深度为 5,指定边权重所在属性为 @follow.level,返回游走深度小于 5 的结果
algo(random_walk).params({
walk_length: 5,
walk_num: 3,
edge_schema_property: @follow.level
}).stream() as walk
where size(walk) < 5
return walk
实时统计
算法无统计值。