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 $D$ is constructed whose vertices correspond to web pages and a directed arc from vertex $i$ to vertex $j$ exists if and only if page $i$ has a link out to page $j$. Then a stochastic matrix $A=(a_{ij})$ is constructed from $D$: for each $i,j$ set

 $a_{ij}=1/d(i)$

if the outdegree of vertex $i,d(i)$ is positive and there is an arc from $i$ to $j$ in $D$. Set

 $a_{ij}=0$

if $d(i)>0$ but there is no arc from $i$ to $j$ in $D$.

Set

 $a_{ij}=1/n$

if $d(i)=0$, where $n$ is the order of the matrix.

Having defined $A$ choose a positive row vector $v^{T}$ such that $v^{T}\textbf{1}=1$ where 1 is a vector of all ones. Finally, choose a constant $c\in(0,1)$. The Google matrix $G$ is

 $G=cA+(1-c)\textbf{1}v^{T}.$

Clearly, $G$ is stochastic. For the actual matrix that Google uses $c$ is about .85.

Title Google matrix GoogleMatrix 2013-03-22 17:01:05 2013-03-22 17:01:05 Mathprof (13753) Mathprof (13753) 6 Mathprof (13753) Definition msc 15A51