A Web Aggregation Approach for Distributed Randomized PageRank Algorithms
A Web Aggregation Approach for Distributed Randomized PageRank Algorithms
复制标题
DOI：
10.1109/tac.2012.2190161
复制
发表时间：
2012-03
影响因子：
6.8
通讯作者：
H. Ishii;R. Tempo;E. Bai
中科院分区：
文献类型：
--
作者：
H. Ishii;R. Tempo;E. Bai
Google 采用的 PageRank 算法为每个网页分配了一个重要性衡量标准，用于在搜索结果中排名。在我们最近的论文中，我们为该算法提出了一种分布式随机方法，其中网页被视为通过与链接页面通信来计算自己的 PageRank 的代理。本文基于这种方法来减少算法的计算和通信负载。特别是，我们开发了一种通过利用网络固有的稀疏性来系统地将网页聚合成组的方法。对于每个组，计算聚合的 PageRank 值，然后可以将其分配给组成员。我们为聚合的 PageRank 提供了一种分布式更新方案，并对其收敛特性进行了分析。该方法特别受到大规模马尔可夫链和多智能体共识的奇异扰动技术结果的启发。提供了一个数值示例来说明在保持排名误差较小的同时减少计算量的程度。
The PageRank algorithm employed at Google assigns a measure of importance to each web page for rankings in search results. In our recent papers, we have proposed a distributed randomized approach for this algorithm, where web pages are treated as agents computing their own PageRank by communicating with linked pages. This paper builds upon this approach to reduce the computation and communication loads for the algorithms. In particular, we develop a method to systematically aggregate the web pages into groups by exploiting the sparsity inherent in the web. For each group, an aggregated PageRank value is computed, which can then be distributed among the group members. We provide a distributed update scheme for the aggregated PageRank along with an analysis on its convergence properties. The method is especially motivated by results on singular perturbation techniques for large-scale Markov chains and multi-agent consensus. A numerical example is provided to illustrate the level of reduction in computation while keeping the error in rankings small.