Journal
INTERNET MATHEMATICS
Volume 2, Issue 3, Pages 333-358Publisher
TAYLOR & FRANCIS INC
DOI: 10.1080/15427951.2005.10129104
Keywords
-
Categories
Funding
- OTKA of the Hungarian National Science Fund [T 42481, T 42559, T 42706, T 44733]
- NKFP project Data Riddle [2/0017/2002]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available