.

Mathematical Properties and Analysis of Google’s PageRank

Ilse C.F. Ipsen, Rebecca S. Wills

might help.

http://www4.ncsu.edu/~ipsen/ps/cedya.pdf

.

To answer my question;

BackRub (PageRank)'s webcrawler, as defined in this paper, creates a square matrix of 26 million web pages, which the inventors normalize using their dampening factor and whatever other tricks they have up their sleeve that they have chosen not to enumerate to us. Then they decompose the matrix into eigenvectors and eigenvalues.

Any eigenvector has the property \|v\|_2 = 1, and as such the entries in v correspond to a probability distribution, a vector of mutually exclusive and exhaustive situations (i.e. that a random walker that follows links on the internet lands on a page). As such, the principal eigenvector of the adjacency matrix of the web is also a probability distribution.,

Letting A be the normalized link matrix of the web, we can see that PageRank PR(A) converges to A^k b for any arbitrary b we choose.

Assume that A = Q \Lambda Q^{-1}, an eigenvalue decomposition, with Q being the set of eigenvectors of A.

The principal eigenvector is obtained (naively) through power iteration, continuous multiplication of A.

For each individual iteration, multiplication by the matrix A of any vector b scales b according to the eigenvalues and eigenvectors of A. Using the notation above, q_i \in Q are the directions that the vector is scaled in, and \lambda_i \in \Lambda is the magnitude of the transformation of b in the q_i direction.

What this means is that b' = Ab is scaled in the direction of all eigenvectors, but it is scaled with greater magnitude ("stretched further") in the q_i direction. If we normalize v such that \|v\|_2 = 1, then we have a unit vector that--no matter what b we chose, is closer to q_1 than it was before.

If we multiply the resultant vector by A again and normalize, we get another unit vector with still smaller euclidean distance from the true q_1.

Upon normalization, A^i b = q_1 + \varepsilon_i and A^{i+1} b = q_1 + \varepsilon_{i+1} produce error terms such that \varepsilon_{i+1} < \varepsilon_{i}.

Performing this calculation k times, A^k b*, converges to q_1, as every single iteration gets us closer, so as k goes to infinity, \varepsilon_k goes to zero, and we are guaranteed that the limit is q_1.

The eigenvalue decomposition is stable (enough) and unique for a square matrix, and as such it converges. As for the probability distribution they mention, the principal eigenvector, normalized, has value one, or in other words, squaring the components of this eigenvector such that they are nonnegative yields a vector that sums to one.

More information on eigenvalues and eigenvectors:

http://en.wikipedia.org/wiki/Eig...

*Whereas A counts the number of paths of length 1 and A^2 counts the number of paths of length 2 from i to j, A^k counts all paths of length k.