Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/random_walk/
Documentation version: v5.3.2

# Random Walk

## Algorithm introduction

Random walk simulates probabilistic traversal paths and summarizes visit distribution across graph nodes.

Compute a single-path walk on a directed graph whose node 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 nodes.

For more information, see [Random Walk](https://en.wikipedia.org/wiki/Random_walk).

## Data model

To implement the Random Walk algorithm in GQL, the following data model is used to create a graph type:

- Entities are represented by nodes of type `Node`, with properties `id` and `rating`.
- Relationships are represented by edges of type `Link`, with property `weight`.

For the complete definition of the graph type, see [Prepare graph data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/random_walk/#1_prepare_graph_data).

## Procedure implementation[]()

To compute Random Walk results, a [procedure](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/procedures/create/) is created.

For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/random_walk/#procedure_implement). The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

- `source_id`: `INT64`. ID of the starting node for the walk.
- `max_steps`: `INT64`. Maximum number of steps per walk.

Additionally, the following variables are defined within the procedure:

 | Variable name | Variable type | Description
 | `frontier` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Active set of walkers in the current step.
 | `step` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Current walk step counter.
 | `next_id` | [Primitive value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/value-variable/) | Internal variable used during procedure execution.
 | `next_pick` | Global [SumAgg aggregator value variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | Internal variable used during procedure execution.
 | `walk_table` | [Table variable](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/variable-definition/table-variable/) | Output table storing the walk path records.

The following steps outline the logic of the procedure:

1. Initialize each walk starting from its source node; add all starting nodes to `frontier`.
2. At each step, each walker in the `frontier` samples one outgoing neighbor using `SAMPLE RIGHT`.
3. Record the current node and step into `walk_table`; advance `frontier` to the sampled neighbors.
4. Stop when `step` reaches the walk length or no walker can move. Return the complete walk path records.

## Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow [Prepare algorithm sample data](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data[]()

1. 

Create a graph type that matches your data model.

````
'''
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. 

Download these CSV files and save them with their original names in `examples/algorithms/random_walk/` under your deployment directory:

  - [random_walk_node.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/random_walk/random_walk_node.csv): Node data.
  - [random_walk_edge.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/random_walk/random_walk_edge.csv): Edge data.

Preview the CSV files

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 a temporary graph based on the graph type and load the data files into the temporary graph.

````
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: ','
      }
  }
'''

````

After the import succeeds, run this query in the console to check the node count:

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

````

The expected `node_count` is `24`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) before continuing.

### 2. Create a procedure[]()

Create a procedure to implement the Random Walk algorithm. For more information about the procedure, see [Procedure implementation](https://dev-docs.nebula-graph.io/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. Call your procedure[]()

Start a random walk at node `1` for at most `8` steps and return the node ID visited at each step.

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

````

Returns:

Expand to view results

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

````

Note

Because Random Walk samples outgoing edges randomly, the returned walk trace can differ from one execution to another.

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see [EXPORT](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/). Match the exported fields to the returned columns and target properties.