pipette
ENEnglish

Nearly optimal Personalized PageRank computation

Rong-Hua Li, Yichun Yang, Junjie Zhou

Preprint

En palabras de los autores

We study the fundamental problem of computing Personalized PageRank (PPR) on an undirected and unweighted graph . We focus on the -error guarantee introduced by Andersen, Chung, and Lang [ACL; FOCS 2006 & Internet Math 2007]. Their classic local push method computes an approximate PPR vector satisfying the ACL -error guarantee in time, where is the teleportation parameter. In this paper, we eliminate the dependence on and present an algorithm that achieves the same error guarantee in time. Consequently, we obtain a nearly optimal algorithm for PPR computation under the ACL error guarantee, and a nearly linear algorithm for local graph clustering with complexity independent of .

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.