CoChat

Distributed PageRank computation based on iterative aggregation-disaggregation methods

Zhu, Yangbo, Ye, Shaozhi, Li, Xing · 2005 · Proceedings of the 14th ACM international conference on Information and knowledge management

The DOI matches its Crossref record; 30 of the 33 references it cites were found in a registry or an index; none of the 3 sources its claims cite is checked for support yet.

Abstract

PageRank has been widely used as a major factor in search engine ranking systems. However, global link graph information is required when computing PageRank, which causes prohibitive communication cost to achieve accurate results in distributed solution. In this paper, we propose a distributed PageRank computation algorithm based on iterative aggregation-disaggregation (IAD) method with Block Jacobi smoothing. The basic idea is divide-and-conquer. We treat each web site as a node to explore the block structure of hyperlinks. Local PageRank is computed by each node itself and then updated with a low communication cost with a coordinator. We prove the global convergence of the Block Jacobi method and then analyze the communication overhead and major advantages of our algorithm. Experiments on three real web graphs show that our method converges 5--7 times faster than the traditional Power method. We believe our work provides an e#cient and practical distributed solution for PageRank on large scale Web graphs.

Overview

CoChat Summary

TL;DR

The paper proposes a distributed PageRank computation algorithm based on iterative aggregation-disaggregation with Block Jacobi smoothing, grouping pages by web site and using a coordinator for global updates. Experiments on three real web graphs show 5–7× faster convergence than the Power method and better one-iteration accuracy than LPR-Ref-2.

Key findings

  • DPC converges 5–7 times faster than the traditional Power method: at ε = 10⁻⁵, iterations were ST01 54 vs 11, ST03 42 vs 7, and CN04 34 vs 5.
  • After one iteration, DPC had lower L1 distance to the true PageRank than Power method and LPR-Ref-2: ST01 0.023 vs 0.539/0.207, ST03 0.124 vs 0.523/0.477, CN04 0.014 vs 0.140/0.146.
  • Kendall’s τ-distance after one iteration was also lower for DPC: ST01 0.071 vs 0.190/0.142, ST03 0.010 vs 0.155/0.070, CN04 0.013 vs 0.093/0.087.
  • Communication overhead is O(Pos((L̄ + Ū)S(π))) + O(N), roughly equivalent to LPR-Ref-2; the paper reports Pos((L̄ + Ū)S(π)) reductions to 8M (20.0%) for ST01, 165M (34.1%) for ST03, and 35M (23.3%) for CN04.

Methods

  • Design: divide-and-conquer distributed PageRank; each web site computes local PageRank, a coordinator solves the aggregated coarse-level system, and nodes perform local smoothing via extended local transition matrices; the algorithm is proven equivalent to an IAD method with Block Jacobi smoothing.
  • Data: three real web graphs — ST01 (65M URLs, 607M links, 542K sites, average out-degree 9.28, inter-node links 6.53%), ST03 (49M URLs, 1185M links, 25K sites, average out-degree 24.05, inter-node links 40.85%), and CN04 (88M URLs, 485M links, 697K sites, average out-degree 5.53, inter-node links 30.99%).
  • Evaluation: L1 distance and Kendall’s τ-distance, with Kendall’s τ estimated by Monte Carlo using 10¹⁰ random pairs because exact computation is O(N²); compared against Power method and LPR-Ref-2, with simulation carried out on one machine.

Limitations

  • Stated: the paper notes that global convergence of IAD remains an open problem and proves convergence only for the Block Jacobi method in the PageRank scenario; future work asks how to update PageRank vectors efficiently and whether asynchronous iterations are possible since ρ(T) = 1.
  • Evident: experiments are a simulation on one machine, not an actual distributed deployment, so real network and communication costs are not measured.
  • Evident: LPR-Ref-2 can be run only once, so its convergence rate cannot be evaluated; Kendall’s τ-distance is approximated by Monte Carlo rather than computed exactly.

Model-written summary of a shortened version of the paper’s full text (it is longer than we read). Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1145/1099554.1099705

Cites

30 of 30 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 0 Not valid · 3 Not checked · 10 Own results and interpretations

4 more claims

Create a free account to see all 13 claims and every source verdict.

See all claims — free account
  • It may state two separate claims as one. 4
  • Probably not a substantial claim. 1

Create a free account to see these claims.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

1 of 1

Citations

Cites

Research works printed but not linked: 5

  1. F. Chatelin . Iterative aggregation/disaggregation methods. In Proc. of Int. Workshop on Mathematical Computer Performance and Reliability , 1983 . F. Chatelin. Iterative aggregation/disaggregation methods. In Proc. of Int. Workshop on Mathematical Computer Performance and Reliability, 1983.
  2. H. Kafeety , C. Meyer , and W. Stewart . A general framework for iterative aggregation/ disaggregation methods . In Proc. of the 4th Copper Mountain Conf. on Iterative Methods , 1992 . H. Kafeety, C. Meyer, and W. Stewart. A general framework for iterative aggregation/ disaggregation methods. In Proc. of the 4th Copper Mountain Conf. on Iterative Methods, 1992.
  3. C. Lee , G. Golub , and S. Zenios . A fast two-stage algorithm for computing pagerank and its extensions. Technical report , Stanford Univ. , 2003 . C. Lee, G. Golub, and S. Zenios. A fast two-stage algorithm for computing pagerank and its extensions. Technical report, Stanford Univ., 2003.
  4. P. Lyman , H. Varian , J. Dunn , A. Strygin , and K. Swearingen . How much information project. Technical report , Univ. of California , Berkeley , 2003 . P. Lyman, H. Varian, J. Dunn, A. Strygin, and K. Swearingen. How much information project. Technical report, Univ. of California, Berkeley, 2003.
  5. 10.5555/645740.666754 · doi:10.5555/645740.666754

Cited by

See all 66

Metadata

Authors
Zhu, Y., Ye, S., & Li, X.
Affiliations
  • Tsinghua University (CN)
  • University of California, Davis (US)
Venue
Proceedings of the 14th ACM international conference on Information and knowledge management
Publisher
ACM
Published
2005-10-31
Pages
578-585
ISSN
2155-0751 (ISSN-L)
OpenAlex
W2098593316
Cited by
65
References
33
Citations by year
2024: 1 · 2023: 2 · 2022: 2 · 2020: 1 · 2019: 5 · 2018: 4 · 2017: 1 · 2016: 1 · 2015: 5 · 2014: 1 · 2013: 6 · 2012: 6
FWCI
3.67
Type
conference paper
Language
en
Open access
closed
Locations
ACM International Conference on Information and Knowledge Management (CIKM) (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
Keywords
PageRank, distributed computing, web graph, divide-and-conquer, communication overhead, convergence analysis, power method

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-10-07, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-07 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.