The problem of approximating the PageRank score of a node with minimal information about the rest of the graph has attracted considerable attention in the last decade; but its central question, whether it is in general necessary to explore a non-vanishing fraction of the graph, remained open until now (only for specific graphs and/or nodes was a solution known). We present the first algorithm that produces a (1\pm\epsilon)-approximation of the score of any one node in any n-node graph with probability (1-\epsilon) visiting at most O(n^\frac{2}{3}\sqrt{\log(n)})=o(n) nodes. Our result is essentially tight (we prove that visiting \Omega(n^\frac{2}{3}) nodes is in general necessary to solve even an easier "ranking" version of the problem under any "natural" graph exploration model, including all those in the literature) but it can be further improved for some classes of graphs and/or nodes of practical interest - e.g. to O(n^\frac{1}{2} \gamma^\frac{1}{2}) nodes in graphs with maximum outdegree \gamma.

### Approximating PageRank locally with sublinear query complexity

#### Abstract

The problem of approximating the PageRank score of a node with minimal information about the rest of the graph has attracted considerable attention in the last decade; but its central question, whether it is in general necessary to explore a non-vanishing fraction of the graph, remained open until now (only for specific graphs and/or nodes was a solution known). We present the first algorithm that produces a (1\pm\epsilon)-approximation of the score of any one node in any n-node graph with probability (1-\epsilon) visiting at most O(n^\frac{2}{3}\sqrt{\log(n)})=o(n) nodes. Our result is essentially tight (we prove that visiting \Omega(n^\frac{2}{3}) nodes is in general necessary to solve even an easier "ranking" version of the problem under any "natural" graph exploration model, including all those in the literature) but it can be further improved for some classes of graphs and/or nodes of practical interest - e.g. to O(n^\frac{1}{2} \gamma^\frac{1}{2}) nodes in graphs with maximum outdegree \gamma.
##### Scheda breve Scheda completa Scheda completa (DC) 2014
http://arxiv.org/abs/1404.1864
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/2898701
##### Citazioni
• ND
• ND
• ND