Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index; none of the 12 sources its claims cite is checked for support yet.
Abstract
PageRank is one of the principle criteria according to which Google ranks Web pages. PageRank can be interpreted as a frequency of visiting a Web page by a random surfer, and thus it reflects the popularity of a Web page. Google computes the PageRank using the power iteration method, which requires about one week of intensive computations. In the present work we propose and analyze Monte Carlo‐type methods for the PageRank computation. There are several advantages of the probabilistic Monte Carlo methods over the deterministic power iteration method: Monte Carlo methods already provide good estimation of the PageRank for relatively important pages after one iteration; Monte Carlo methods have natural parallel implementation; and finally, Monte Carlo methods allow one to perform continuous update of the PageRank as the structure of the Web changes.
Overview
CoChat Summary
TL;DR
The paper proposes and analyzes Monte Carlo methods for PageRank computation, including a complete-path algorithm that records all visited pages and stops at dangling nodes. It shows theoretically and experimentally that important pages can be estimated accurately after one iteration, with cyclic-start Monte Carlo outperforming random-start Monte Carlo and complete-path stopping at dangling nodes performing best on their dataset.
Key findings
- MC complete path stopping at dangling nodes gives small error for important pages already after the first iteration; on the INRIA dataset it outperforms power iteration even for the first 1000 most important pages. One iteration gave a relative error of only 7% with 95% confidence for pages with high PageRank, and if important pages have PageRank 10^4 times larger than the minimal PageRank value, the method achieves about 1% error for important pages after the first iteration.
- MC algorithms with cyclic start outperform MC algorithms with random start. On the dataset, MC complete path stopping at dangling nodes performs best, followed by MC complete path with random start; MC end-point with cyclic start has the worst performance.
- The number of required samples is linear in n, and a reasonable evaluation for popular pages can be obtained even with N = n, i.e., one run per page; this is much less pessimistic than the earlier rough O(n^2) estimate. The estimator is consistent, and the additional relative error from estimating γ is of order 1/√(mn) and can essentially be neglected.
- The PageRank vector on the dataset follows a power law closely.
Methods
- Design: theoretical analysis of Monte Carlo PageRank algorithms based on the absorbing Markov chain interpretation, with convergence and confidence-interval comparisons; algorithms include MC end-point with random start, MC end-point with cyclic start, MC complete path, MC complete path stopping at dangling nodes, and MC complete path with random start.
- Data: the Web site of INRIA Sophia Antipolis, about 50000 Web pages and 200000 hyperlinks; data collected with a custom Web crawler using an Oracle database, and power iteration plus three MC algorithms implemented in PL/SQL.
- Main analysis: computed PageRank with 20 digits accuracy via sufficient power iterations, sorted the PageRank vector, chose four elements, performed 10 iterations of the PI method and 10 iterations of the three implemented MC algorithms, and compared actual relative error and 95% confidence intervals.
Limitations
- The paper states that if first-iteration results are unsatisfactory, increasing m is hard to improve: after m iterations the MC relative error reduces on average only by the factor 1/√m, whereas the power iteration error decreases exponentially with m; MC can still be advantageous because of simplicity in parallel implementation.
- The paper states that the choice between end-point and complete-path versions depends on the total PageRank of dangling nodes and the probability of a cycle returning to j; many short cycles add high extra variability, and high dangling-node rank can stop walks early, potentially making the difference negligible. On a modified graph including intra-page hyperlinks, the MC methods showed very slow convergence.
- Evident from the text: experiments use one Web site (about 50000 pages and 200000 hyperlinks), not the full Web, and the variance derivation assumes that all W_ij’s are independent.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Figures
Verification
Claims the paper makes
0 Valid · 4 Not valid · 9 Not checked · 31 Own results and interpretations
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Monte Carlo methods provide good estimation of the PageRank for relatively important pages already after one iteration”
- Also stated in: § Proof. See the Appendix. · boosted
“Strikingly, it follows from (18) that the Monte Carlo method gives good results for important pages in one iteration only, that is, when m = 1.”
- Also stated in: § 5 Conclusions · boosted
“Our theoretical and experimental results have demonstrated that the Monte Carlo algorithms determine the PageRank of relatively important pages already after the first iteration.”
boostedstates 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.
- Also stated in: § Proof. See the Appendix. · boosted
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“One can show however that Algorithm 4 provides an estimator with a smaller variance than Algorithm 5.”
- Also stated in: § 2 Monte Carlo algorithms · plain
“Hence, Algorithm 4 provides random variables with smaller variance in both numerator and denominator of (11).”
plainstates a cause- Asserted: passes — The authors put it forward as true.
- Checkable: passes — It can be checked against evidence.
- Load-bearing: unclear — It is unclear whether the paper’s conclusions depend on it.
- Based: passes — The paper gives a reason why it holds.
- Also stated in: § 2 Monte Carlo algorithms · plain
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Thus, ¯ W equals the number of dangling nodes n 0 plus the sum of n -n 0 independent random variables ˆ W i · , i ∈ I 1 .”
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.
- Rests on an assumption not shown here.
A result the paper states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“Second, Theorem 1 states that the error in the estimate of π j originates mainly from estimating w · j .”
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 states — it cites no source for it, so there is none to check. The quote shows it is in the paper.
In the paper
“The factor C ( β ) can be approximated as”
- Also stated in: § 3 Convergence Analysis · plain
“where x 1 -β/ 2 is a (1 -β/ 2) -quantile of the standard normal distribution and n 0 is the number of dangling nodes.”
plainstates an association- 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.
- Also stated in: § 3 Convergence Analysis · plain
21 more claims
Create a free account to see all 44 claims and every source verdict.
- Probably not a substantial claim. 11
- The quote only partly states this claim. 2
- It may state two separate claims as one. 7
Citations
Cites
(1999) · Cited by 12,854
Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., & Wiener, J. (2000) · Computer Networks · doi:10.1016/s1389-1286(00)00083-9 · Cited by 2,810 · cited 1×
“According to [6, 14], the ratio between the number of links and number of pages of the Web is between 7.”
BackgroundScaling personalized web search
Jeh, G., & Widom, J. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775191 · Cited by 1,195 · cited 2×
“The end-point of a random walk that starts from a random page and can be terminated at each step with probability 1 − c, appears to be a sample from the distribution π [4, 7, 9].”
BackgroundThe Web as a Graph: Measurements, Models, and Methods
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. S. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48686-0_1 · Cited by 1,016
Langville, A., & Meyer, C. (2004) · Internet Mathematics · doi:10.1080/15427951.2004.10129091 · Cited by 894
Bianchini, M., Gori, M., & Scarselli, F. (2005) · ACM Transactions on Internet Technology · doi:10.1145/1052934.1052938 · Cited by 539 · cited 2×
“For instance, in [2], the PageRank is seen as the average number of surfers navigating a given page at a given time instant provided that at each time instant t ≥ 0, a surfer can cease from navigating with probability (1 − c) and on average (1 − c) surfers start navigating from each page.”
BackgroundExtrapolation 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
Challenges in web search engines
Henzinger, M. R., Motwani, R., & Silverstein, C. (2002) · ACM SIGIR Forum · doi:10.1145/792550.792553 · Cited by 307
Adaptive methods for the computation of PageRank
Kamvar, S., Haveliwala, T., & Golub, G. (2004) · Linear Algebra and its Applications · doi:10.1016/j.laa.2003.12.008 · Cited by 271
Adaptive on-line page importance computation
Abiteboul, S., Preda, M., & Cobena, G. (2003) · Proceedings of the twelfth international conference on World Wide Web - WWW '03 · doi:10.1145/775152.775192 · Cited by 213
Cited by
Fast incremental and personalized PageRank
Bahmani, B., Chowdhury, A., & Goel, A. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1929861.1929864 · Cited by 327
“Our algorithm is a Monte Carlo method [2] that works by maintaining a small number of short random walk segments starting at each node in the social graph.”
BackgroundMethodInfluentialk-nearest neighbors in uncertain graphs
Potamias, M., Bonchi, F., Gionis, A., & Kollios, G. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920967 · Cited by 235
Heat kernel based community detection
Kloster, K., & Gleich, D. F. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623706 · Cited by 205
“[13] to achieve a randomized sublinear time algorithm to estimate the largest PageRank entries, and in fact, Monto Carlo methods frequently feature in PageRank computations due to the relationship between the diffusion and a random walk [7, 13, 8, 9].”
MethodScalable Graph Embedding for Asymmetric Proximity
Zhou, C., Liu, Y., Liu, X., Liu, Z., & Gao, J. (2017) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v31i1.10878 · Cited by 190
“Due to the complexity of the iteration-style computation, Monte Carlo approach is usually adopted when calculating Rooted PageRank values (Gupta et al. 2013; Fogaras et al. 2005; Bahmani, Chowdhury, and Goel 2010; Avrachenkov et al. 2007).”
MethodAn Introduction to Search Engines and Web Navigation
Levene, M. (2010) · Wiley eBooks · doi:10.1002/9780470874233 · Cited by 197
Fast personalized PageRank on MapReduce
Bahmani, B., Chakrabarti, K., & Xin, D. (2011) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1989323.1989425 · Cited by 157
“Based on this idea, Fogaras et al [10] and later Avrachenkov et al [2] proposed the following method for PPR approximation: Starting at each node u .”
MethodInfluentialDistributed 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
“That is, each page exchanges its value with the pages that it is linked to and those linked to it.”
BackgroundPersonalized PageRank Estimation and Search: A Bidirectional Approach
Lofgren, P., Banerjee, S., & Goel, A. (2016) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/2835776.2835823 · Cited by 171
“They are efficient for certain ranges of |T |, but our experiments show they are too slow for realtime search across most values of |T |: • Monte-Carlo [2, 9]: Sample random walks from s, and filter out any walk whose endpoint is not in T .”
BackgroundMethodInfluentialFast Distributed PageRank Computation
Sarma, A. D., Molla, A. R., Pandurangan, G., & Upfal, E. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-35668-1_2 · Cited by 114
FAST-PPR: scaling personalized pagerank estimation for large graphs
Lofgren, P., Banerjee, S., Goel, A., & Seshadhri, C. (2014) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2623745 · Cited by 136
“Monte-Carlo refers to the standard random-walk algorithm [13, 15, 16, 17] – we perform cMC δ walks and estimate πu(v) by the fraction of walks terminating at v.”
MethodLastra-Díaz, J. J., Goikoetxea, J., Taieb, M. A. H., García-Serrano, A. M., Aouicha, M. B., & Agirre, E. (2019) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2019.07.010 · Cited by 105
PRINCE: Provider-side Interpretability with Counterfactual Explanations in Recommender Systems
Ghazimatin, A., Balalau, O., Saha Roy, R., & Weikum, G. (2020) · Proceedings of the 13th International Conference on Web Search and Data Mining · doi:10.1145/3336191.3371824 · Cited by 88
“Approximate algorithms include power iteration [38], local push [2, 3, 56] and Monte Carlo methods [4, 5].”
MethodApproximate Personalized PageRank on Dynamic Graphs
Zhang, H. R., Lofgren, P., & Goel, A. (2016) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2939672.2939804 · Cited by 103
A web aggregation approach for distributed randomized PageRank algorithmsPreprint
Ishii, H., Tempo, R., & Bai, E. (2012) · Cited by 77
Bahmani, B., Kumar, R., Mahdian, M., & Upfal, E. (2012) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2339530.2339539 · Cited by 78
HubPPR: effective indexing for approximate personalized pagerank
Wang, S., Tang, Y., Xiao, X., Yang, Y., & Li, Z. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3021924.3021936 · Cited by 90
“For the PPR query, we compare HubPPR against BiPPR [20], FastPPR [21], and a baseline Monte-Carlo approach [3].”
MethodAn Uncertainty-Aware Approach for Exploratory Microblog Retrieval
Liu, M., Liu, S., Zhu, X., Liao, Q., Wei, F., & Pan, S. (2016) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2015.2467554 · Cited by 68
“The advantages of this sampling method over the matrix-based method are as follows [2]: • Ranking scores are locally updated when the input changes locally; • The ranking scores of important items are accurately estimated after a few iterations; • The uncertainty of the ranking scores are modeled accurately because th…”
MethodA 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
“The work of [5] employs techniques based on Monte Carlo simulation.”
Fast distributed PageRank computation
Sarma, A. D., Molla, A. R., Pandurangan, G., & Upfal, E. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.04.003 · Cited by 67
“Keywords: PageRank, Distributed Algorithm, Random Walk, Monte Carlo Method ∗Appeared in Theoretical Computer Science (TCS), volume 561, pages 113 -121, 2015 [10].”
BackgroundMethodInfluentialRandom Walks and Neural Network Language Models on Knowledge Bases
Goikoetxea, J., Soroa, A., & Agirre, E. (2015) · Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) · doi:10.3115/v1/n15-1165 · Cited by 71
“The algorithm used for creating the contexts is a Monte Carlo method for computing the PageRank algorithm (Avrachenkov et al., 2007).”
MethodShenTu: Processing Multi-Trillion Edge Graphs on Millions of Cores in Seconds
Lin, H., Zhu, X., Yu, B., Tang, X., Xue, W., Chen, W., Zhang, L., Hoefler, T., Ma, X., Liu, X., et al. (2018) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc.2018.00059 · Cited by 78
“Thus, researchers and industry usually resort to simplified graphs or other approximation methods [54].”
Parallel personalized pagerank on dynamic graphs
Guo, W., Li, Y., Sha, M., & Tan, K. (2017) · Proceedings of the VLDB Endowment · doi:10.14778/3151113.3151121 · Cited by 65
A Survey on Personalized PageRank Computation Algorithms
Park, S., Lee, W., Choe, B., & Lee, S. (2019) · IEEE Access · doi:10.1109/access.2019.2952653 · Cited by 63
“There are two Monte-Carlo methods for the Personalized PageRank problem: the MC end-point and the MC complete path [22].”
MethodQuick Detection of Top-k Personalized PageRank Lists
Avrachenkov, K. E., Litvak, N., Nemirovsky, D., Smirnova, E., & Sokol, M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-21286-4_5 · Cited by 62
“Next, we exploit the fact that the element (s, j) of the matrix [I − cP ] equals to the expected number of visits to node j by the random walk initiated at state s with the run time geometrically distributed with parameter c [2].”
BackgroundMethodInfluentialSelf-citationAn Arnoldi-Extrapolation algorithm for computing PageRank
Wu, G., & Wei, Y. (2010) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2010.02.009 · Cited by 50
Rozenshtein, P., & Gionis, A. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46227-1_42 · Cited by 50
“Methodologically, the closest papers to our work, are Monte-Carlo simulation algorithms [2] and PageRank calculation by local updates [1, 7].”
BackgroundEfficient 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
“It can be verified that the three definitions of PPR above are essentially equivalent [30].”
BackgroundMethodInfluentialA survey on network node ranking algorithms: Representative methods, extensions, and applications
Liu, J., Li, X., & Dong, J. (2020) · Science China Technological Sciences · doi:10.1007/s11431-020-1683-2 · Cited by 49
“An overview article about personalized PageRank [37] summarizes five PPR calculation methods in recent years: direct equation solving [38], iterative equation solving [39], bookmark coloring [40], dynamic programming [41] and Monte-Carlo sampling [42].”
MethodA Singular Perturbation Approach for Choosing the PageRank Damping Factor
Avrachenkov, K. E., Litvak, N., & Pham, K. S. (2008) · Internet Mathematics · doi:10.1080/15427951.2008.10129300 · Cited by 52
Self-citationSocially-aware caching strategy for content centric networking
Bernardini, C., Silverston, T., & Festor, O. (2014) · IFIP Networking Conference (IFIP Networking) · doi:10.1109/ifipnetworking.2014.6857093 · Cited by 47
“[35], [36] also shows that it is feasible to compute a good estimation of the PageRank without the entire knowledge of the network.”
BackgroundOnline estimating the k central nodes of a network
Lim, Y.-S., Menasché, D. S., Ribeiro, B., Towsley, D., & Basu, P. (2011) · IEEE Network Science Workshop (NSW) · doi:10.1109/nsw.2011.6004633 · Cited by 43
“In addition, while [17] and [18] focus on the web graph, in this paper we consider a more diverse set of topologies.”
BackgroundPowerWalk: Scalable Personalized PageRank via Random Walks with Vertex-Centric Decomposition
Liu, Q., Li, Z., Lui, J. C. S., & Cheng, J. (2016) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2983323.2983713 · Cited by 42
“[3] proposed a Monte-Carlo complete path algorithm for computing the global PageRank which also utilizes the full trajectory of each random walk.”
MethodInfluentialA Sublinear Time Algorithm for PageRank Computations
Borgs, C., Brautbar, M., Chayes, J., & Teng, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-30541-2_4 · Cited by 43
“Next, a linear time Monte Carlo based method to estimate PageRank of all nodes is devised in [3].”
MethodA Monte Carlo algorithm for cold start recommendation
Rong, Y., Xiao, W., & Cheng, H. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2566486.2567978 · Cited by 39
“According to [3]:”
MethodResultInfluentialOn the embeddability of random walk distances
Zhao, X., Chang, A., Sarma, A. D., Zheng, H.-T., & Zhao, B. Y. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2556549.2556554 · Cited by 42
“linear algebraic optimization [19, 29] and Monte Carlo approximation algorithms [13, 3].”
MethodFighting Opinion Control in Social Networks via Link Recommendation
Amelkin, V., & Singh, A. K. (2019) · ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD) · doi:10.1145/3292500.3330960 · Cited by 35
“[4], who show that PageRank of high-centrality nodes estimated via Monte Carlo simulation converge very fast.”
BackgroundBiloshchytskyi, A. O., Kuchansky, A., Andrashko, Y., Biloshchytska, S., Kuzka, O., & Terentyev, О. (2017) · Eastern-European Journal of Enterprise Technologies · doi:10.15587/1729-4061.2017.103651 · Cited by 44
“Paper [16] described applying the Monte Carlo method to speed up”
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].”
BackgroundMultiscale Matrix Sampling and Sublinear-Time PageRank Computation
Borgs, C., Brautbar, M., Chayes, J., & Teng, S. (2013) · Internet Mathematics · doi:10.1080/15427951.2013.802752 · Cited by 42
“The PageRank estimation method of [3] conducts simulation of a constant number of random walks from each of the nodes in the network and therefore it requires linear time in the size of the network.”
MethodOn the Distributed Complexity of Large-Scale Graph Computations
Pandurangan, G., Robinson, P., & Scquizzato, M. (2018) · ACM Transactions on Parallel Computing · doi:10.1145/3210377.3210409 · Cited by 31
“In the Monte Carlo method, the basic idea is to approximate PageRank by directly simulating the corresponding random walk and then estimating the stationary distribution with the performed walk’s distribution [20, 4].”
BackgroundMethodFrogWild! fast PageRank approximations on graph engines
Mitliagkas, I., Borokhovich, M., Dimakis, A. G., & Caramanis, C. (2015) · Proceedings of the VLDB Endowment · doi:10.14778/2757807.2757812 · Cited by 44
Makkar, A., & Kumar, N. (2018) · Future Generation Computer Systems · doi:10.1016/j.future.2018.07.046 · Cited by 30
Organizing User Search Histories
Hwang, H., Lauw, H. W., Getoor, L. C., & Ntoulas, A. (2011) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.251 · Cited by 31
“Instead, we pick the most efficient Monte Carlo random walk simulation method among the ones presented in [15], and use it on QFG to approximate the stationary distribution for q .”
MethodLarge-scale graph analytics in Aster 6
Simmen, D. E., Schnaitter, K., Davis, J., et al. (2014) · Proceedings of the VLDB Endowment · doi:10.14778/2733004.2733013 · Cited by 29
“Adaptation might require invention of more sophisticated algorithms [18] than the centralized counterparts [23], substitute metrics that can be computed more efficiently at scale than classic metrics [21], or use of probabilistic techniques [9] that trade off accuracy for performance.”
BackgroundBidirectional PageRank Estimation: From Average-Case to Worst-Case
Lofgren, P., Banerjee, S., & Goel, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-26784-5_13 · Cited by 28
“We first summarize the existing methods for PageRank estimation: Monte Carlo Methods: A standard method [4,9] for estimating πσ[t] is by using the terminal node of independently generated random walks of length L ∼ Geometric(α) starting from a random node sampled from σ.”
MethodDistribution of PageRank Mass Among Principle Components of the Web
Avrachenkov, K., Litvak, N., & Pham, K. S. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-77004-6_2 · Cited by 29
“Of course, a drastic reduction of c also considerably accelerates the computation of PageRank by numerical methods [22, 5, 23].”
MethodSelf-citationYu, Q., Miao, Z., Wu, G., & Wei, Y. (2012) · Information Retrieval · doi:10.1007/s10791-012-9183-2 · Cited by 31
“Many technologies have been proposed to speed up the computation, such as the Monte Carlo methods (Avrachenkov et al. 2007), the inner-outer method (Gleich et al. 2010), the extrapolation methods (Brezinski et al. 2005; Haveliwala et al. 2003; Kamvar et al. 2003a), the adaptive method (Kamvar et…”
BackgroundMethodFAST-PPR: Scaling Personalized PageRank Estimation for Large GraphsPreprint
Lofgren, P., Banerjee, S., Goel, A., & Seshadhri, C. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.3181 · Cited by 33
“Monte-Carlo refers to the standard random-walk algorithm [13, 15, 16, 17] – we perform cMC δ walks and estimate πu(v) by the fraction of walks terminating at v.”
MethodA Survey on Proximity Measures for Social Networks
Cohen, S., Kimelfeld, B., & Koutrika, G. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-34213-4_13 · Cited by 28
Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks
Wang, S., & Tao, Y. (2018) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3183713.3196919 · Cited by 33
“2 we show that several existing algorithms [1, 3] designed for approximate PPR computation can be adapted to answer AHH queries as well.”
MethodFast Incremental and Personalized PageRankPreprint
Bahmani, B., Chowdhury, A., & Goel, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1006.2880 · Cited by 27
“Our algorithm is a Monte Carlo method [2] that works by maintaining a small number of short random walk segments starting at each node in the social graph.”
BackgroundMethodInfluentialConvergence 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
Fast and Exact Top-k Algorithm for PageRank
Fujiwara, Y., Nakatsuji, M., Shiokawa, H., Mishima, T., & Onizuka, M. (2013) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v27i1.8454 · Cited by 25
Manipulation-Resistant Reputations Using Hitting Time
Hopcroft, J. E., & Sheldon, D. R. (2007) · Springer eBooks · doi:10.1007/978-3-540-77004-6_6 · Cited by 42
Sensitivity Analysis of Centralities on Unweighted Networks
Murai, S., & Yoshida, Y. (2019) · doi:10.1145/3308558.3313422 · Cited by 25
“4 PageRank To analyze the edge sensitivity of PageRank, we use a random-walkbased representation of PageRank [3].”
MethodPROTECTOR: An optimized deep learning-based framework for image spam detection and prevention
Makkar, A., & Kumar, N. (2021) · Future Generation Computer Systems · doi:10.1016/j.future.2021.06.026 · Cited by 27
Heat kernel based community detectionPreprint
Kloster, K., & Gleich, D. F. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1403.3148 · Cited by 32
“[13] to achieve a randomized sublinear time algorithm to estimate the largest PageRank entries, and in fact, Monto Carlo methods frequently feature in PageRank computations due to the relationship between the diffusion and a random walk [7, 13, 8, 9].”
MethodIndex-Free Approach with Theoretical Guarantee for Efficient Random Walk with Restart Query
Lin, D., Wong, R. C.-W., Xie, M., & Wei, V. J. (2020) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde48307.2020.00084 · Cited by 23
“Specifically, the index-free approaches are: (1) Power, which generates the ground truth [21], (2) Forward Search (FWD) [2], (3) Random Walk sampling (MC) [4], (4) FORA, which has the best query performance among Monte-Carlo-based algorithms [29], (5) TopPPR, which has the best query performance for the top-K query [3…”
BackgroundMethodQuick Detection of High-Degree Entities in Large Directed Networks
Avrachenkov, K. E., Litvak, N., Prokhorenkova, L., & Suyargulova, E. (2014) · Proceedings · doi:10.1109/icdm.2014.95 · Cited by 27
“Most of our experiments are performed on the Twitter graph, because it is a good example of a huge network (approximately a billion of registered users) with a very limited rate of requests to API.”
MethodSelf-citationEfficient Algorithms for Personalized PageRankPreprint
Lofgren, P. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.04633 · Cited by 39
“These walks can be computed as needed or computed in advance, and various papers [4, 6, 11, 41] consider different variations.”
BackgroundMethodInfluentialToward Efficient Hub-Less Real Time Personalized PageRank
Pirouz, M., & Zhan, J. (2017) · IEEE Access · doi:10.1109/access.2017.2773038 · Cited by 22
“methods based on probabilistic techniques such as [33], where Avrachenkov et al.”
BackgroundMethodDynamics-based centrality for directed networks
Masuda, N., & Kori, H. (2010) · Physical Review E · doi:10.1103/physreve.82.056107 · Cited by 21
Distributed Randomized PageRank Algorithm Based on Stochastic Approximation
Lei, J., & Chen, H.-F. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2359311 · Cited by 19
“To reduce the computation burden, a random-walk-based algorithm is proposed in [9], and a randomized algorithm based on the mirror descent method of convex stochastic optimization is given in [8].”
MethodDistributed 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
“The work of [1] employs Monte Carlo simulation techniques.”
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
EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs
Li, H., & Chen, L. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3589308 · Cited by 23
“We first introduce the procedure in static graphs [2, 5, 41] and then propose an incremental sampling method for dynamic graphs.”
MethodComparing apples and oranges: normalized pagerank for evolving graphs
Berberich, K., Bedathur, S., Weikum, G., & Vazirgiannis, M. (2007) · International World Wide Web Conference (WWW) · doi:10.1145/1242572.1242737 · Cited by 26
“For the proof of the theorem we use the following lemma that follows from the results of Avrachenko et al. [ 1 ] and Jeh and Widom [6].”
MethodManipulation-Resistant Reputations Using Hitting Time
Hopcroft, J. E., & Sheldon, D. R. (2008) · Internet Mathematics · doi:10.1080/15427951.2008.10129303 · Cited by 23
“Computationally, the Monte Carlo methods in [9] and [ 3 ] are similar to our algorithms for hitting time.”
MethodAccelerating the Arnoldi-Type Algorithm for the PageRank Problem and the ProteinRank Problem
Wu, G., Zhang, Y., & Wei, Y. (2013) · Journal of Scientific Computing · doi:10.1007/s10915-013-9696-x · Cited by 18
“There are many efficient approaches for accelerating the computation, such as the Monte Carlo methods [2], the adaptive algorithms [26], the extrapolation methods [8,25], the reordering methods [22,30,54], the inner-outer algorithms [16], and so on.”
MethodInfluence Analysis in Evolving Networks: A Survey
Yu, Y., & Pei, J. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2934447 · Cited by 20
“The method is based on the probabilistic explanation of PageRank values [86], which is implied by another representation of the PageRank vector”
MethodWalking Randomly, Massively, and Efficiently
Łącki, J., Onak, K., Sankowski, P., et al. (2020) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 19
Optimized relativity search: node reduction in personalized page rank estimation for large graphs
Pirouz, M., & Zhan, J. (2016) · Journal Of Big Data · doi:10.1186/s40537-016-0047-2 · Cited by 21
Jin, Z., Shi, D., Wu, Q., Yan, H., & Fan, H. (2012) · ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp) · doi:10.1145/2370216.2370430 · Cited by 18
“[1] demonstrate that the Monte Carlo method provides good estimation of PageRank for relatively important pages already after one iteration.”
MethodView-based Explanations for Graph Neural Networks
Chen, T., Qiu, D., Wu, Y., Khan, A., Ke, X., & Gao, Y. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3639295 · Cited by 31
“For SYN dataset, we use sparse matrix multiplication and random walk technique [3, 12] to optimize the computation on large graphs, and parallelize on multi-processes.”
MethodUsing Web Graph Structure for Person Name Disambiguation.
Smirnova, E., Avrachenkov, K. E., & Trousse, B. (2010) · Cited by 18
Self-citationDynamic centrality measures for cattle trade networks
Hoscheit, P., Anthony, E., & Vergu, E. (2021) · Applied Network Science · doi:10.1007/s41109-021-00368-5 · Cited by 17
Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach
Liao, M., Li, R.-H., Dai, Q., & Wang, G. (2022) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3514221.3526140 · Cited by 32
“Specifically, previous PPR computation methods can be divided into two categories, including deterministic methods [3, 4, 10, 28] and Monte Carlo algorithms [7, 33].”
BackgroundMethodReal-Time PageRank on Dynamic Graphs
Sallinen, S., Luo, J., & Ripeanu, M. (2023) · ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC) · doi:10.1145/3588195.3593004 · Cited by 16
“There are also methods such as random walks [8, 43] or the Monte-Carlo method [1, 2], which we deem “approximate,” as they aim to provide an estimate.”
MethodFast Incremental PageRank on Dynamic Networks
Zhan, Z., Hu, R., Gao, X., & Huai, N. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-19274-7_12 · Cited by 16
A 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.”
MethodEfficient and Effective Similarity Search over Bipartite Graphs
Yang, R. (2022) · International World Wide Web Conference (WWW) · doi:10.1145/3485447.3511959 · Cited by 22
“Mathematically, the HPP value 𝜋 ( 𝑢,𝑢 𝑖 ) is formulated as follows [12]: In essence, HPP is the Personalized PageRank (PPR) [30, 38]”
MethodEfficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches
Liao, M., Li, R.-H., Dai, Q., Chen, H., Qin, H., & Wang, G. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3589305 · Cited by 25
“To our knowledge, one of best existing approximate algorithms that is tailored to PageRank centrality computation is such a Monte Carlo solution proposed in [3].”
MethodInfluentialProbabilistic Relation between In-Degree and PageRank
Litvak, N., Scheinhardt, W., & Volkovich, Y. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-78808-9_7 · Cited by 13
Self-citationBATON: Batch One-Hop Personalized PageRanks with Efficiency and Accuracy
Luo, S., Xiao, X., Lin, W., & Kao, B. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2912606 · Cited by 15
“Ref [4] also proposes a PageRank estimation using the entire random walk path.”
MethodPageRank computation via a distributed randomized approach with lossy communication
Ishii, H., Tempo, R., & Bai, E. (2012) · Systems & Control Letters · doi:10.1016/j.sysconle.2012.09.004 · Cited by 12
Efficient Resistance Distance Computation: The Power of Landmark-based Approaches
Liao, M., Li, R.-H., Dai, Q., Chen, H., Qin, H., & Wang, G. (2023) · Proceedings of the ACM on Management of Data · doi:10.1145/3588922 · Cited by 25
“Another set of methods are based on random walk sampling [7, 33, 47] which are also not very efficient to achieve a good estimation accuracy on large graphs.”
Sublinear Algorithms for Local Graph Centrality Estimation
Bressan, M., Peserico, E., & Pretto, L. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00073 · Cited by 11
“We employ SAMPLENODE() [42], a simple routine originally introduced in [31], [44], which emulates PageRank’s random walk using JUMP() and STEP() queries.”
BackgroundMethodInfluentialEdge-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
“By applying a power series expansion [11], the SSPPR vector π can be derived as:”
MethodDBpedia-Based Entity Linking via Greedy Search and Adjusted Monte Carlo Random Walk
Liu, M., Chen, L., Liu, B., Zheng, G., & Zhang, X. (2017) · ACM Transactions on Information Systems · doi:10.1145/3086703 · Cited by 13
“One is Power Iteration [24] and the other one is Monte Carlo random walk [1].”
BackgroundEfficient numerical methods to solve sparse linear equations with application to PageRank
Anikin, A. S., Gasnikov, A. V., Gornov, A. Y., Kamzolov, D., Maximov, Y., & Nesterov, Y. E. (2020) · Optimization methods & software · doi:10.1080/10556788.2020.1858297 · Cited by 26
Monte Carlo Based Incremental PageRank on Evolving Graphs
Liao, Q., Jiang, S., Yu, M., Yang, Y., & Li, T. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-57454-7_28 · Cited by 13
Approximating PageRank locally with sublinear query complexity.
Bressan, M., Peserico, E., & Pretto, L. (2014) · Padua Research Archive (University of Padova) · Cited by 11
Enabling graph mining in RDF triplestores using SPARQL for holistic in-situ graph analysis
Lee, S. M., Sukumar, S. R., Hong, S., et al. (2015) · Expert Systems with Applications · doi:10.1016/j.eswa.2015.11.010 · Cited by 11
Distributed Randomized Algorithms for PageRank Based on a Novel Interpretation
Suzuki, A., & Ishii, H. (2018) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2018.8430939 · Cited by 13
“, [1]) and distributed algorithms (e.”
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
Self-citationWTF, GPU! computing twitter's who-to-follow on the GPU
Geil, A., Wang, Y., & Owens, J. D. (2014) · doi:10.1145/2660460.2660481 · Cited by 11
“Both methods are quite accurate, but there are a few trade-offs [1].”
MethodA 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
Self-citationComputing the Stationary Distribution LocallyPreprint
Lee, C., Ozdaglar, A., & Shah, D. (2013) · arXiv (Cornell University) · Cited by 22
Surfing the Network for Ranking by Multidamping
Kollias, G., Gallopoulos, E., & Grama, A. Y. (2013) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.15 · Cited by 11
“[32] derive: (i) a Monte Carlo-type algorithm that computes, with high probability, a PageRank vector approximation with relative error at most 0.”
BackgroundMethodInfluentialDistributed 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
Metadata
- Authors
- Avrachenkov, K., Litvak, N., Nemirovsky, D., & Osipova, N.
- Affiliations
- Institut national de recherche en sciences et technologies du numérique (FR)
- Venue
- SIAM Journal on Numerical Analysis
- Published
- 2007-01
- Volume
- 45
- Issue
- 2
- Pages
- 890-904
- ISSN
- 0036-1429 (ISSN-L)
- 1095-7170
- OpenAlex
- W2107577105
- Cited by
- 250
- References
- 15
- Citations by year
- 2026: 2 · 2025: 5 · 2024: 15 · 2023: 13 · 2022: 15 · 2021: 10 · 2020: 13 · 2019: 20 · 2018: 10 · 2017: 14 · 2016: 17 · 2015: 19 · 2014: 27 · 2013: 18 · 2012: 11
- FWCI
- 12.08
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Numerical Analysis (publishedVersion)
- University of Twente Research Information (publishedVersion)
- University of Twente Research Information (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Physical Sciences › Computer Science › Information Systems › Information Retrieval and Search Behavior
- Physical Sciences › Mathematics › Statistics and Probability › Markov Chains and Monte Carlo Methods
- Keywords
- PageRank, Monte Carlo methods, power iteration, web page ranking, parallel computing
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-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-10 (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.



