Can one compute the PageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n -node graph, returns a multiplicative $(1\pmε)$-approximation of the score of any given node with probability $(1-δ)$, using at most $O\big(n^2/3 łn(n)^1/3 łn(1/δ)^2/3 ε^-2/3 \big) = \tildeO (n^2/3 )$ queries which return either a node chosen uniformly at random, or the list of neighbours of a given node. Alternatively, we show that the same guarantees can be attained by fetching at most $O\big( E^4/5 d^-3/5 łn(n)^1/5 łn(1/δ)^3/5 ε^-6/5 \big) = \tildeO (E^4/5 )$ arcs, where E is the total number of arcs in the graph and d is its average degree.

Brief announcement: On approximating pageRank locally with sublinear query complexity

Peserico, Enoch;Pretto, Luca
2018

Abstract

Can one compute the PageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n -node graph, returns a multiplicative $(1\pmε)$-approximation of the score of any given node with probability $(1-δ)$, using at most $O\big(n^2/3 łn(n)^1/3 łn(1/δ)^2/3 ε^-2/3 \big) = \tildeO (n^2/3 )$ queries which return either a node chosen uniformly at random, or the list of neighbours of a given node. Alternatively, we show that the same guarantees can be attained by fetching at most $O\big( E^4/5 d^-3/5 łn(n)^1/5 łn(1/δ)^3/5 ε^-6/5 \big) = \tildeO (E^4/5 )$ arcs, where E is the total number of arcs in the graph and d is its average degree.
2018
Annual ACM Symposium on Parallelism in Algorithms and Architectures
9781450357999
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/3299957
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact