1
$\begingroup$

I was reading a paper about the PageRank algorithm and it mentions $ 2 $ ways to compute the weighted score for each vertex: If $ M_{n \times n} $ is a positive column stochastic matrix that represents the transition state for each vertex in the graph, then we know that the sequence $ Mz, M^{2}z, \dots, M^{k}z $ converges for $ z = [\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}]^{T}. $ This is the first way to compute the final weighted score. The second way is to find the probabilistic eigenvector $ v^{\ast} $ corresponding to the eigenvalue $ 1 $ of $ M $ (we know that $ M $ must have $ 1 $ as one of its eigenvalue from the P-F Theorem).

For the first approach, the rate of convergence is $ \frac{1}{|\lambda_{2}|} $ where $ \lambda_{2} $ is the second largest eigenvalue (in magnitude) of $ M $ and for the second approach, computing $ v^{\ast} $ has runtime complexity of $ O(n^3) $ where $ n $ is the size of the matrix $ M. $

So my question is suppose I want to determine which approach requires less time to perform, is there any metric to compare the $ 2 $ approaches?

This is how I understand the notation of "rate of convergence" and its relation to big-O notation, but there's no explicit function for the iterative method to do the limit computation, so I am currently stuck. Is that what you have in mind when you say about the concept of convergence? If no, can you tell me how you understand this concept?

$\endgroup$
  • 2
    $\begingroup$ Have you tried to work out what the running time of the first approach will be? It should follow immediately from the definition of "rate of convergence". Try writing it down, then comparing to what you know the runtime of the second approach is. If you understand "the rate of convergence", this should be an easy exercise. If you don't, you should probably instead asking questions about what that concept means. $\endgroup$ – D.W. Jul 18 '16 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.