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?).
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.
