Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
Towards Scaling Fully Personalized PageRank: Algorithms, Lower Bounds, and Experiments
复制标题
DOI：
10.1080/15427951.2005.10129104
复制
发表时间：
2005-01-01
影响因子：
--
通讯作者：
Sarlos, Tamas
中科院分区：
文献类型：
--
作者：
Fogaras, Daniel;Racz, Balazs;Sarlos, Tamas
个性化 PageRank 表示用户选择的页面周围基于链接的页面质量，其方式与 PageRank 表示整个网络的质量类似。然而，现有的个性化 PageRank 算法只能为有限的页面选择提供在线查询服务。在本文中，我们通过一种预先计算紧凑数据库的新颖算法实现了完全个性化；使用该数据库，它可以对任意用户选择的个性化提供在线响应。该算法使用模拟随机游走；我们证明，对于固定的错误概率，我们的数据库大小与网页数量呈线性关系。我们通过渐近最坏情况下界证明我们的估计方法的合理性：我们表明，在某些图集上，精确的个性化 PageRank 值只能从大小与顶点数量成二次方的数据库中获得。此外，我们在斯坦福 WebBase 图上通过实验评估了近似精度。
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.