Random Walk

Random Walk is an algorithm that generate random paths in a graph. A random walk starts at every vertex that has an outgoing edge, and moves to another vertex at random. The random walk algorithm will print all possible paths of the specified size from the walks that were performed onto a file in the CSV format.


CREATE QUERY tg_random_walk(
INT step = 8, INT path_size = 4, STRING filepath = "/home/tigergraph/path.csv",
SET<STRING> edge_types, INT sample_num)


Name Description Data type


The number of hops performed in each random walk.



The length of the paths to output. The length refers to the number of vertices in a path. For example, if a walk has two steps: A → B → C, then there are paths of both lengths 2 and lengths 3 that can be output from this walk. If a path size of 2 is supplied, then the algorithm outputs two paths: A → B and B → C. If the path size is 3, then there is one path: A → B → C.



The filepath to output the paths to.



The edge types that the random walk will traverse.



At each possible step, the number of sample walks to perform.



Suppose we have the following social graph:

Example social graph

If we run the random walk algorithm on the graph and supply a path size of 3 and a step of 2, and a sample number of 1. Then from each vertex there is a two-step random walk, and a total of 6 three-vertex paths:

Howard Yelena Noah
Noah Owen Noah
George Owen Noah
Eddie Noah Yelena
Yelena Howard Yelena
Owen George Owen

We can also perform a 3 step walk and still ask for three-vertex paths, in which case the number of paths would double, because in each 3 step walk, there are two possible three-vertex paths:

Howard Yelena Noah
Owen Yelena Noah
Noah Owen Noah
George Owen Noah
Yelena Owen Noah
Eddie Noah Owen
Howard Yelena Noah
Noah Owen Noah
George Owen Noah
Eddie Noah Howard
Yelena Noah Howard
Owen Noah Howard