Skip to main content



Linear Algebra in Ranking Algorithms.

When we learned about the ranking algorithm in class, we used simple algebra and intuition to create a series of equations to solve our long-time equilibrium solution. How do we achieve this using a standardized method with computers? Ultimately, the millions of web pages are too big for humans to handle and a standard method that computers can use is needed. We look to linear algebra for our answer.

http://online.sfsu.edu/meredith/Linear_Algebra/725_F2010/PDF/Dynneson_FinalDraft_Linear-Algebra-Project.pdf
The first idea is to use Markov chains to create a stochastic model for the page ranking algorithm. The idea is that a matrix represents the pages, and repeated calculations of the matrix using linear algebra should result in an equilibrium similar to the one discussed in class. In the matrix, let a[i,j] represent the row i and column j. a[i,j] also represents if there is a link connected from j to i. If there is not, this value is 0, if there is, this value is non-zero. The columns must add up to 1 so each a[i,j] in column 3, for example, must add up to 1 evenly. This will then be repeatedly calculated to find the equilibrium.

https://www.rose-hulman.edu/~bryan/googleFinalVersionFixed.pdf
Similarly, another method if using linear algebra is using eigenvector. Similar to the previous method, eigenvectors which correspond to an eigenvalue are very helpful in determining solutions for matrix after a long time i.e. a million updates for example. Since this algorithm also uses linear algebra, it becomes a much simpler problem for computers to solve as well.

Both methods of finding page ranking use linear algebra, a method computer can easily solve. Like in our class, isolated and dangling nodes break the solution so the solution to that is to isolate the node from the calculation and continue the calculation. While the algebraic method in class might be a more intuitive way for humans to solve the problem of page ranking, it is much faster to use the standardized linear algebra for computers to solve the page ranking problem.

Comments

Leave a Reply

Blogging Calendar

October 2018
M T W T F S S
« Sep   Nov »
1234567
891011121314
15161718192021
22232425262728
293031  

Archives