Example 1: Consider five webpages A, B, C, D, and E that link to each other according to the graph below. For instance, the arrow from A to C indicates that page A links to page C, and the two-way arrow between A and B indicates that A and B link to each other. D - -> E The PageRank algorithm assigns ranks r(A), r(B), r(C), r(D), and r(E) that are all between 0 and 1 (inclusive) and sum to 1. Each page equally distributes its own PageRank along its outbound links. For example, page B has two outbound links, so page B "donates" " to both page A and page D. Page D also gives half its PageRank to page A, so the PageRank of A satisfies: "(A) = (B) r (D) 2 2 Since page B has inbound links from page A (which has four total outbound links) and page C (which has two total outbound links), the PageRank of page B satisfies: r(B) = "(A) r(C) 4 2 The full list of equations is: r(A) = (B) + r (D) 2 2 r(B) = _ r(A) r(C) 4 2 r(C) = (A) r(B) 4 2 r(D) = (A) 4 -+r(E) r(E) = "(A) r(C) J r(D) 4 2 2The unique solution of this system of linear equations for which the sum of the PageRanks is 1 is: r(A) 0.211 r(B) 0.105 2(0) = 0.105 MD) 0.316 NE) 0.263 We always normalize our solution vector so that the sum of the PageRanks is 1. Interpreting these results, we see that page D would show up rst in a search since it has the highest rank (0.316), followed by page E, with a rank of 0.263, and so on. It is interesting to note that even though page E has the most inbound links, it doesn't have the highest PageRank. This is because page E only has one outbound link, to page D, so page D receives the entirety of page E's PageRank, plus a small contribution from page A. Exercise 1: (6 pts) Use the technique of the example above to nd the PageRanks of pages A, B, and C in the graph below. A B \\/ Example 1 (can't): Returning to our example, we may write the system of linear equations we found in matrix form: 0 0.5 0 0.5 0 r(A) 0.25 0 0.5 0 0 1(3) 0.25 0.5 0 0 0 F: ", where F: 'r(C) 0.25 0 0 0 1 TH?) 0.25 0 0.5 0.5 0 r(E) Denote the 5 x 5 matrix above by P. The columns of P describe the outbound links from each webpage (the rst column of P, for example, indicates that A has outbound links to B, C, D, and E, and equally distributes its PageRank among them). Because of this, the sum of the entries in each column of P is 1. In other words, P is a stochastic matrix, and can be thought of as the transition matrix of a Markov chain. Additionally, the vector P of PageRanks we are searching for is an eigenvector of P corresponding to the eigenvalue A = 1. Since the entries of *1" sum to 1, r" is actually a steady-state vector of P! Example 2: Consider the simple graph of links below: A B \\/ O' The corresponding matrix is: 000 P=1/200 1/210 The third column of P is the zero vector, so P is not the transition matrix of a Markov chain! If we access a random page (A, B, or C) and click links randomly, then we always end up stuck at C after at most two clicks. To remedy this, whenever we have a page that doesn't link to any other pages, we modify the link diagram so that the page links to all pages, even itself. In this example, we draw arrows from C to all three pages: A B \\/ 0 U The new matrix is: 0 0 1/3 P = 1/2 0 1/3 1/2 1 1/3 We call P the altered transition matrix. In general, if there are n webpages, then we form P from P by replacing any columns of zeroes by the vector (1, 1, ..., !). An altered transition matrix is always a stochastic matrix (why?), and should be used to find PageRanks if at least one webpage does not link to other pages. Exercise 2: (12 pts) Consider the link diagram below. A