Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient

DOI10.1137/050643799zbMath1146.60056OpenAlexW2107577105MaRDI QIDQ5386203

Nelly Litvak, Danil Nemirovsky, Natalia Osipova, Konstantin E. Avrachenkov

Publication date: 22 April 2008

Published in: SIAM Journal on Numerical Analysis (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050643799

zbMATH Keywords

absorbing Markov chainPageRankGoogleMonte Carlo Methods

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Discrete-time Markov processes on general state spaces (60J05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Numerical analysis or methods applied to Markov chains (65C40)

Related Items (18)

An efficient Monte Carlo approach to compute PageRank for large graphs on a single PC ⋮ Efficient numerical methods to solve sparse linear equations with application to PageRank ⋮ Accelerating the Arnoldi-type algorithm for the PageRank problem and the ProteinRank problem ⋮ Red light green light method for solving large Markov chains ⋮ PageRank computation via a distributed randomized approach with lossy communication ⋮ On perturbations of principal eigenvectors of substochastic matrices ⋮ Sublinear Algorithms for Local Graph-Centrality Estimation ⋮ A parallel pagerank algorithm for undirected graph ⋮ Distributed PageRank computation with improved round complexities ⋮ Probabilistic Relation between In-Degree and PageRank ⋮ On the complexity of the Monte Carlo method for incremental PageRank ⋮ Fast distributed PageRank computation ⋮ An Arnoldi-extrapolation algorithm for computing pagerank ⋮ Distribution of PageRank Mass Among Principle Components of the Web ⋮ Multiplicative Approximations of Random Walk Transition Probabilities ⋮ Multiscale Matrix Sampling and Sublinear-Time PageRank Computation ⋮ Multiway Monte Carlo Method for Linear Systems ⋮ A Hessenberg-type algorithm for computing PageRank problems

This page was built for publication: Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient