20.2. Random Walks on Graphs 861
A Google-graph is a random-walk graph such that every edge leaving any given
vertex has the same probability. That is, the probability of each edgehv!wiis
1=outdeg.v/.
A digraph issymmetricif, wheneverhv!wiis an edge, so ishw!vi. Given
any finite, symmetric Google-graph, let
d.v/WWD
outdeg.v/
e;
whereeis the total number of edges in the graph.
(a)Ifdwas used for webpage ranking, how could you hack this to give your page
a high rank? ...and explain informally why this wouldn’t work for “real” page rank
using digraphs?
(b)Show thatdis a stationary distribution.Homework Problems
Problem 20.12.
A digraph isstrongly connectediff there is a directed path between every pair of
distinct vertices. In this problem we consider a finite random walk graph that is
strongly connected.
(a)Letd 1 andd 2 be distinct distributions for the graph, and define themaximum
dilation, , ofd 1 overd 2 to be
WWDmax
x 2 Vd 1 .x/
d 2 .x/:
Call a vertex,x,dilatedifd 1 .x/=d 2 .x/D. Show that there is an edge,hy!zi,
from an undilated vertexyto a dilated vertex,z.Hint:Choose any dilated vertex,
x, and consider the set,D, of dilated vertices connected toxby a directed path
(going tox) that only uses dilated vertices. Explain whyD¤V, and then use the
fact that the graph is strongly connected.
(b)Prove that the graph hasat most onestationary distribution. (There alwaysis
a stationary distribution, but we’re not asking you prove this.) Hint:Letd 1 be a
stationary distribution andd 2 be a different distribution. Letzbe the vertex from
part (a). Show that starting fromd 2 , the probability ofzchanges at the next step.
That is,db 2 .z/¤d 2 .z/.
Exam Problems
Problem 20.13.
For which of the graphs in Figure 20.9 is the uniform distribution over nodes a