[Math] Convergence rate of PageRank, the problem when the second eigenvalue is complex

complex numbersconvergence-divergenceeigenvalues-eigenvectorsmarkov chainsmatrices

As far as I know the Google matrix used to calculate the PageRank is not symetric, that means that some eigenvalues can be complex, furthermore, we know that the second eigenvalue is equal to the damping factor (it's convergence rate to 0 is the same as the convergence rate to the stationary regime which is pagerank).

So in the case where this second eigenvalue is complex, how should I consider the damping factor d which is supposed to be real 0

Best Answer

The vector consisting of the rankings is mathematically the Perron vector of a stochastic matrix. There are more than one ways to determine the Perron vector. If I remember correctly, Google has actually never revealed the algorithm it employed to determine that vector, although an early paper by Brin and Page seems to suggest that the power method was used. So, strictly speaking, it does not make much sense for outsiders to speak of the convergence rate of PageRank algorithm.

If we assume that the power method is used, then the convergence rate is ratio of the modulus of the second dominant eigenvalue to the Perron eigenvalue. So, it doesn't matter whether the second dominant eigenvalue is real or nonreal.

By the way, your claim that the second dominant eigenvalue is the damping factor is untrue. It's easy to generate a random counterexample by computer.