Estimating PageRank on graph streams

DOI10.1145/1970392.1970397MaRDI QIDQ3016259zbMATH OpenOpenAlexFDO

Authors Atish Das Sarma, Sreenivas Gollapudi, Rina Panigrahy

Publication date 14 July 2011

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.155.3159

zbMATH Keywords

algorithmsgraph conductancemixing timePageRankrandom walkstreaming algorithms

Mathematics Subject Classification ID

Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Internet topics (68M11) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fast distributed PageRank computation
• A sublinear time algorithm for PageRank computations
• \texttt{PageRank} and random walks on graphs
• An efficient Monte Carlo approach to compute PageRank for large graphs on a single PC
• Local Computation of PageRank Contributions

Cited in

(20)

• Local community detection in dynamic graphs using personalized centrality
• Active exploration for large graphs
• Graph sketching and streaming: new approaches for analyzing massive graphs
• 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
• A sublinear time algorithm for PageRank computations
• Buyback problem -- approximate matroid intersection with cancellation costs
• Multiplicative Approximations of Random Walk Transition Probabilities
• Superlinear lower bounds for multipass graph processing
• Bidirectional PageRank estimation: from average-case to worst-case
• Representing and Quantifying Rank - Change for the Web Graph
• Data mining of social networks represented as graphs
• Fast distributed PageRank computation
• Simulating random walks on graphs in the streaming model
• Evolutionary network analysis: a survey
• Intrinsic graph structure estimation using graph Laplacian
• Distributed PageRank computation with improved round complexities
• \textit{m-PageRank}: a novel centrality measure for multilayer networks
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• New algorithms and lower bounds for streaming tournaments

This page was built for publication: Estimating PageRank on graph streams

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