Can one assess, by visiting only a small portion of a graph, if a given node has a signicantly 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

BRESSAN, MARCO;PESERICO STECCHINI NEGRI DE SALVI, ENOCH;PRETTO, LUCA
2013

Abstract

Can one assess, by visiting only a small portion of a graph, if a given node has a signicantly 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?).
2013
Proceedings of the 22nd International World Wide Web Conference (WWW 2013)
9781450320382
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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/11577/2603845
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 9
social impact