Google matrix

Google’s PageRank algorithmMathworldPlanetmath 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 graphMathworldPlanetmath 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=(aij) is constructed from D: for each i,j set


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


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



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

Having defined A choose a positive row vectorMathworldPlanetmath vT such that vT𝟏=1 where 1 is a vector of all ones. Finally, choose a constant c(0,1). The Google matrix G is


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

Title Google matrix
Canonical name GoogleMatrix
Date of creation 2013-03-22 17:01:05
Last modified on 2013-03-22 17:01:05
Owner Mathprof (13753)
Last modified by Mathprof (13753)
Numerical id 6
Author Mathprof (13753)
Entry type Definition
Classification msc 15A51