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 Commented Sep 28, 2017 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. Commented Sep 28, 2017 at 6:24
• Okay. I got my results. Much thanks! @rhermans Commented Sep 28, 2017 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} *)