Graph Algorithms the Fun Way

13 RANDOM WALKS

So far, this book has introduced a variety of algorithms focused on achieving specific goals. This chapter considers algorithms that seek to do something a bit different: inducing random behavior on graphs. Analyzing random movement through a graph allows us to model and study systems with nondeterministic behavior such as randomized network routing or real-world social interactions.

Random walks on graphs have a rich mathematical history that extends well beyond the scope of this book. This chapter provides an overview of random walks, an introduction of how to analyze them with Markov chains, and code for implementing ...