Analysis of an online algorithm for solving large Markov chains
Litvak, Nelly and Robert, Philippe (2008) Analysis of an online algorithm for solving large Markov chains. In: 3rd International Workshop on Tools for Solving Structured Markov Chains, SMCTools 2008, 2024 October 2008, Athens, Greece.

PDF
146kB 
Abstract:  Algorithms for ranking of web pages such as Google PageRank 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 precomputed offline, several challenging problems in contemporary web search, such as personalized search and search in entity graphs, require online PageRank computation. In this work we present a probabilistic point of view for an original online 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 twodimensional 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. 
Item Type:  Conference or Workshop Item 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/65207 
Official URL:  http://dx.doi.org/10.4108/ICST.VALUETOOLS2008.4425 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 254988