Chapter 4 google

Question 1

Random walk on directed graph

Answer 1

Each path equal probability out of vertex, directed.

Transition probabilities:

p_ij = l_ij /d_i

Where l_ij is the number of links from page I to page j

d_i is the total number of links from page i

Question 2

Properties of directed graph random surfer

Answer 2

Random page all pages have a link out of it and so this random walk forms an IRREDUCIBLE AND APERIODIC MC.

By results of chapter 3 it will have a unique stationary distribution which represents the limiting probabilities that the surfer is on each page. These values are used as rankings.

Question 3

Damping in google page rank directed graph and random surfer

Answer 3

A modification to the random surfer MC is that , at random times, the surfer starts from a page at random . This happens at each time step with probability 1-d,
d is the probability the surfer behaves as previously defined.

Transition probabilities are now

p_ij = d( l_ij/d_i) + (1+d) 1/N where N is the total number of pages in the system.

Here the MC is irreducible and aperiodic. Hence unique stationary dist vector(pi)

Page rank of page I is the probability under that stat limit dist pi_i.