A Web Aggregation Approach for Distributed Randomized PageRank Algorithms

DOI10.1109/TAC.2012.2190161zbMATH Open1369.93695arXiv1203.6606OpenAlexW3103669764MaRDI QIDQ5352997FDOQ5352997

Authors: Hideaki Ishii, Er-wei Bai, Roberto Tempo 

Publication date: 8 September 2017

Published in: IEEE Transactions on Automatic Control (Search for Journal in Brave)

Abstract: The PageRank algorithm employed at Google assigns a measure of importance to each web page for rankings in search results. In our recent papers, we have proposed a distributed randomized approach for this algorithm, where web pages are treated as agents computing their own PageRank by communicating with linked pages. This paper builds upon this approach to reduce the computation and communication loads for the algorithms. In particular, we develop a method to systematically aggregate the web pages into groups by exploiting the sparsity inherent in the web. For each group, an aggregated PageRank value is computed, which can then be distributed among the group members. We provide a distributed update scheme for the aggregated PageRank along with an analysis on its convergence properties. The method is especially motivated by results on singular perturbation techniques for large-scale Markov chains and multi-agent consensus.

Full work available at URL: https://arxiv.org/abs/1203.6606

Mathematics Subject Classification ID

Applications of graph theory (05C90) Stochastic stability in control theory (93E15) Internet topics (68M11)

Cited In (9)

• Hierarchical consensus problem in hybrid multiagent systems
• Reach almost sure consensus with only group information
• Reach almost sure consensus via \(L_p\)-norm group information
• PageRank computation via a distributed randomized approach with lossy communication
• Impact of minimum-cut density-balanced partitioning solutions in distributed webpage ranking
• Consensus of high-order multi-agent systems with large input and communication delays
• Sparse and distributed Analytic Hierarchy Process
• Control of multiple viruses interacting and propagating in multilayer networks
• Random block coordinate descent methods for linearly constrained optimization over networks

This page was built for publication: A Web Aggregation Approach for Distributed Randomized PageRank Algorithms

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