Tipo di prodotto | Articolo in rivista |
---|---|
Titolo | A Web Aggregation Approach for Distributed Randomized PageRank Algorithms |
Anno di pubblicazione | 2012 |
Formato |
|
Autore/i | Ishii, Hideaki; Tempo, Roberto; Bai, Er-Wei |
Affiliazioni autori | Tokyo Institute of Technology, Japan; CNR-IEIIT; University of Iowa |
Autori CNR e affiliazioni |
|
Lingua/e |
|
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. |
Lingua abstract | inglese |
Altro abstract | - |
Lingua altro abstract | - |
Pagine da | 2703 |
Pagine a | 2717 |
Pagine totali | 15 |
Rivista | IEEE transactions on automatic control (Print) Attiva dal 1963 Editore: Institute of Electrical and Electronics Engineers, - New York, N.Y. Paese di pubblicazione: Stati Uniti d'America Lingua: inglese ISSN: 0018-9286 Titolo chiave: IEEE transactions on automatic control (Print) Titolo proprio: IEEE transactions on automatic control. (Print) Titolo abbreviato: IEEE trans. automat. contr. (Print) Titoli alternativi:
|
Numero volume della rivista | 57 |
Fascicolo della rivista | 11 |
DOI | 10.1109/TAC.2012.2190161 |
Verificato da referee | Sì: Internazionale |
Stato della pubblicazione | Published version |
Indicizzazione (in banche dati controllate) |
|
Parole chiave | Aggregation, distributed computation, multi-agent consensus, PageRank algorithm, randomization, search engines, stochastic matrices |
Link (URL, URI) | - |
Titolo parallelo | - |
Data di accettazione | - |
Note/Altre informazioni | - |
Strutture CNR |
|
Moduli CNR | |
Progetti Europei | - |
Allegati |
|
