In math's web, it roams,
Spider's random dance, it homes,
Through theorem domes.
--ChatGPT
5. Random walks on graphs and Markov chains#
In this chapter, we continue to analyze datasets in the form of networks. A powerful way to extract information about the structure of a network is to analyze the behavior of a random walk “diffusing” on it. We will frame such walks in the more general context of Markov chains, a class of stochastic processes with many applications in data science.
The chapter has three main objectives:
To define discrete-time, finite-space Markov chains and derive some of their main properties, in particular their limit behavior.
To specialize these results to the case of random walks of graphs.
To study applications in network analysis, notably PageRank.
Image credit: Made with Midjourney