## You are here

HomeGoogle matrix

## Primary tabs

# 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 $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$.

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.

## Mathematics Subject Classification

15A51*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections