Re:Q: Why is PageRank so complicated?
by korch on Monday October 18, 2010 @04:49AM
(#1802740)
It's not just about eigenvectors, though that is the coolest part of it. The "magic" part is that PageRank is also about stochastic processes, which use the Ergodic theorem to show that their PageRank exists at an arbitrary scale. Therefore it doesn't matter how big or complex the link structure on the web gets—it will scale.
See this:
"For any matrix A = [cP + (1-c)E]' where P is an n×n row-stochastic
matrix, E is a nonnegative n×n rank-one row-stochastic matrix, and 0
=< c =< 1, the second eigenvalue of A has modulus less than or equal
to c. Furthermore, if P has at least two irreducible closed subsets,
the second eigenvalue is equal to c.
This statement has implications for the convergence rate of the
standard PageRank algorithm as the web scales, for the stability of
PageRank to perturbations to the link structure of the web, for the
detection of Google spammers, and for the design of algorithms to
speed up PageRank."
See this:
"For any matrix A = [cP + (1-c)E]' where P is an n×n row-stochastic matrix, E is a nonnegative n×n rank-one row-stochastic matrix, and 0 =< c =< 1, the second eigenvalue of A has modulus less than or equal to c. Furthermore, if P has at least two irreducible closed subsets, the second eigenvalue is equal to c.
This statement has implications for the convergence rate of the standard PageRank algorithm as the web scales, for the stability of PageRank to perturbations to the link structure of the web, for the detection of Google spammers, and for the design of algorithms to speed up PageRank."
http://answers.google.com/answers/threadview/id/379557.html