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.

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 n$matrix 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.

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.

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:

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.