Consider a toy small example of a directed web graph G = (V;E): (a) Suppose we assign all 18 nodes equal initial page rank values of 1 18 .

Consider a toy small example of a directed web graph G = (V;E):

(a) Suppose we assign all 18 nodes equal initial page rank values of 1

18 . Now suppose

we apply the unscaled Page Rank algorithm to this graph. After one iteration (or

round) of the algorithm, will any nodes have a page rank value of zero? If so, which

ones and why? If not, briefly explain why not.

(b) Answer the same question as in part (a) for both two and three iterations of unscaled

page rank.

(c) When the algorithm converges (i.e., reaches equilibrium), which nodes in the graph

will have non-zero page rank values? What will their equilibrium page rank values

be? Briefly justify your answer.

(d) Suppose we repeat part (a) but consider a variation of the graph in which a single

node can delete a single one of their outgoing edges. Which nodes can increase

their (equilibrium) page rank values by deleting a single outgoing edge? Briefly

justify your answer. (Do not consider simultaneous deletion of multiple edges, just

one single edge.)

(e) What is the minimum number of edges that would need to be added to the graph

so that every node has non-zero page rank? Briefly explain what edges would be

needed and why.

(f) Suppose we use scaled Page Rank on the original graph in part (a) with scaling factor

s = 0:9. Which nodes will have non-zero (equilibrium) page rank values? Qualitatively,

briefly describe which node will now have the highest page rank value.

• Attachment 1
• Attachment 2