The $25B Eigenvector: The Linear Algebra behind Google (2006)

The gist is that you can formulate the PageRank problem as a flow equation r = Mr, where r is a vector of PageRanks and M is a stochastic adjacency matrix, which can be interpreted as the probability of visiting one page from another.

This matrix is huge and hence this is tough to solve.

But since M is a stochastic matrix, it has the property that its largest eigenvalue is exactly 1, and all other eigenvalues are < 1. And the equation r = Mr can be interpreted as r being the eigenvector of M with eigenvalue 1, as this equation implies multiplying by M is equivalent to multiplying by 1.

Repeatedly multiplying by M hence shrinks every eigenvector except the eigenvector with eigenvalue 1. So you start with some initialization of r, and repeatedly multiply by M until it converges. The resulting value of r solves r = Mr since all other eigenvectors shrank towards zero.

This is a much more efficient way to compute r, and hence makes PageRank computationally feasible.

Interesting that Google has added two orders of magnitude to their market cap since going public in 2004.

https://nlp.stanford.edu/pubs/secondeigenvalue.pdf

The $25B eigenvector (2006) [pdf] - https://news.ycombinator.com/item?id=16091646 - Jan 2018 (68 comments)