Google matrix
Google’s PageRank algorithm uses a particular stochastic matrix called the Google matrix.The purpose of the PageRank algorithm is to compute a stationary vector of the Google matrix.The stationary vector is then used to provide a ranking of the pages on the internet.
A directed graph is constructed whose vertices correspond to web pages and a directedarc from vertex to vertex exists if and only if page has a link out topage .Then a stochastic matrix is constructed from : for each set
if the outdegree of vertex is positive and there is an arc from to in .Set
if but there is no arc from to in .
Set
if , where is the order of the matrix.
Having defined choose a positive row vector such that where 1 is a vector of all ones.Finally, choose a constant .The Google matrix is
Clearly, is stochastic. For the actual matrix that Google uses is about .85.