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

Nelli Litvak, Philippe Robert

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

84 Downloads (Pure)

Abstract

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.
Original languageUndefined
Title of host publicationProceedings of the third International Workshop on Tools for Solving Structured Markov Chains, SMCTools 2008
PublisherICST
Pages-
Number of pages6
ISBN (Print)978-963-9799-31-8
DOIs
Publication statusPublished - 2008
Event3rd International Workshop on Tools for Solving Structured Markov Chains, SMCTools 2008 - Athens, Greece
Duration: 20 Oct 200824 Oct 2008

Publication series

Name
PublisherInstitute for Computer Sciences, Social-Informatics and Telecommunications Engineering (ICST)
NumberWoTUG-31

Workshop

Workshop3rd International Workshop on Tools for Solving Structured Markov Chains, SMCTools 2008
Period20/10/0824/10/08
Other20-24 October 2008

Keywords

  • EWI-14592
  • METIS-254988
  • IR-65207

Cite this