GoogleMatrix 2007-04-29 22:44:07 2007-04-29 22:48:06 Definition % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here 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 $\textbf{1}$ is a vector of all ones. Finally, choose a constant $c \in (0,1)$. The \emph{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.