TITLE: Steady-state analysis of Google-like stochastic matrices with 
block iterative methods   

AUTHORS: Tugrul Dayar and Gokce N. Noyan  

ABSTRACT: A Google–like matrix is a positive stochastic matrix given by a 
convex combination of a sparse, nonnegative matrix and a particular rank 
one matrix. Google itself uses the steady–state vector of a large matrix 
of this form to help order web pages in a search engine. We investigate 
the computation of the steady–state vectors of such matrices using block 
iterative methods. The block partitionings considered include those based 
on block triangular form and those having triangular diagonal blocks 
obtained using cutsets. Numerical results show that block Gauss–Seidel 
with partitionings based on block triangular form is most often the best 
approach. However, there are cases in which a block partitioning with 
triangular diagonal blocks is better, and the Gauss–Seidel method is 
usually competitive.

KEY WORDS: Google; PageRank; stochastic matrices; power method; block 
iterative methods; partitionings; cutsets; triangular blocks