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?).
| 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
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
