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 directed arc from vertex to vertex exists if and only if page has a link out to page . Then a stochastic matrix is constructed from : for each set
if but there is no arc from to in .
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.