Random Walk on Graphs

From CLAIRlib

In this tutorial you'll learn how to use Clairlib to perform random walk on graphs. To do this we'll use random_walk.pl utility. This script takes a graph file in edgelist format as input and performs the random walk on it based on several options as described by

random_walk.pl --help

For example, if you have the following graph "example.graph"

1 2
1 4
2 1
2 3
4 1
4 3
4 5
5 1
3 1

and the transition probabilities between the nodes are as follows "example.trans"

1 2 0.30
1 4 0.70
2 1 0.65
2 3 0.35
4 1 0.20
4 3 0.50
4 5 0.30
5 1 1.00
3 1 1.00

The probabilities after walking 100 random steps for 500 rounds, can be found by running

random_walk.pl --grpah example.graph --transition_file example.trans --steps 100 --rounds 500 --output example100.prob

The computed probabilities will be outputed to "example100.prob" and will be something like,

5 0.098
2 0.098
3 0.168
1 0.35
4 0.286

To compute the stationary distribution (after walking so many random steps), run the following command,

random_walk.pl --grpah example.graph --transition_file example.trans --stationary --output example.prob

The content of the file "example.prob" after running the command will be something like this

5 0.07
2 0.11
3 0.17
1 0.37
4 0.26