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
A Web Aggregation Approach for Distributed Randomized PageRank Algorithms
Ishii, H., Tempo, R., & Bai, E. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2012.2190161 · Cited by 77
“Aggregation for PageRank computation has also been explored to obtain acceptable approximation in [37, 49] by classical methods in the Markov chain literature.”
Personalized PageRank Clustering: A graph clustering algorithm based on random walks
Tabrizi, S. A., Shakery, A., Asadpour, M., Abbasi, M., & Tavallaie, M. A. (2013) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2013.07.021 · Cited by 71
“[52–55]), PPC has the potential to be used distributedly which can make it an ideal solution for clustering at a scale that is infeasible with any single-machine implementation.”
BackgroundMultilevel Adaptive Aggregation for Markov Chains, with Application to Web Ranking
Sterck, H. D., Manteuffel, T. A., McCormick, S. F., et al. (2008) · SIAM Journal on Scientific Computing · doi:10.1137/070685142 · Cited by 57
“While the IAD method is normally employed as a two-level method, the use of multilevel versions has been proposed in the literature, and the link to algebraic multigrid methods has been pointed out before [18, 19, 20, 21].”
BackgroundMethodEfficient Parallel Computation of PageRank
Kohlschütter, C., Chirita, P., & Nejdl, W. (2006) · Lecture notes in computer science · doi:10.1007/11735106_22 · Cited by 55
“This coordinator is only responsible for arranging the iteration process at partition-level and does not know anything about the rank scores or the link structure (it is much simpler than the coordinator in [26]).”
BackgroundMethodEfficient Algorithms for Personalized PageRank Computation: A Survey
Yang, M., Wang, H., Wei, Z., Wang, S., & Wen, J.-R. (2024) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2024.3376000 · Cited by 89
“Another early work [113] uses divide-and-conquer to compute local PageRank vectors and then update them through communication with a coordinator.”
BackgroundEfficient PageRank and SpMV Computation on AMD GPUs
Wu, T., Wang, B., Shan, Y., et al. (2010) · Proceedings of the International Conference on Parallel Processing · doi:10.1109/icpp.2010.17 · Cited by 47
“For example, Zhu et al. [2] used iterative aggregation-disaggregation method to increase the convergence speed.”
MethodDistributed Algorithms on Exact Personalized PageRank
Guo, T., Cao, X., Cong, G., Lu, J., & Lin, X. (2017) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3035918.3035920 · Cited by 37
NCDawareRank: a novel ranking method that exploits the decomposable structure of the web
Νικολακόπουλος, Α. Ν., & Garofalakis, J. D. (2013) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/2433396.2433415 · Cited by 34
“[33] propose a distributed PageRank computation algorithm based on IAD methods.”
MethodComputing the PageRank Variation for Fragile Web Data
Ishii, H., & Tempo, R. (2009) · SICE Journal of Control Measurement and System Integration · doi:10.9746/jcmsi.2.1 · Cited by 30
“There has been a line of research in this direction including [4]–[7].”
BackgroundConvergence of Distributed Randomized PageRank Algorithms
Zhao, W., Chen, H.-F., & Fang, H. (2013) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2264553 · Cited by 27
“In this regards , several other approaches, such as the adaptive computation method [ 15], distributed randomized method [9][10][11][12][19], asyn chronous iteration method [14][16], etc.”
MethodpFusion: A P2P Architecture for Internet-Scale Content-Based Search and Retrieval
Zeinalipour-Yazti, D., Kalogeraki, V., & Gunopulos, D. (2007) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2007.1060 · Cited by 26
“If such an operation is too expensive, then somebodycanfocusonthe k highestrankedanswersforsome user-defined parameter k using well-established distributed top-k query processing algorithms [7].”
MethodDistributed PageRank Computation: An Improved Theoretical Study
Luo, S. (2019) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v33i01.33014496 · Cited by 28
“There have been a number of works on distributed PageR-ank algorithms (Guo et al. 2017; Sarma et al. 2015; Zhu, Ye, and Li 2005).”
BackgroundDistributed randomized PageRank computation based on web aggregation
Ishii, H., Tempo, R., Bai, E., & Dabbene, F. (2009) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2009.5399514 · Cited by 17
“In [18], Markov chain methods are applied to the problem by utilizing the block structures in the web.”
MethodDistributed PageRank computation with improved round complexities
Luo, S., Wu, X., & Kao, B. (2022) · Information Sciences · doi:10.1016/j.ins.2022.05.108 · Cited by 20
Fast PageRank approximation by adaptive sampling
Liu, W., Li, G., & Cheng, J. S.-C. (2013) · Knowledge and Information Systems · doi:10.1007/s10115-013-0691-1 · Cited by 19
“Decomposition techniques on the transition matrix are employed in iterative aggregationdisaggregation method [25].”
MethodBlack hole metric: Overcoming the pagerank normalization problem
Buzzanca, M., Carchiolo, V., Longheu, A., Malgeri, M., & Mangioni, G. (2018) · Information Sciences · doi:10.1016/j.ins.2018.01.033 · Cited by 16
“domains. For instance, [3] proposes a Monte Carlo technique to perform fast computation of random walk based algorithms such as PageRank. There also exists at least a version of distributed PageRank [48] which better handles the ever increasing number of web pages to rank: one of the main shortcoming of basic PageRank…”
MethodA distributed randomized approach for the PageRank computation: Part 1
Ishii, H., & Tempo, R. (2008) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2008.4739020 · Cited by 17
“For example, Monte Carlo methods are examined in [3], while the work in [29] exploits the block structure of the web to apply techniques from the Markov chain literature.”
MethodBoosting Item-based Collaborative Filtering via Nearly Uncoupled Random Walks
Νικολακόπουλος, Α. Ν., & Karypis, G. (2020) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3406241 · Cited by 17
“More recently, near decomposability has been recognized as a property of the Web [22] and it has inspired the development of algorithms for faster computation of PageRank [4, 62] (building on a large body of related research in the field of numerical linear algebra; see e.g.,[52, 53]) as well as the development of new…”
MethodInfluentialEdge-based local push for personalized PageRank
Wang, H., Wei, Z., Gan, J., Yuan, Y., Du, X., & Wen, J.-R. (2022) · Proceedings of the VLDB Endowment · doi:10.14778/3523210.3523216 · Cited by 19
“Except for SSPPR queries, there are other lines of researches concerning single-target PPR queries [8, 9, 40, 51], single-pair PPR queries [23, 38, 39, 41, 52], distributed PPR queries [27, 36, 42, 46, 69], or SSPPR computation on dynamic graphs [44, 65, 66].”
BackgroundKudělka, M., Zehnalová, Š., Horák, Z., Krömer, P., & Snåšel, V. (2015) · International Journal of Applied Mathematics and Computer Science · doi:10.1515/amcs-2015-0022 · Cited by 12
“286 M. Kudělka et al. The communication overhead which exists when executing the traditional power iteration method in a distributed way was also the focus of the work of Zhu et al. (2005).”
MethodCharalambous, T., Hadjicostis, C. N., Rabbat, M., & Johansson, M. (2016) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2016.7798241 · Cited by 11
A survey on distributed approaches to graph based reputation measures
Avrachenkov, K. E., Nemirovsky, D., & Pham, K. (2007) · Performance Evaluation Methodolgies and Tools · doi:10.5555/1345263.1345370 · Cited by 13
A survey on distributed approaches to graph based reputation measures
Avrachenkov, K. E., Nemirovsky, D., & Pham, K. S. (2007) · International ICST Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS) · doi:10.4108/smctools.2007.2027 · Cited by 11
Distributed PageRank Computation with Link Failures
Ishii, H., & Tempo, R. (2010) · Lecture notes in control and information sciences · doi:10.1007/978-3-540-93918-4_13 · Cited by 7
Query Independent Scholarly Article Ranking
Ma, S., Gong, C., Hu, R., Luo, D., Hu, C., & Huai, J. (2018) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2018.00090 · Cited by 12
“Second, we are to study distributed algorithms, similar to [43] that computes PageRank in a distributed environment.”
MethodPageRank: A modified random surfer model
Boo, V. K., & Anthony, P. (2011) · International Conference on Information Technology in Asia (CITA) · doi:10.1109/cita.2011.5998269 · Cited by 9
“For example, [6] proposed a theory to improve computation time for PageRank with iterative aggregation/disaggregation (IAD) method, while [ 7 ] proposed distributed PageRank computation (DPC) algorithm which is based on IAD method with Block Jacobi smoothing.”
MethodA distributed randomized approach for the PageRank computation: Part 2
Ishii, H., & Tempo, R. (2008) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2008.4739022 · Cited by 8
“For example, Monte Carlo methods are examined in [3], while the work in [29] exploits the block structure of the web to apply techniques from the Markov chain literature.”
MethodAnalysis of hyperlinks and the ant algorithm for calculating the ranks of Web pages
Alyguliev, R. M. (2007) · Automatic Control and Computer Sciences · doi:10.3103/s0146411607010075 · Cited by 8
“Another distributed algorithm for calculating PageRank which utilizes the method of Iterative Aggre-gation-Disaggregation (IAD) was proposed in [15].”
MethodDistributed PageRank computation with link failures
Ishii, H., & Tempo, R. (2009) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2009.5160351 · Cited by 8
“In [28], block structures in the web are exploited to apply Markov chain methods while the work of [1] utilizes techniques from Monte Carlo simulation.”
MethodVisual Analytics and Interactive Technologies: Data, Text and Web Mining Applications
Zhang, Q., Segall, R. S., & Cao, M. (2011) · IGI Global eBooks · doi:10.4018/978-1-60960-102-7 · Cited by 27
A Survey and Comparative Study of Different PageRank Algorithms
Jilani, T. A., Fatima, U., Baig, M. M., et al. (2015) · International Journal of Computer Applications · doi:10.5120/21410-4444 · Cited by 6
“Aggregation or Disaggregation Iterative Approach Aggregation or Disaggregation iterative method is used to expeditiously compute PageRank vector than the Power Method as studied by Zhu, Yu and Li [10].”
MethodArchitecture and performance of runtime environments for data intensive scalable computing
Fox, G., & Ekanayake, J. (2010) · Cited by 8
Distributed randomized pagerank algorithms based on web aggregation over unreliable channels
Ishii, H., Tempo, R., & Bai, E. (2010) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2010.5718041 · Cited by 4
“The first stems from computational aspects; see also [1], [12], [20] for studies in this direction.”
BackgroundFast Flow-based Random Walk with Restart in a Multi-query Setting
Yan, Y., Heimann, M., Jin, D., & Koutra, D. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975321.39 · Cited by 4
“Other iterative methods belong to domain decomposition methods, such as Block Jacobi [22] and Additive Schwarz [16], and GraphLab [15].”
MethodUsing Graphics Processors for High Performance SimRank Computation
He, G., Li, C., Chen, H., Du, X., & Feng, H. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2011.91 · Cited by 4
“, distributed PageRank computing [11], PageRank updating [36], [9], etc.”
MethodA Distributed Framework for Organizing an Internet of Things
Walters, J., Kanter, T., & Savioli, E. (2012) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-642-29479-2_18 · Cited by 3
“This concept of ranking has been explored and used both in a centralized [17] as well as distributed [18] solutions.”
BackgroundEvolving Presentity-Based Context Schemas by Estimating Context Proximity
Walters, J., & Kanter, T. (2012) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-642-32304-1_13 · Cited by 2
“Centralized solutions such as Google index a tiny portion, less than 10 billion of the estimated 550 billion pages, on the relatively static Internet [16] [22].”
BackgroundAggregation-iterative analogues and generalizations of projection-iterative methods
Shuvar, B. A., Obshta, A., & Kopach, M. I. (2013) · Carpathian Mathematical Publications · doi:10.15330/cmp.5.1.156-163 · Cited by 2
Fragile link structure in PageRank computation
Ishii, H., & Tempo, R. (2009) · doi:10.1109/cdc.2009.5399501 · Cited by 2
“Hence, there has been a line of research to develop more efficient computational methods including [3], [5], [11], [17].”
PageRank Computation via Web Aggregation in Distributed Randomized Algorithms
Suzuki, A., & Ishii, H. (2019) · Proceedings of the IEEE Conference on Decision & Control, including the Symposium on Adaptive Processes · doi:10.1109/cdc40024.2019.9029680 · Cited by 2
“Aggregation-based computation of PageRank has been studied, for example, in [14], [22] using classical methods in Markov chains and in [3] via extensive simulations.”
MethodDecentralized Network Analysis: A Proposal
Montresor, A. (2008) · IEEE Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE) · doi:10.1109/wetice.2008.36 · Cited by 2
“The lion’s share of such literature is given by PageRank implementations [9], with even a large number of distributed versions [7, 14, 13].”
BackgroundConvergence of Distributed Randomized PageRank AlgorithmsPreprint
Zhao, W., Chen, H.-F., & Fang, H. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.3178 · Cited by 2
“In this regards , several other approaches, such as the adaptive computation method [ 15], distributed randomized method [9][10][11][12][19], asyn chronous iteration method [14][16], etc.”
MethodBockting, S. (2009) · Cited by 2
Parameter Estimation in a Stochastic System Model for PageRank
Clifton, C. E., & Pasik-Duncan, B. (2015) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611974072.59 · Cited by 2
“Important contributions have focused on improving the quality of rankings via topic-dependent or “personalized” PageRank [6], [13], as well improving the efficiency of PageRank computation using Monte Carlo methods [2], [23], extrapolation and adaptive methods [15], [16], and aggregation methods [5], [8], [11], [17],…”
MethodTowards the Notion of Typical Documents in Large Collections of Documents
Kłopotek, M. A., Wierzchoń, S. T., Ciesielski, K., Dramiński, M., & Czerski, D. (2011) · IGI Global eBooks · doi:10.4018/978-1-60960-102-7.ch001 · Cited by 2
Unconventional analogs of single-parametric method of iterational aggregation
Демків, І. І., Kopach, M. I., Obshta, A., et al. (2018) · Carpathian Mathematical Publications · doi:10.15330/cmp.10.2.296-302 · Cited by 1
(2011) · SpringerReference · doi:10.1007/springerreference_60484 · Cited by 1
Distributed Randomized Algorithms for the PageRank ComputationPreprint
Ishii, H., & Tempo, R. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1203.6599 · Cited by 1
Efficient PageRank Computation via Distributed Algorithms with Web ClusteringPreprint
Suzuki, A., & Ishii, H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.09979 · Cited by 1
“Such studies can be found, for example, in [21], [37] using classical methods in Markov chains and in [5] via extensive simulations.”
MethodClassement de services et de données par leur utilisation
Constantin, C. (2007) · OpenGrey (Institut de l'Information Scientifique et Technique)
Probabilistic Multiagent Reasoning over Annotated Amalgamated F-Logic Ontologies
Schatten, M. (2013) · ISRN Artificial Intelligence · doi:10.1155/2013/691707
“A solution to the first problemmight be to calculate ranks in a distributed manner, as has been shown in [10].”
BackgroundDEWS: A decentralized engine for Web search
Ahmed, R., Bari, M. F., Haque, R., et al. (2014) · doi:10.1109/cnsm.2014.7014168
“Distributed PageRank computation based on Iterative aggregation-disaggregation method is proposed in [23].”
MethodGADBMS: A Framework for Scalable Array Analytics
Clemons, T., Parthasarathy, S., & Sadayappan, P. (2012) · doi:10.1109/sc.companion.2012.165
LARGE-SCALE NETWORK ANALYSIS ON DISTRIBUTED ARCHITECTURES
Paolino, C. (2010) · AMS Degree Thesis (University of Bologna)
A Stochastic System Model for PageRank: Parameter Estimation and Adaptive Control
Clifton, C. E. (2015) · KU ScholarWorks (University of Kansas)
Iterative Computing over a Unified Relationship Matrix for Information Integration
Xi, W. (2006) · VTechWorks (Virginia Tech)
Investigation of Convergence of Iterative Aggregation Methods for Linear Equations in a Banach Space
Kopach, M. I., Obshta, A., & Shuvar, B. A. (2015) · Journal of Vasyl Stefanyk Precarpathian National University · doi:10.15330/jpnu.2.4.50-57
Steady-state analysis of Google-like stochastic matrices
Noyan, G. N. (2007) · Bilkent University Institutional Repository (Bilkent University)
A PageRank Inspired Approach to Measure Network Cohesiveness
Carchiolo, V., Grassia, M., Longheu, A., Malgeri, M., & Mangioni, G. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-34914-1_33
Web-site-based partitioning techniques for efficient parallelization of the PageRank computation
Cevahir, A. (2006) · Bilkent University Institutional Repository (Bilkent University)
Two Parallel PageRank Algorithms via Improving Forward PushPreprint
Zhang, Q., Tang, R., Yao, Z., et al. (2023) · Research Square · doi:10.21203/rs.3.rs-2624542/v1
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.