9
$\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
    $\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 Sep 27 '17 at 15:35
16
$\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$
  • $\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$ – nasha amalina Sep 28 '17 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 Sep 28 '17 at 6:24
  • $\begingroup$ Okay. I got my results. Much thanks! @rhermans $\endgroup$ – nasha amalina Sep 28 '17 at 9:07
8
$\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$
4
$\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, privacy policy and cookie policy

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