A Web Aggregation Approach for Distributed Randomized PageRank Algorithms

Hideaki ISHII; Roberto TEMPO; Er-Wei BAI

doi:10.1109/TAC.2012.2190161

Back

A Web Aggregation Approach for Distributed Randomized PageRank Algorithms

Journal article

Peer reviewed

A Web Aggregation Approach for Distributed Randomized PageRank Algorithms

Hideaki ISHII, Roberto TEMPO and Er-Wei BAI

IEEE transactions on automatic control, Vol.57(11), pp.2703-2717

2012

DOI: 10.1109/TAC.2012.2190161

Files and links (1)

url

https://arxiv.org/pdf/1203.6606View

Open Access

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. A numerical example is provided to illustrate the level of reduction in computation while keeping the error in rankings small.

Applied Sciences

Software

Memory organisation. Data processing

Information systems. Data bases

Exact sciences and technology

Computer systems and distributed systems. User interface

Artificial intelligence

Computer science; control theory; systems

Details

Title: Subtitle: A Web Aggregation Approach for Distributed Randomized PageRank Algorithms
Creators: Hideaki ISHII - Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Yokohama 226-8502, Japan
Roberto TEMPO - CNR-IEIIT, Politecnico di Torino, 10129 Turin, Italy
Er-Wei BAI - Department of Electrical and Computer Engineering, The University of Iowa, Iowa City, IA 52242-1527, United States
Resource Type: Journal article
Publication Details: IEEE transactions on automatic control, Vol.57(11), pp.2703-2717
DOI: 10.1109/TAC.2012.2190161
ISSN: 0018-9286
eISSN: 1558-2523
Publisher: Institute of Electrical and Electronics Engineers
Language: English
Date published: 2012
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984083994402771

Metrics

21 Record Views

52 Times Cited - Web of Science