TY - GEN

T1 - Analysis of an on-line algorithm for solving large Markov chains

AU - Litvak, Nelli

AU - Robert, Philippe

PY - 2008

Y1 - 2008

N2 - Algorithms for ranking of web pages such as Google Page-Rank assign importance scores according to a stationary distribution of a Markov random walk on the web graph. Although in the classical search scheme the ranking scores are pre-computed off-line, several challenging problems in contemporary web search, such as personalized search and search in entity graphs, require on-line PageRank computation. In this work we present a probabilistic point of view for an original on-line algorithm proposed by Abiteboul, Preda and Cobena [1]. According to this algorithm, at the beginning, each page receives an equal amount of ‘cash’, and every time when a page is visited by a random walk, it distributes its cash among its outgoing links. The PageRank score of a page is then proportional to the amount of cash transferred from this page. In this paper, instead of dealing with the variable ‘cash’, which is continuous, we create a two-dimensional discrete ‘cat and mouse’ Markov chain such that the amount of cash on each page can be expressed via probabilities for this new Markov chain. We also indicate further research directions, such as the analysis of the cat and mouse chain in the case when the cat’s movements are described by a classical stochastic process such as the M/M/1 random walk.

AB - Algorithms for ranking of web pages such as Google Page-Rank assign importance scores according to a stationary distribution of a Markov random walk on the web graph. Although in the classical search scheme the ranking scores are pre-computed off-line, several challenging problems in contemporary web search, such as personalized search and search in entity graphs, require on-line PageRank computation. In this work we present a probabilistic point of view for an original on-line algorithm proposed by Abiteboul, Preda and Cobena [1]. According to this algorithm, at the beginning, each page receives an equal amount of ‘cash’, and every time when a page is visited by a random walk, it distributes its cash among its outgoing links. The PageRank score of a page is then proportional to the amount of cash transferred from this page. In this paper, instead of dealing with the variable ‘cash’, which is continuous, we create a two-dimensional discrete ‘cat and mouse’ Markov chain such that the amount of cash on each page can be expressed via probabilities for this new Markov chain. We also indicate further research directions, such as the analysis of the cat and mouse chain in the case when the cat’s movements are described by a classical stochastic process such as the M/M/1 random walk.

KW - EWI-14592

KW - METIS-254988

KW - IR-65207

U2 - 10.4108/ICST.VALUETOOLS2008.4425

DO - 10.4108/ICST.VALUETOOLS2008.4425

M3 - Conference contribution

SN - 978-963-9799-31-8

SP - -

BT - Proceedings of the third International Workshop on Tools for Solving Structured Markov Chains, SMCTools 2008

PB - ICST

Y2 - 20 October 2008 through 24 October 2008

ER -