jump to navigation

Does Google uses the theory from 1800’s to rank a Site ?? Wednesday, February 7, 2007

Posted by sarasotapodcast in Blogroll, Feed, My Favorite Tags, Sarasota Podcast.
add a comment

Does Google uses the theory from 1800’s to rank a Site ??

While I was going thru the Google Algorithm and ranking theory, came up with some fascinating facts and interesting theories used to rank a website. Find all the related links and resources below


Perron-Frobenius theorem:
Perron–Frobenius theorem, named after Oskar Perron and Ferdinand Georg Frobenius, is a theorem in matrix theory about the eigenvalues and eigenvectors of a real positive
n×n matrix.

 

Perron-Frobenius theorem has particular use in algebraic graph theory.  The “underlying graph” of a nonnegative real n \times nmatrix is the graph with vertices 1, \ldots, n and arc ij if and only if  A_{ij}\neq 0. If the underlying graph of such a matrix is strongly connected, then the matrix is irreducible, and thus the generalized Perron-Frobenius theorem applies.

 

Google page rank:

PageRank relies on the uniquely democratic nature of the web by using its vast link structure as an indicator of an individual page’s value. In essence, Google interprets a link from page A to page B as a vote, by page A, for page B. But, Google looks at more than the sheer volume of votes, or links a page receives; it also analyzes the page that casts the vote. Votes cast by pages that are themselves “important” weigh more heavily and help to make other pages “important.
For more info: http://www.google.com/technology/

 

Please let me know your thoughts and comments, even thou Math is not my subject, definitely love to hear from people who are good at Math.

 

References:

  1. http://209.85.165.104/search?q=cache:PjNaBazSGRYJ:www.chachadays.org/Govan-ChaCha06.pdf+Perron%E2%80%93Frobenius+theorem+and+google&hl=en&ct=clnk&cd=8&gl=us
  2. http://www.gnxp.com/MT2/archives/001364.html
  3. http://pdfdl.oceighty.net/pdf2html.php?url=http://people.ccmr.cornell.edu/~ginsparg/INFO295/pr.pdf
  4. http://www9.org/w9cdrom/251/251.html

 

Theorem 2.1 (Perron-Frobenius Theorem )
Source: http://www9.org/w9cdrom/251/251.html

If a n-dimensional matrix is positive or non-negative irreducible, then

  • The spectrum radius of , , is also a latent root of ;
  • There is a positive eigenvector of corresponding to ;
  • The eigenfunction of has a single root , i.e., ,
  • ��

Although the rank algorithms based on linkage structure break through the limitation of traditional IR technology, they still have some shortcomings:

  • Only the authority metric has been taken into account;
  • The iterative computation results in bad performance;
  • It is difficult to deal with the overflow or underflow problem during iteration;
  • Because of the “rank sink problem”, the iterative computation may not converge.
Advertisements