Distributed PageRank computation based on iterative aggregation-disaggregation methods
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
Cites
Statistics
Verification
Claims the paper makes
0 Valid · 0 Not valid · 3 Not checked · 10 Own results and interpretations
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“ST01 0.190 0.142 0.071 ST03 0.155 0.070 0.010 CN04 0.093 0.087 0.013”
§ 0 otherwise > 4.3 Accuracy of a Single Iteration
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The amount of communication traffic is proportional to Pos((L̄ + Ū)S(π)), which is much smaller than Pos(L̄ + Ū). Table 1 shows the comparison in real web graphs.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“In DPC algorithm, the local PageRank vectors for many nodes converge quickly.”
plain- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Experiments on three real web graphs show that our method converges 5–7 times faster than the traditional Power method.”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
A result the paper reports from its own data — it cites no other source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“ST01 0.539 0.207 0.023 ST03 0.523 0.477 0.124 CN04 0.140 0.146 0.014”
§ 0 otherwise > 4.3 Accuracy of a Single Iteration
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: passes — The paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
4 more claims
Create a free account to see all 13 claims and every source verdict.
- It may state two separate claims as one. 4
- Probably not a substantial claim. 1
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.
Rated minor: it would not touch a result — a value no result rests on, a p-value that stays on the same side of the significance level, or a conflict that is clerical, resolved elsewhere in the paper, or outside its own findings.
In the paper
§ 0 otherwise
“In Step 2, node Gi sends the coordinator a vector P̄∗iπi, which is equal to the ith column of P̄S(π).”
§ 0 0 . . . S(π)n
“where S(π)i = (πi/‖(πi‖1) is a column vector denoting the censored stationary distribution of pages in node Gi.”
Citations
Cites
(1999) · Cited by 12,854
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Kendall, M. G. (1957) · Biometrika · doi:10.2307/2333282 · Cited by 6,383
Golub, G. H., & Loan, C. F. V. (1996) · Johns Hopkins University Press eBooks · Cited by 6,027
Moran, P. A. P., & Kendall, M. G. (1951) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2980903 · Cited by 2,573
The webgraph framework I: compression techniques
Boldi, P., & Vigna, S. (2004) · Proceedings of the 13th international conference on World Wide Web · doi:10.1145/988672.988752 · Cited by 1,201
Govindarajulu, Z., Kendall, M., & Gibbons, J. D. (1992) · Technometrics · doi:10.2307/1269571 · Cited by 1,130
Langville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
Extrapolation methods for accelerating PageRank computations
Kamvar, S. D., Haveliwala, T. H., Manning, C. D., & Golub, G. H. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775190 · Cited by 407
Stochastic Complementation, Uncoupling Markov Chains, and the Theory of Nearly Reducible Systems
Meyer, C. D. (1989) · SIAM Review · doi:10.1137/1031050 · Cited by 316
Research works printed but not linked: 5
- 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.
- 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.
- 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.
- 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.
- 10.5555/645740.666754 · doi:10.5555/645740.666754
Cited by
Twister: a runtime for iterative MapReduce
Ekanayake, J., Li, H., Zhang, B., Gunarathne, T., Bae, S.-H., Qiu, J., & Fox, G. (2010) · Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing · doi:10.1145/1851476.1851593 · Cited by 777
“There already exist many published work optimizing PageRank algorithm, like some of them accelerate computation by exploring the block structure of hyperlinks[31, 32].”
MethodDistributed Randomized Algorithms for the PageRank Computation
Ishii, H., & Tempo, R. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2042984 · Cited by 145
Parallel SimRank computation on large graphs with iterative aggregation
He, G., Feng, H., Li, C., & Chen, H. (2010) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1835804.1835874 · Cited by 124
“Since [31] brought forward the concept of nearly completely reducible (NCR) Markov chain, the iterative aggregation method has been widely exploited to applications based on NCR Markov chains, e.g. distributed PageRank computing [41], PageRank updating [20], [21], etc. GPU Applications.”
MethodRecWalk: Nearly Uncoupled Random Walks for Top-N Recommendation
Νικολακόπουλος, Α. Ν., & Karypis, G. (2019) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3289600.3291016 · Cited by 90
“More recently near decomposability has been recognized as a property of the Web [19] and it has inspired the development of algorithms for faster computation of PageRank [6, 47] (building on a large body of related research in the field of numerical linear algebra; see e.”
MethodA web aggregation approach for distributed randomized PageRank algorithmsPreprint
Ishii, H., Tempo, R., & Bai, E. (2012) · Cited by 77
Metadata
- Authors
- Zhu, Y., Ye, S., & Li, X.
- Affiliations
- Tsinghua University (CN)
- University of California, Davis (US)
- ORCID
- Li, Xing
- 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.