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

DOI10.1137/050643799MaRDI QIDQ5386203zbMATH OpenOpenAlexFDO

Authors Nelly Litvak, Danil Nemirovsky, Natalia Osipova, Konstantin 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 chainGoogleMonte Carlo MethodsPageRank

Mathematics Subject Classification ID

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) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Recommendations

• On the complexity of the Monte Carlo method for incremental PageRank
• An efficient Monte Carlo approach to compute PageRank for large graphs on a single PC
• Several relaxed iteration methods for computing PageRank
• On the multi-splitting iteration method for computing PageRank
• On a generalized two-stage iterative method for computing PageRank
• A general multi-splitting iteration method for computing PageRank
• On convergence of the inner-outer iteration method for computing Pagerank
• The coupled iteration algorithms for computing PageRank
• A relaxed two-step splitting iteration method for computing PageRank
• An inner-outer iteration for computing PageRank

Cited in

(23)

• PageRank computation via a distributed randomized approach with lossy communication
• A Hessenberg-type algorithm for computing PageRank problems
• On the complexity of the Monte Carlo method for incremental PageRank
• Red light green light method for solving large Markov chains
• An efficient Monte Carlo approach to compute PageRank for large graphs on a single PC
• Comparing two page importance algorithms in probabilistic view
• Multiplicative Approximations of Random Walk Transition Probabilities
• Probabilistic Relation between In-Degree and PageRank
• Accelerating the Arnoldi-type algorithm for the PageRank problem and the ProteinRank problem
• Fast distributed PageRank computation
• Multiscale matrix sampling and sublinear-time PageRank computation
• Efficient numerical methods to solve sparse linear equations with application to PageRank
• Multiway Monte Carlo method for linear systems
• Distribution of PageRank Mass Among Principle Components of the Web
• Using Polynomial Chaos to Compute the Influence of Multiple Random Surfers in the PageRank Model
• Accelerating PageRank computations
• Sublinear Algorithms for Local Graph-Centrality Estimation
• A parallel pagerank algorithm for undirected graph
• Distributed PageRank computation with improved round complexities
• Connectivity of random graphs after centrality-based vertex removal
• Randomly sparsified Richardson iteration: a dimension-independent sparse linear solver
• On perturbations of principal eigenvectors of substochastic matrices
• An Arnoldi-extrapolation algorithm for computing pagerank

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5386203)