• The paint spilling metaphor is due to Berkhin [Ber06].

11.2 PageRank We have all encountered the PageRank algorithm: it is how Google got started ranking web pages. It involves random walks in directed graphs. We are going to talk more about random walks in directed graphs in a later lecture. But, I need to give you the introduction now. PageRank considers a process that with probability α jumps to a uniformly random vertex of a graph, and with probability 1 − α follows a random edge out of the present node. The PageRank vector is the steady-state distributuion of this process. That is, if we let W be the walk matrix of the directed graph (you can figure out how to define it), the PageRank vector p will satisfy p =