Markov Chains and Web Ranking: a Multilevel Adaptive Aggregation Method

  • Date: 05/18/2007
Lecturer(s):

De Sterck Hans (University of Waterloo)

Location: 

University of British Columbia

Topic: 

Google's PageRank method for ranking web pages models how a `random
surfer' follows links between web pages in a random fashion. The
stationary probability vector of the resulting Markov chain provides a
ranking of all the pages in the network. Calculating this stationary
probability vector is a very large problem: Google now indexes more
than 25 billion internet web pages. We present a multilevel adaptive
aggregation method for the linear algebra problem of calculating the
stationary probability vector of a Markov chain. The method described
is a variant of adaptive algebraic multigrid methods for sparse linear
systems, and is also related to existing aggregation methods for Markov
chains. We apply our multilevel method to a set of stochastic matrices
that provide models for web page ranking. These numerical tests serve
to illustrate for which types of stochastic matrices our multilevel
adaptive method may provide significant speedup compared to standard
iterative methods. The tests also provide some insight into why the
PageRank model is a successful model for determining a ranking of web
pages.

Other Information: 

SCAIM Seminar 2007

Sponsor: 

pims