We use a few cookies

Essential cookies keep the library working. With your permission, we'd also like to use analytics to see what's useful and improve the experience. Read our Privacy Policy or Cookie Policy.

Skip to main content
Home/e-Resources/Mathematics/Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
PeriodicalsMathematics

Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments

Checking your access to this record.

Abstract & Overview

Personalized PageRank expresses link-based page quality around userselected pages in a similar way as PageRank expresses quality over the entire web. Existing personalized PageRank algorithms can, however, serve online queries only for a restricted choice of pages. In this paper we achieve full personalization by a novel algorithm that precomputes a compact database; using this database, it can serve online responses to arbitrary user-selected personalization. The algorithm uses simulated random walks; we prove that for a fixed error probability the size of our database is linear in the number of web pages. We justify our estimation approach by asymptotic worst-case lower bounds: we show that on some sets of graphs, exact personalized PageRank values can only be obtained from a database of size quadratic in the number of vertices. Furthermore, we evaluate the precision of approximation experimentally on the Stanford WebBase graph.

Cite this record

Dániel Fogaras, Balázs Rácz, Károly Csalogány, Tamás Sarlós (2005). Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments. Internet Mathematics, 2(3), 333–358. https://doi.org/10.1080/15427951.2005.10129104

Copy in another style

Fogaras, D., Rácz, B., Csalogány, K., & Sarlós, T. (2005). Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments. Internet Mathematics, 2(3), 333–358. https://doi.org/10.1080/15427951.2005.10129104
Author names are used as deposited, so check their order before you submit.

Metadata is harvested from open-access indexes and can be incomplete. Check a citation against the published version before relying on it — see our open access & attribution policy.