November 2024
Intermediate to advanced
416 pages
11h 11m
English
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 ...