13
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to Mma.SE! Your question needs more from your side. Here its considered helpful and polite to show your own efforts and share your data and code attempts in a well formatted form, so we can quickly see the problem you are facing. Please help us to help you and edit your question accordingly. Also, please take the tour, it will help you understand the site. If you write an excellent question it will inspire great answers. $\endgroup$
    – rhermans
    Commented Sep 27, 2017 at 15:35

3 Answers 3

20
$\begingroup$
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}
   ]]]

enter image description here


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]}
   ]]]

enter image description here

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Commented Sep 28, 2017 at 4:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – rhermans
    Commented Sep 28, 2017 at 6:24
  • $\begingroup$ Okay. I got my results. Much thanks! @rhermans $\endgroup$ Commented Sep 28, 2017 at 9:07
10
$\begingroup$

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}
]
$\endgroup$
7
$\begingroup$

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} *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.