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.
Specifications
Parameters
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. |
|
Example
Suppose we have the following 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:
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:
Last updated