I was trying to understand how to use the inverse interation method to compute the page rank as an exercise.In this chapter (page 4) about page rank (by Cleve Moler), the author suggests to use the following statements to compute the page rank using the inverse iteration:c = sum(G, 1);k = find(c ~= 0);D = sparse(k, k, 1 ./ c(k), n, n);e = ones(n, 1);I = speye(n, n);...A = p*G*D + deltax = (I - A) \ ex = x / sum(x)where p should be the probability that a random walk follows a link and delta should be (1 - p) / n (as far I've understood), i.e. the probability that a particular random page is chosen. Note that 1 - p is the probability that some arbitrary page is chosen.Now, in the chapter 8 of the book A First Course in Numerical Methods (about Eigenvalues and Singular Values), at page 228 (at least in this version that I've), there's the following inverse iteration method:Main QuestionsExcluding the calculation of $\lambda$ (the eigenvalue), what's the relation between this inverse iteration and the previous? How does one reach from this last exposure of the algorithm (in the picture) to the Matlab implementation above? A step by step procedure would really be appreciated!Notes (so that you don't have to answer to these):I understood that the shift inverse method consists in finding the eigenven values of $(A - \alpha I)^{-1}$ instead of $A$. Even though I can't visualize really how this would be helpful.I understood that $(A - \alpha I)\tilde{v} = v_{k - 1}$ comes from $\tilde{v} = (A - \alpha I)^{-1}v_{k - 1}$, but we don't want to compute the inverse of $(A - \alpha I)$.I understood that we can choose $\alpha$ (so that it's close to the wanted eigenvalue). Since we know that the sought eigenvalue is $1$, we the statement $(A - \alpha I)$ may simplify to $(A - I)$...Other Minor QuestionsWhy are we using delta in A = p*G*D + delta.What's A in the inverse iteration of the picture?Again in this chapter (page 4) about page rank (by Cleve Moler), the author says (after those statements above) that (I - A) is theoretically singular. Why is that? And how could we avoid it?
PageRank using Inverse Iteration Method by Cleve Moler
matlab;eigenvalues;iterative method;graph theory;numerical