Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/random_walk/
Documentation version: v5.3.2

# 随机游走

本文介绍随机游走算法，并演示如何用 GQL 实现该算法。

## 数据模型

为了在 GQL 中实现随机游走算法，使用以下数据模型创建图类型：

- 实体由类型为`Node`的点表示，点属性包括`id`和`rating`。
- 实体间关系由类型为`Link`的边表示，边属性包括`weight`。

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/random_walk/#1_prepare_graph_data)。

## 过程实现[]()

为了计算随机游走结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/random_walk/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

- `source_id`：`INT64`类型。 游走起始点的 ID。
- `max_steps`：`INT64`类型。 每次游走的最大步数。

此外，在过程内部定义了以下变量：

 | 变量名 | 变量类型 | 描述
 | `frontier` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前步骤中的活跃游走者集合。
 | `step` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前游走步骤计数。
 | `next_id` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 过程执行中的内部变量。
 | `next_pick` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 过程执行中的内部变量。
 | `walk_table` | [表变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/table-variable/) | 存储游走路径记录的输出表。

以下步骤概述了该过程的逻辑：

1. 以每个起始点初始化各游走路径；将所有起始点加入`frontier`。
2. 在每个步骤中，`frontier`中的每个游走者使用`SAMPLE RIGHT`采样一个出边邻居。
3. 将当前点和步骤记录到`walk_table`；将`frontier`推进到采样到的邻居。
4. 当`step`达到游走长度或无游走者可移动时停止。返回完整游走路径记录。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建一个与数据模型匹配的图类型。

````
'''
CREATE GRAPH TYPE IF NOT EXISTS random_walk_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/random_walk/`：

  - [random_walk_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/random_walk/random_walk_node.csv)：点数据。
  - [random_walk_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/random_walk/random_walk_edge.csv)：边数据。

查看 CSV 内容

random_walk_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

random_walk_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

基于图类型创建临时图，并将数据文件加载到临时图中。

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #random_walk_graph TYPED random_walk_graph_type

````

````
'''
USE #random_walk_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/random_walk/random_walk_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/random_walk/random_walk_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

````

导入成功后，在控制台执行以下查询核对点数：

````
'''
USE #random_walk_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

`node_count`应为`24`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现随机游走算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/random_walk/#procedure_implement)。 

````
'''
CREATE OR REPLACE PROCEDURE random_walk(
  source_id INT64,
  max_steps INT64
)
RETURNS (step_no INT64, node_id INT64)
COMMENT "Compute a single-path walk on a directed graph whose vertex primary key is id. Starting from source_id, each round selects one outgoing edge, returns the visited trajectory, stops after max_steps rounds, and stops early at sink vertices."
AS {
  VALUE frontier ACTIVE_SET

  VALUE step INT64 = 0
  VALUE next_id INT64 = 0
  VALUE next_pick TopKAgg<1, node_id INT64 ASC>

  TABLE walk_table TYPED TABLE {
    step_no INT64,
    node_id INT64
  }

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    EXPORT 0, s.id INTO walk_table
  }
  FINALLY {
    SET frontier = s
  }

  WHILE step < max_steps THEN {
    SET @next_pick.clear()

    MATCH (s)-[e]->(t)
    WHERE s IN frontier
    PER PATH {
      SET @next_pick += RECORD{node_id: t.id}
    }

    IF @next_pick.size() = 0 THEN {
      BREAK
    }

    SET next_id = @next_pick.min().node_id

    MATCH (t)
    WHERE t.id = next_id
    PER NODE (t) {
      EXPORT step + 1, t.id INTO walk_table
    }
    FINALLY {
      SET frontier = t
    }

    SET step = step + 1
  }

  FOR r IN walk_table
  RETURN r.step_no AS step_no, r.node_id AS node_id
  ORDER BY step_no ASC
}
'''

````

### 3. 调用过程[]()

从点`1`开始随机游走，最多执行`8`步，返回每一步访问的点 ID。

````
USE #random_walk_graph CALL random_walk(1, 8) RETURN step_no, node_id

````

返回：

展开查看返回

````
+---------+---------+
| step_no | node_id |
+---------+---------+
| 0       | 1       |
| 1       | 2       |
| 2       | 3       |
| 3       | 4       |
| 4       | 6       |
| 5       | 8       |
| 6       | 9       |
| 7       | 10      |
| 8       | 12      |
+---------+---------+

````

Note

由于随机游走会随机采样出边，因此每次执行过程时，返回的游走轨迹都可能不同。

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。