概述
随机游走(Random Walk)从图中的某个节点开始,随机移动至其中一个邻居节点;这个过程通常会重复进行预设的次数。这个概念最早由英国数学家和生物统计学家Karl Pearson于1905年引入,自那时以来,它已经成为了研究各种系统的基石,而不仅限于图论领域。
- K. Pearson, The Problem of the Random Walk (1905)
基本概念
随机游走
随机游走是一种数学模型,用于模拟以随机或不可预测的方式进行的一系列步骤,类似于一个醉汉酒后乱步所形成路径。
基本的随机游走在一维空间中进行:一个节点从数轴的原点开始,每次向上或向下移动一个单位,移动的方向概率相等。一个10步随机游走的示例如下:
![](https://img.ultipa.cn/draw/draw_39cd2d9439484a909677ce843f6efd9b.jpg?v='1661417101846')
以下是多次执行这种随机游走的示例,每次游走100步:
![](https://img.ultipa.cn/2022-08-25-17-00-09-1920px-Random-Walk-example.png)
图中的随机游走
在图中,随机游走从一个节点开始,并依次经过相邻节点形成路径。这个过程由游走深度控制,该深度确定要访问的节点数。
嬴图的随机游走算法实现的是经典随机游走。默认情况下,每条边被赋予相同的权重(等于1),从而遍历每条边的概率相等。当指定边权重时,遍历每条边的概率与其权重成正比。需要注意的是,随机游走存在多种变体,例如Node2Vec游走和Struc2Vec游走。
特殊说明
- 节点可以沿自环边游走。
- 如果游走从一个孤点开始,且该点没有自环边,那么游走在第一步后就会停止,因为没有相邻的边可以继续前进。
- 随机游走的结果与边的方向无关。
语法
- 命令:
algo(random_walk)
- 参数:
名称 | 类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 是 | 指定游走起点的ID/UUID;忽略表示指定全部点 |
walk_length | int | ≥1 | 1 |
是 | 每次游走的深度,即访问的节点数量 |
walk_num | int | ≥1 | 1 |
是 | 从每个指定节点开始的游走次数 |
edge_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 是 | 用作边权重的边属性,权重值为所有指定属性值的和;只沿着带有这些属性的边游走 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
示例图如下,边上的数值是边属性score的值:
![](https://img.ultipa.cn/draw/draw_85be99bb5cee487c99836baf9d60c9ef.jpg?v='1691996334002')
文件回写
配置项 |
回写内容 |
描述 |
---|---|---|
filename | _id ,_id ,... |
访问的节点的ID |
algo(random_walk).params({
walk_length: 6,
walk_num: 2
}).write({
file:{
filename: 'walks'
}})
结果:文件walks
K,
J,G,J,G,F,D,
I,I,I,H,I,I,
H,I,I,I,I,I,
G,J,G,J,G,H,
F,D,C,A,B,A,
E,F,D,C,D,C,
D,F,G,H,G,H,
C,D,F,E,F,D,
B,A,B,A,C,A,
A,C,A,C,D,F,
K,
J,G,J,G,J,G,
I,I,I,H,I,I,
H,I,H,G,J,G,
G,H,I,I,H,G,
F,D,C,D,F,E,
E,C,D,F,G,J,
D,C,D,C,E,F,
C,E,C,A,B,A,
B,A,B,A,C,A,
A,B,A,C,D,C,
直接返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | []perWalk | 访问的节点的UUID列表 | [_uuid, _uuid, ...] |
algo(random_walk).params({
walk_length: 6,
walk_num: 2,
edge_schema_property: 'score'
}) as walks
return walks
结果:walks
[11] |
[10, 7, 10, 7, 10] |
[9, 9, 9, 9, 9] |
[8, 9, 9, 9, 9] |
[7, 10, 7, 10, 7] |
[6, 4, 3, 4, 3] |
[5, 6, 7, 6, 4] |
[4, 6, 7, 10, 7] |
[3, 1, 3, 1, 3] |
[2, 1, 3, 1, 3] |
[1, 3, 4, 3, 5] |
[11] |
[10, 7, 10, 7, 10] |
[9, 9, 9, 8, 7] |
[8, 9, 8, 7, 8] |
[7, 6, 4, 6, 4] |
[6, 5, 6, 4, 6] |
[5, 3, 4, 6, 4] |
[4, 6, 4, 6, 7] |
[3, 4, 3, 4, 6] |
[2, 1, 3, 1, 3] |
[1, 2, 1, 3, 1] |
流式返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | []perWalk | 访问的节点的UUID列表 | [_uuid, _uuid, ...] |
algo(random_walk).params({
walk_length: 5,
walk_num: 1,
edge_schema_property: '@default.score'
}).stream() as walks
where size(walks) == 5
return walks
结果:walks
[10, 7, 10, 7, 6] |
[9, 9, 9, 9, 9] |
[8, 9, 9, 9, 9] |
[7, 10, 7, 6, 4] |
[6, 4, 3, 4, 6] |
[5, 6, 4, 6, 4] |
[4, 3, 4, 6, 4] |
[3, 1, 3, 5, 3] |
[2, 1, 3, 4, 6] |
[1, 2, 1, 2, 1] |