A Software Tool for the Steady–State Analysis of Google–like Stochastic Matrices

Tugrul Dayar; Gokce Nil  Noyan

4th International ICST Workshop on Tools for solving Structured Markov Chains

Research Article

A Software Tool for the Steady–State Analysis of Google–like Stochastic Matrices

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/ICST.VALUETOOLS2009.7453,
    author={Tugrul Dayar and Gokce Nil  Noyan},
    title={A Software Tool for the Steady--State Analysis of Google--like Stochastic Matrices},
    proceedings={4th International ICST Workshop on Tools for solving Structured Markov Chains},
    publisher={ACM},
    proceedings_a={SMCTOOLS},
    year={2010},
    month={5},
    keywords={Markov chains steady\{state vector Google},
    doi={10.4108/ICST.VALUETOOLS2009.7453}
}

Tugrul Dayar
Gokce Nil Noyan
Year: 2010
A Software Tool for the Steady–State Analysis of Google–like Stochastic Matrices
SMCTOOLS
ICST
DOI: 10.4108/ICST.VALUETOOLS2009.7453

Tugrul Dayar¹^,*, Gokce Nil Noyan²^,*

1: Department of Computer Engineering, Bilkent University, TR06800 Bilkent, Ankara, Turkey.
2: Undersecretariat for Defence Industries, Ziyabey Caddesi, 21 Sokak, No.4 TR06520 Balgat, Ankara, Turkey.

*Contact email: tugrul@cs.bilkent.edu.tr, gnnoyan@ssm.gov.tr

Abstract

The problem of computing the steady-state vector of positive stochastic matrices which are convex combinations of sparse, nonnegative matrices possibly having zero rows with appropriately chosen rank-1 matrices is addressed by a software tool. The dynamically changing matrices used by the Google search engine in ranking web pages are among the largest of such matrices. Ranking pages amounts to solving for the steady-state vectors of these matrices. The tool implements the power, quadratically extrapolated power, and iterative methods based on various block partitionings, including those with block triangular form and with triangular blocks obtained using cutsets.

Keywords: Markov chains steady{state vector Google

Published: 2010-05-16
Publisher: ACM
Modified: 2010-05-16

: http://dx.doi.org/10.4108/ICST.VALUETOOLS2009.7453