A sublinear time algorithm for PageRank computations

DOI10.1007/978-3-642-30541-2_4MaRDI QIDQ2900584zbMATH OpenOpenAlexFDO

Authors Michael Brautbar, Christian Borgs, Jennifer T. Chayes, Shang-Hua Teng

Publication date 23 July 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-30541-2_4

zbMATH Keywords

local randomized algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Social networks; opinion dynamics (91D30) Internet topics (68M11)

Recommendations

• Multiscale matrix sampling and sublinear-time PageRank computation
• Local Computation of PageRank Contributions
• Sublinear Algorithms for Local Graph-Centrality Estimation
• Local Computation of PageRank Contributions
• Estimating PageRank on graph streams

Cited in

(16)

• Bidirectional PageRank estimation: from average-case to worst-case
• Multiscale matrix sampling and sublinear-time PageRank computation
• Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
• On the complexity of the Monte Carlo method for incremental PageRank
• A Hessenberg-type algorithm for computing PageRank problems
• Fast distributed PageRank computation
• Ranking and sparsifying a connection graph
• On approximating the stationary distribution of time-reversible Markov chains
• On approximating the stationary distribution of time-reversible Markov chains
• On efficient randomized algorithms for finding the PageRank vector
• Sublinear Algorithms for Local Graph-Centrality Estimation
• Distributed PageRank computation with improved round complexities
• A parallel pagerank algorithm for undirected graph
• Solving local linear systems with boundary conditions using heat kernel pagerank
• Estimating PageRank on graph streams
• Quick detection of top-k personalized PageRank lists

This page was built for publication: A sublinear time algorithm for PageRank computations

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