8 K.BRYAN AND T.LEISE Show more generally that (AP)ij >0 if and only if page i can be reached from page j in EXACTLY p steps. Argue that (I+A+A2+...+AP)ij>0 if and only if page i can be reached from page j in p or fewer steps (note p=0 is a legitimate choice-any page can be reached from itself in zero steps!) .Explain why I+A+A2+...+An-1 is a positive matrir if the web is strongly connected. .Use the last part (and Exercise 8)so show that B=(I+A+A2+...+An-1)is positive and column-stochastic (and hence by Lemma 3.2,dim(Vi(B))=1). ·Show that if x∈(A)then x∈(B).Why does this imply that dim((A)=l? EXERCISE 11.Consider again the web in Figure 2.1,with the addition of a page 5 that links to page 3,where page 3 also links to page 5.Calculate the new ranking by finding the eigenvector of M (corresponding to A=1)that has positive components summing to one.Use m =0.15. EXERCISE 12.Add a sirth page that links to every page of the web in the previous exercise,but to which no other page links.Rank the pages using A,then using M with m =0.15,and compare the results. EXERCISE 13.Construct a web consisting of two or more subwebs and determine the ranking given by formula (3.1). At present the web contains at least eight billion pages-how does one compute an eigenvector for an eight billion by eight billion matrix?One reasonable approach is an iterative procedure called the power method(along with modifications)that we will now examine for the special case at hand. It is worth noting that there is much additional analysis one can do,and many improved methods for the computation of PageRank.The reference [7]provides a typical example and additional references. 4.Computing the Importance Score Eigenvector.The rough idea behind the power method2 for computing an eigenvector of a matrix M is this:One starts with a "typical"vector xo,then generates the sequence xk=Mxk-1(so xk=M*xo)and lets k approaches infinity.The vector xk is,to good approximation,an eigenvector for the dominant (largest magnitude)eigenvalue of M.However,depending on the magnitude of this eigenvalue,the vector xk may also grow without bound or decay to the zero vector.One thus typically rescales at each iteration,say by computingwhere can be any vector norm.The method generally requires that Mxk■ the corresponding eigenspace be one-dimensional,a condition that is satisfied in the case when M is defined by equation (3.1). To use the power method on the matrices M that arise from the web ranking problem we would generally need to know that any other eigenvalues A of M satisfy <1.This assures that the power method will converge to the eigenvector we want.Actually,the following proposition provides what we need,with no reference to any other eigenvalues of M! DEFINITION 4.1.The 1-norm of a vector v is llvl=i lvil. PROPOSITION 4.Let M be a positive column-stochastic n x n matrir and let V denote the subspace of R"consisting of vectors v such that vj=0.Then MvEV for any vV,and IMvl≤cllv for any v∈V,where c=max1≤≤nl1-2min1≤isn Mijl<1.Proof..To see that Mv∈Vis straightforward:Let w=Mv,so that wi=Mijvj and 三三三4g-店（②）小三=4 Hence w=Mv EV.To prove the bound in the proposition note that h-2-店（公） 2See [15]for a general introduction to the power method and the use of spectral decomposition to find the rate of convergence of the vectors xk=M"xo8 K. BRYAN AND T. LEISE • Show more generally that (Ap )ij > 0 if and only if page i can be reached from page j in EXACTLY p steps. • Argue that (I + A + A2 + · · · + Ap )ij > 0 if and only if page i can be reached from page j in p or fewer steps (note p = 0 is a legitimate choice—any page can be reached from itself in zero steps!) • Explain why I + A + A2 + · · · + An−1 is a positive matrix if the web is strongly connected. • Use the last part (and Exercise 8) so show that B = 1 n (I + A + A2 + · · · + An−1 ) is positive and column-stochastic (and hence by Lemma 3.2, dim(V1(B)) = 1). • Show that if x ∈ V1(A) then x ∈ V1(B). Why does this imply that dim(V1(A)) = 1? Exercise 11. Consider again the web in Figure 2.1, with the addition of a page 5 that links to page 3, where page 3 also links to page 5. Calculate the new ranking by finding the eigenvector of M (corresponding to λ = 1) that has positive components summing to one. Use m = 0.15. Exercise 12. Add a sixth page that links to every page of the web in the previous exercise, but to which no other page links. Rank the pages using A, then using M with m = 0.15, and compare the results. Exercise 13. Construct a web consisting of two or more subwebs and determine the ranking given by formula (3.1). At present the web contains at least eight billion pages—how does one compute an eigenvector for an eight billion by eight billion matrix? One reasonable approach is an iterative procedure called the power method (along with modifications) that we will now examine for the special case at hand. It is worth noting that there is much additional analysis one can do, and many improved methods for the computation of PageRank. The reference [7] provides a typical example and additional references. 4. Computing the Importance Score Eigenvector. The rough idea behind the power method2 for computing an eigenvector of a matrix M is this: One starts with a “typical” vector x0, then generates the sequence xk = Mxk−1 (so xk = Mkx0) and lets k approaches infinity. The vector xk is, to good approximation, an eigenvector for the dominant (largest magnitude) eigenvalue of M. However, depending on the magnitude of this eigenvalue, the vector xk may also grow without bound or decay to the zero vector. One thus typically rescales at each iteration, say by computing xk = Mxk−1 kMxk−1k , where k · k can be any vector norm. The method generally requires that the corresponding eigenspace be one-dimensional, a condition that is satisfied in the case when M is defined by equation (3.1). To use the power method on the matrices M that arise from the web ranking problem we would generally need to know that any other eigenvalues λ of M satisfy |λ| < 1. This assures that the power method will converge to the eigenvector we want. Actually, the following proposition provides what we need, with no reference to any other eigenvalues of M! Definition 4.1. The 1-norm of a vector v is kvk1 = P i |vi |. Proposition 4. Let M be a positive column-stochastic n × n matrix and let V denote the subspace of lRn consisting of vectors v such that P j vj = 0. Then Mv ∈ V for any v ∈ V , and kMvk1 ≤ ckvk1 for any v ∈ V , where c = max1≤j≤n |1 − 2 min1≤i≤n Mij | < 1. Proof. To see that Mv ∈ V is straightforward: Let w = Mv, so that wi = Pn j=1 Mijvj and Xn i=1 wi = Xn i=1 Xn j=1 Mijvj = Xn j=1 vj Xn i=1 Mij! = Xn j=1 vj = 0. Hence w = Mv ∈ V . To prove the bound in the proposition note that kwk1 = Xn i=1 eiwi = Xn i=1 ei   Xn j=1 Mijvj   , 2See [15] for a general introduction to the power method and the use of spectral decomposition to find the rate of convergence of the vectors xk = Mkx0