# Generate random walk on a graph

I have a graph with 100 nodes and 200 edges. How can I generate a random walk in it and animate it?

Block[
{
graph = RandomGraph[{20, 100}]
, start
, path
},
start = RandomChoice[VertexList[graph]];
path = NestList[RandomChoice[AdjacencyList[graph, #]] &, start, 5];
ListAnimate[
Table[
Graph[graph
, VertexStyle -> {v -> Red}
, VertexSize -> Large
]
, {v, path}
]]] Block[
{
graph = GridGraph[{6, 6}]
, start
, path
},
start = RandomChoice[VertexList[graph]];
path = NestList[RandomChoice[AdjacencyList[graph, #]] &, start, 30];
ListAnimate[
Table[
Graph[
graph
, VertexStyle ->
Append[Map[Rule[#, Pink] &, Union[path[[1 ;; v]]]],
path[[v]] -> Red]
, EdgeStyle ->
Evaluate[(UndirectedEdge[#1, #2] -> Directive[Red, Thick]) & @@@
Partition[path[[1 ;; v]], 2, 1]]
, VertexSize -> Large
]
, {v, Length[path]}
]]] • I used your method in my modular graphs. It works wonderfully. Thank you. But what should i do if i want to start specifically at one node? @rhermans – nasha amalina Sep 28 '17 at 4:04
• You should try to understand the code, as it should be self evident if you have red the documentation for the functions I'm using. Change how start is defined, that is the starting vertex. – rhermans Sep 28 '17 at 6:24
• Okay. I got my results. Much thanks! @rhermans – nasha amalina Sep 28 '17 at 9:07

If you need good performance (e.g. compute hundreds of long random walks to get good statistics), consider using IGRandomWalk from the IGraph/M package.

rg = RandomGraph[{100, 200}]

walk = IGRandomWalk[rg, 1, 100]

Animate[
HighlightGraph[rg, vertex],
{vertex, walk}
]


You can use DiscreteMarkovProcess.

For example,

graph = GridGraph[{5, 5}]

mp = DiscreteMarkovProcess[1 (* starting vertex index, not name *), graph]

walk = RandomFunction[mp, {1, 10}]["Values"]
(* {1, 2, 1, 6, 11, 16, 11, 12, 7, 2} *)


Animate:

Animate[
HighlightGraph[g, vertex],
{vertex, walk}
]


Performance comparison with IGRandomWalk from IGraph/M:

RandomFunction[mp, {1, 10000}]; // RepeatedTiming
(* {0.034, Null} *)

IGRandomWalk[graph, 1, 10000]; // RepeatedTiming
(* {0.00038, Null} *)