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±ϵ)-approximation of the score of any given node with probability (1−δ), using at most On2/3 ln(n)1/3 ln(1/δ)2/3ϵ−2/3 = Õ(n2/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 OE4/5d−3/5 ln(n)1/5 ln(1/δ)3/5ϵ−6/5 = Õ(E4/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 / M. Bressan, E. Peserico, L. Pretto - In: SPAA '18: Proceedings[s.l] : ACM, 2018. - ISBN 9781450357999. - pp. 87-89 (( Intervento presentato al 30. convegno SPAA tenutosi a Wien nel 2018 [10.1145/3210377.3210664].

Brief announcement: On approximating pageRank locally with sublinear query complexity

M. Bressan
Primo
;
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±ϵ)-approximation of the score of any given node with probability (1−δ), using at most On2/3 ln(n)1/3 ln(1/δ)2/3ϵ−2/3 = Õ(n2/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 OE4/5d−3/5 ln(n)1/5 ln(1/δ)3/5ϵ−6/5 = Õ(E4/5) arcs, where E is the total number of arcs in the graph and d is its average degree.
Local computation; PageRank; Query complexity; Random walks; Sublinear algorithms
Settore INF/01 - Informatica
ACM SIGACT
ACM SIGARCH
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
Bressan&2018-SPAA.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.1 MB
Formato Adobe PDF
1.1 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento 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/2434/922288
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact