期刊
INTERNET MATHEMATICS
卷 2, 期 3, 页码 333-358出版社
TAYLOR & FRANCIS INC
DOI: 10.1080/15427951.2005.10129104
关键词
-
资金
- OTKA of the Hungarian National Science Fund [T 42481, T 42559, T 42706, T 44733]
- NKFP project Data Riddle [2/0017/2002]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据