Can one assess, by visiting only a small portion of a graph, if a given node has a significantly higher PageRank score than another? We show that the answer strongly depends on the interplay between the required correctness guarantees (is one willing to accept a small probability of error?) and the graph exploration model (can one only visit parents and children of already visited nodes?).

The power of local information in pagerank / M. Bressan, E. Peserico, L. Pretto - In: WWW '13 Companion: Proceedings / [a cura di] D. Schwabe,V. Almeida, H. Glaser, R. Baeza-Yates, S. Moon. - [s.l] : ACM, 2013. - ISBN 978-1-4503-2038-2. - pp. 179-180 (( Intervento presentato al 22. convegno International Conference on World Wide Web tenutosi a Rio de Janeiro nel 2013 [10.1145/2487788.2487878].

The power of local information in pagerank

M. Bressan;
2013

Abstract

Can one assess, by visiting only a small portion of a graph, if a given node has a significantly higher PageRank score than another? We show that the answer strongly depends on the interplay between the required correctness guarantees (is one willing to accept a small probability of error?) and the graph exploration model (can one only visit parents and children of already visited nodes?).
Graph ranking; Local computation; Pagerank
Settore INF/01 - Informatica
Banco do Brasil
BR PETROBRAS
Comite Gestor da Internet no Brazil (CGI.BR)
Microsoft
Nucleo de Informatcao e Coordenacao do Ponto BR (NIC.BR)
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
Bressan&2013-WWW.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 470 kB
Formato Adobe PDF
470 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/922274
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact