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
Items 101–200 of 254
Preventing the diffusion of information to vulnerable users while preserving PageRank
Loukides, G., & Gwadera, R. (2017) · International Journal of Data Science and Analytics · doi:10.1007/s41060-017-0082-x · Cited by 10
Distributed Randomized Algorithms for PageRank Computation: Recent Advances
Ishii, H., & Suzuki, A. (2018) · Systems & control · doi:10.1007/978-3-030-04630-9_12 · Cited by 11
Makkar, A. (2022) · Sustainable Cities and Society · doi:10.1016/j.scs.2021.103658 · Cited by 10
Distributively Computing Random Walk Betweenness Centrality in Linear Time
Hua, Q.-S., Ai, M., Jin, H., et al. (2017) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2017.287 · Cited by 10
A local updating algorithm for personalized PageRank via Chebyshev polynomials
Bautista, E., & Matthieu Latapy, B. (2022) · Social Network Analysis and Mining · doi:10.1007/s13278-022-00860-5 · Cited by 11
“This interpretation of Personalized PageRank has been exploited by numerous works to develop fast algorithms for computing PageRank (Haveliwala 1999; Kamvar et al. 2004; Fujiwara et al. 2012; Bahmani et al. 2011; Maehara et al. 2014; Avrachenkov et al. 2007; Andersen et al. 2006; Berkhin 2006).”
MethodGleich, D. F., Komjáthy, J., & Litvak, N. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-26784-5 · Cited by 12
Self-citationMANIPULATION OF PAGERANK AND COLLECTIVE HIDDEN MARKOV MODELS
Sheldon, D. R. (2010) · eCommons (Cornell University) · Cited by 10
Tight Bounds for Distributed Graph Computations.Preprint
Pandurangan, G., Robinson, P., & Scquizzato, M. (2016) · arXiv (Cornell University) · Cited by 10
On the complexity of the Monte Carlo method for incremental PageRank
Lofgren, P. (2013) · Information Processing Letters · doi:10.1016/j.ipl.2013.11.006 · Cited by 9
“They use the Monte Carlo method of computing PageRank [2].”
MethodInfluentialFriend recommendation with a target user in social networking services
Kim, S. (2015) · IEEE International Conference on Data Engineering Workshops (ICDEW) · doi:10.1109/icdew.2015.7129582 · Cited by 11
“This experimentally shows that findings of [15], [22] are valid in the case of Katz centrality and influence.”
MethodBinRank: Scaling Dynamic Authority-Based Search Using Materialized Subgraphs
Hwang, H., Balmin, A., Reinwald, B., & Nijkamp, E. (2010) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.85 · Cited by 10
“Therefore, the issue of scalability of PPR has attracted a lot of attention [3], [4], [5].”
BackgroundMethodInfluentialPairwise comparisons in spectral ranking
Tang, Y., & Li, Y. (2016) · Neurocomputing · doi:10.1016/j.neucom.2016.08.029 · Cited by 8
“, the Monte Carlo sampling based on short random walks [16], subgraph based method [17], ε-approximation method [5], and linear system solver related method [18].”
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.”
MethodFrogWild! -- Fast PageRank Approximations on Graph EnginesPreprint
Mitliagkas, I., Borokhovich, M., Dimakis, A. G., et al. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.04281 · Cited by 9
“In [5], a random-walks-based algorithm is proposed.”
Sublinear estimation of a single element in sparse linear systems
Shyamkumar, N., Banerjee, S., & Lofgren, P. (2016) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2016.7852323 · Cited by 8
“These are widely used for estimating transition probabilities and PageRank [11].”
MethodUSE OF THE LINK RANKING METHOD TO EVALUATE SCIENTIFIC ACTIVITIES OFSCIENTIFIC SPACE SUBJECTS
Biloshchytskyi, A. O., Kuchansky, A., Andrashko, Y., & Biloshchytska, S. (2020) · Scientific Journal of Astana IT University · doi:10.37943/aitu.2020.1.63600 · Cited by 8
“[15] described the application of the Monte Carlo method to accelerate the finding of the PR index.”
MethodA Hessenberg-type algorithm for computing PageRank Problems
Gu, X., Lei, S., Zhang, K., Shen, Z.-L., Wen, C., & Carpentieri, B. (2021) · Numerical Algorithms · doi:10.1007/s11075-021-01175-w · Cited by 10
“When the damping factor α is close to 1, more sophisticated and efficient numerical method should be developed, such as the Monte Carlo methods [10], the adaptive algorithms [3, 11], the extrapolation methods [2, 7, 12], the reordering methods [13, 14], the inner-outer algorithms [15], and so on.”
MethodOn the distributed complexity of large-scale graph computations
Pandurangan, G., Robinson, P., & Scquizzato, M. (2021) · Padua Research Archive (University of Padova) · doi:10.1145/3460900 · Cited by 8
“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 [3, 19].”
BackgroundMethodA Review of Graph-Based Models for Entity-Oriented Search
Devezas, J. L., & Nunes, S. (2021) · SN Computer Science · doi:10.1007/s42979-021-00828-w · Cited by 15
“It can be solved through Gaussian elimination, power iteration or even Monte Carlo methods [12].”
BackgroundReinforcement Learning for Matrix Computations: PageRank as an Example
Borkar, V. S., & Mathkar, A. S. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-04483-5_2 · Cited by 8
“While a bulk of the work in this direction has been on efficient computations for the power method, there have also been alternative approaches, such as Markov Chain Monte Carlo [17], [18], optimization based methods [19], and schemes based on stochastic approximation and/or gossip [20], [21], [22].”
MethodBinRank: Scaling Dynamic Authority-Based Search Using Materialized SubGraphs
Hwang, H., Balmin, A., Reinwald, B., & Nijkamp, E. (2009) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2009.94 · Cited by 10
Distributed 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
“The PageRank value, or simply the value, of page i ∈ V is a real number denoted by x ∗ ∈ [0, 1 ]. The values are ordered: x ∗ > x ∗ j implies that page i is more important than page j.”
BackgroundMethodMitra, A., Kundu, A., Chattopadhyay, M., et al. (2022) · SN Computer Science · doi:10.1007/s42979-022-01315-6 · Cited by 7
Voting-based Opinion Maximization
Saha, A., Ke, X., Khan, A., & Lakshmanan, L. V. S. (2023) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde55515.2023.00048 · Cited by 7
“Other baselines include seed selection via (7) PageRank score (PR) (based on the intuition that more frequently reached nodes in a random graph traversal are more likely to influence other users), (8) Random Walk with Restart (RWR) [25] and (9) Degree Centrality (DC) .”
InfluentialSato, R. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977172.62 · Cited by 14
“Discussion: We point out that Monte-Carlo methods [2, 9], forward push [1], and their variants [35, 36] for estimating the personalized PageRank also run locally, and they do not require full construction of the recommendation network beforehand.”
MethodMonte Carlo Methods for Top-k Personalized PageRank Lists and Name DisambiguationPreprint
Avrachenkov, K. E., Litvak, N., Nemirovsky, D., Smirnova, E., & Sokol, M. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1008.3775 · Cited by 17
“In [5], it has been shown that to find elements with large values of PageRank the Monte Carlo approach requires about the same number of operations as one iteration of the power iteration method.”
Self-citationA spatiotemporal event correlation approach to computer security
O’Hallaron, D. R., Zhang, H., & Xie, Y. (2005) · Cited by 8
Bidirectional PageRank Estimation: From Average-Case to Worst-CasePreprint
Lofgren, P., Banerjee, S., & Goel, A. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.08705 · Cited by 7
“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 σ.”
MethodSchmitt, M. F. L., & Spinosa, E. J. (2022) · User Modeling and User-Adapted Interaction · doi:10.1007/s11257-021-09315-6 · Cited by 8
“Similar to Fogaras et al. (2005); Avrachenkov et al. (2007); Sarkar et al. (2008), we can show that the rate of convergence of Eq.”
ResultInfluentialA Model Based on Cocitation for Web Information Retrieval
Xie, Y., & Huang, T. (2014) · Mathematical Problems in Engineering · doi:10.1155/2014/418605 · Cited by 6
Nearest-neighbor Queries in Probabilistic Graphs
Potamias, M., Bonchi, F., Gionis, A., & Kollios, G. (2009) · OpenBU (Boston University) · Cited by 6
Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based Approach
Liao, M., Zhou, J., Li, R.-H., et al. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3654936 · Cited by 5
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.”
BackgroundBIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRank
Liu, H., & Luo, S. (2024) · Proceedings of the VLDB Endowment · doi:10.14778/3665844.3665855 · Cited by 11
A Group-to-Group Version of Random Walk Betweenness Centrality
Gillani, I. A., Bagchi, A., & Ranu, S. (2020) · doi:10.1145/3430984.3431020 · Cited by 5
“computing this metric within ε precision isO ( log ε log(1−c)nnz(P) ) [4],”
MethodA parallel PageRank algorithm for undirected graph
Zhang, Q., Tang, R., Yao, Z., & Zhang, Z. (2023) · Applied Mathematics and Computation · doi:10.1016/j.amc.2023.128276 · Cited by 4
“Monte Carlo method [8] is also an excellent PageRank algorithm.”
MethodMultiway Monte Carlo Method for Linear Systems
Wu, T., & Gleich, D. F. (2019) · SIAM Journal on Scientific Computing · doi:10.1137/18m121527x · Cited by 5
“, 2005), real world application (Wang et al., 2008; Avrachenkov et al., 2007), convergence analysis (Ji, Mascagni, and Li, 2013; Benzi et al.”
Tracking Virality and Susceptibility in Social Media
Hoang, T.-A., & Lim, E. (2016) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/2983323.2983800 · Cited by 10
“We therefore employ the random walk-based method to approximate the rank efficiently and incrementally [3].”
MethodA Structural Result for Personalized PageRank and its Algorithmic Consequences
Vial, D., & Subramanian, V. (2019) · ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS) · doi:10.1145/3309697.3331481 · Cited by 4
Word Sense Disambiguation Based on Constrained RandomWalks in Linked Semantic Networks
Janz, A., & Piasecki, M. (2019) · doi:10.26615/978-954-452-056-4_061 · Cited by 5
“The authors in (Avrachenkov et al., 2007) proved that we can easily approximate PageRank values using random walks with restarts.”
MethodQuick Detection of High-degree Entities in Large Directed NetworksPreprint
Avrachenkov, K. E., Litvak, N., Prokhorenkova, L., & Suyargulova, E. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1410.0571 · Cited by 7
“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-citationDistribution of PageRank Mass Among Principle Components of the WebPreprint
Avrachenkov, K. E., Litvak, N., & Pham, K. S. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0709.2016 · Cited by 5
“Of course, a drastic reduction of c also considerably accelerates the computation of PageRank by numerical methods [22, 5, 23].”
MethodSelf-citationEstimating Single-Node PageRank in Õ (min{ d t , √ m }) Time
Wang, H., & Wei, Z. (2023) · Proceedings of the VLDB Endowment · doi:10.14778/3611479.3611500 · Cited by 10
Varshitha, K., Talada, S. V., & Mitra, A. (2025) · Risk sciences. · doi:10.1016/j.risk.2025.100013 · Cited by 4
An Improved Approach to the PageRank Problems
Xie, Y., Huang, T., Wen, C., et al. (2013) · Journal of Applied Mathematics · doi:10.1155/2013/438987 · Cited by 4
Li, S., Huang, X., & Lee, C.-H. (2021) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3447548.3467431 · Cited by 6
“While Monte Carlo-type methods or algorithms have been proposed in the literature, their focus has been limited to computing PageRank [2] and solving a large system of linear equations [10, 15].”
MethodRevisiting Local Computation of PageRank: Simple and Optimal
Wang, H., Wei, Z., Wen, J.-R., & Yang, M. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649661 · Cited by 4
“…called RBS , which detects the 𝛿 -contributing set in (cid:101) 𝑂 ( 1 / 𝛿 ) time by applying randomness to the However, RBS requires Θ ( 𝑛 + 𝑚 ) time and bound shows that this (cid:101) 𝑂 ( 1 / 𝛿 ) bound is in general impossible to hand, show that ApproxContributions is already optimal.”
MethodPersonalized PageRanks over Dynamic Graphs - The Case for Optimizing Quality of Service
Zhu, Z., Luo, S., Lin, W., Wang, S., Mo, D., & Li, C. (2024) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde60146.2024.00038 · Cited by 4
Multi-relational PageRank for tree structure sense ranking
Interdonato, R., & Tagarelli, A. (2014) · World Wide Web · doi:10.1007/s11280-014-0302-4 · Cited by 4
“In this regard, the study in [3] gives evidence of the fact that setting m = 1 can be deemed as “sufficient” in practice, and that after m iterations, the relative error of the Monte Carlo method will reduce on average only by a factor 1/ √ m.”
BackgroundMethodInfluentialDesign of sensor placement based on fault diagnosability
Hu, X., Zhang, X., Peng, X., et al. (2017) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2017.8028468 · Cited by 4
Sublinear Algorithms for Local Graph-Centrality Estimation
Bressan, M., Peserico, E., & Pretto, L. (2023) · SIAM Journal on Computing · doi:10.1137/19m1266976 · Cited by 3
Pashikanti, R. P., & Kundu, S. (2022) · Social Network Analysis and Mining · doi:10.1007/s13278-022-00968-8 · Cited by 4
“There are many variations evolved (Breyer 2002; Var-gas 2020; Salehi 2007; Zhou 2015; Avrachenkov et al. 2007) from the above formulation for approximating Pag-eRank ( 𝜋 ).”
BackgroundA new approach for aggregated PageRank computation via distributed randomized algorithms
Ishii, H., Tempo, R., & Bai, E. (2011) · doi:10.1109/cdc.2011.6160880 · Cited by 3
“The work of [1] employs techniques based on Monte Carlo simulation.”
MethodSoudani, N. M., Fatemi, A., & Nematbakhsh, M. A. (2019) · Knowledge and Information Systems · doi:10.1007/s10115-019-01328-3 · Cited by 3
On the Role of Clustering in Personalized PageRank Estimation
Vial, D., & Subramanian, V. (2019) · ACM Transactions on Modeling and Performance Evaluation of Computing Systems · doi:10.1145/3366635 · Cited by 6
“[5], which analyzes Monte Carlo methods for global PageRank estimation, based on both the final step of sampled random walks (as given by (3)) and the number of visits along the entire walk.”
BackgroundMethodLightTraffic: On Optimizing CPU-GPU Data Traffic for Efficient Large-scale Random Walks
Xing, Y., Li, Y., Wang, Z.-Q., et al. (2023) · Proceedings - International Conference on Data Engineering · doi:10.1109/icde55515.2023.00073 · Cited by 3
“For PageRank and uniform sampling, walks are started uniformly at all vertices, and terminated when the number of walked steps reaches l .”
MethodInfluentialPerformance Evaluation of Parallel Graphs Algorithms Utilizing Graphcore IPU
Gepner, P., Kocot, B., Paprzycki, M., et al. (2024) · Electronics · doi:10.3390/electronics13112011 · Cited by 3
FPPR: Fast Pessimistic PageRank for Dynamic Directed Graphs
Pashikanti, R. P., & Kundu, S. (2022) · Studies in computational intelligence · doi:10.1007/978-3-030-93409-5_23 · Cited by 2
Analysis of an on-line algorithm for solving large Markov chains
Litvak, N., & Robert, P. H. (2008) · International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS) · doi:10.4108/icst.valuetools2008.4425 · Cited by 3
“[4, 7]), as well as developing and testing alternative techniques [1, 3].”
BackgroundSelf-citationPersonalizing Forum Search using Multidimensional Random Walks
Ganu, G., & Marian, A. (2014) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v8i1.14515 · Cited by 3
“The second approach to compute PageRank is based on Monte Carlo approximation and is very efficient and highly scalable [Avrachenkov et al., 2007].”
MethodRanking-Based Community Detection for Social Networks
Pirouz, M. (2021) · Lecture notes in networks and systems · doi:10.1007/978-3-030-89912-7_22 · Cited by 3
The Power of AI in IoT : Cognitive IoT-based Scheme for Web Spam Detection
Makkar, A., Kumar, N., & Guizani, M. (2019) · IEEE Symposium Series on Computational Intelligence (SSCI) · doi:10.1109/ssci44817.2019.9002885 · Cited by 3
“The information about all the visited pages is maintained by this algorithm [8].”
Distributed Computation of Sparse CutsPreprint
Sarma, A. D., Molla, A. R., & Pandurangan, G. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1310.5407 · Cited by 3
“However, the algorithm of [16] is for computing the general PageRank (not personalized) (using an approach due to [7]).”
BackgroundAvrachenkov, K. E., Nemirovsky, D., & Osipova, N. (2006) · doi:10.1145/1190095.1190164 · Cited by 3
“These methods are probabilistic Monte Carlo (MC) methods [2], [4].”
MethodSelf-citationApproximating the Stationary Probability of a Single State in a Markov chainPreprint
Lee, C. E., Ozdaglar, A., & Shah, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.1986 · Cited by 6
“Bahmani et al. (2010) addressed how to incrementally update the PageRank vector for dynamically evolving graphs, or graphs where the edges arrive in a streaming manner.”
BackgroundMethodOptimization, control, and game theoretical problems in consensus protocols
Chamie, M. E. (2014) · theses.fr (ABES) · doi:10.70675/d2dd4ab5zaaecz4bc6za36fzc8bbe36b47cf · Cited by 3
Efficient and Accurate PageRank Approximation on Large Graphs
Wu, S., Wu, D., Quan, J., Chan, T. N., & Lu, K. (2024) · Proceedings of the ACM on Management of Data · doi:10.1145/3677132 · Cited by 2
On Efficient Single-Source Personalized PageRank Computation in Online Social Networks
Wei, V. J., Jiang, D., & Zhang, C. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3551751 · Cited by 2
Red Light Green Light Method for Solving Large Markov Chains
Avrachenkov, K. E., Brown, P., & Litvak, N. (2022) · Journal of Scientific Computing · doi:10.1007/s10915-022-01976-8 · Cited by 6
“This includes Monte-Carlo algorithms [17, 5], based on simulation of random walks, and the OPIC algorithm [1, 28, 29], based on redistribution of positive cash.”
MethodSelf-citationPageRank Algorithm Based on Dynamic Damping Factor
HaoLin, Z., Hu, J., & WeiKai, L. (2023) · International Conference on Cyber-Physical Social Intelligence (ICCSI) · doi:10.1109/iccsi58851.2023.10303849 · Cited by 3
Biloshchytskyi, A. O., Omirbayev, S., Mukhatayev, A., et al. (2024) · Procedia Computer Science · doi:10.1016/j.procs.2023.12.161 · Cited by 2
Approximate Local Sums and Their Applications in Radio Networks
Liu, Z., & Herlihy, M. P. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-45174-8_17 · Cited by 2
On perturbations of principal eigenvectors of substochastic matrices
Bourchtein, L., & Bourchtein, A. (2015) · Journal of Computational and Applied Mathematics · doi:10.1016/j.cam.2015.01.013 · 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].”
Limiting the Diffusion of Information by a Selective PageRank-Preserving Approach
Loukides, G., & Gwadera, R. (2016) · IEEE International Conference on Data Science and Advanced Analytics (DSAA) · doi:10.1109/dsaa.2016.16 · Cited by 2
Accelerating PageRank computations
Wierzchoń, S. T., Kłopotek, M. A., Ciesielski, K., Czerski, D., & Dramiński, M. (2011) · Control and Cybernetics · Cited by 2
A Survey on Recommendation Techniques in Numerous Domains
Jain, G., Mishra, N., & Sharma, S. (2013) · International Journal of Computer Applications · doi:10.5120/11745-7379 · Cited by 2
A Structural Result for Personalized PageRank and its Algorithmic Consequences
Vial, D., & Subramanian, V. (2019) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3341617.3326140 · Cited by 4
“Beyond [33], many other works have proposed efficient computation and estimation algorithms for PPR; a small sample includes those using linear algebraic techniques [45, 46], those using dynamic programming [3, 4], and those using randomized schemes [7, 39].”
BackgroundBetter than PageRank: Hitting Time as a Reputation Mechanism
Liu, B. (2014) · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · Cited by 2
Disabling External Influence in Social Networks via Edge RecommendationPreprint
Amelkin, V., & Singh, A. K. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.08139 · Cited by 4
“[27], who show that PageRank of high-centrality nodes estimated via Monte Carlo simulation converge very fast.”
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
Multi-Scale Matrix Sampling and Sublinear-Time PageRank ComputationPreprint
Borgs, C., Brautbar, M., Chayes, J., et al. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.2771 · Cited by 2
“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.”
MethodConnectivity of random graphs after centrality-based vertex removal
van der Hofstad, R., & Pandey, M. (2024) · Journal of Applied Probability · doi:10.1017/jpr.2023.106 · Cited by 1
Goikoetxea, J., Martín, I. S., & Arantzeta, M. (2024) · Frontiers in Language Sciences · doi:10.3389/flang.2024.1458887 · Cited by 1
Zhang, M., & Yu, W. (2025) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/3726302.3730113 · Cited by 1
FFSB: Fast Fibonacci Series-Based personalized PageRank on MPI
Yin, H., Li, J., & Niu, Y. (2013) · International Conference on Information, Communications & Signal Processing (ICICS) · doi:10.1109/icics.2013.6782908 · Cited by 1
“Based this ideal, Fogaras et al[5] and Avrachenkov et al[6] proposed their Monte Carlo approaches to approximate the personalized PageRank.”
User Search Histories Based On Query RelevanceUsing Incremental Algorithm
Revathi, A. R., & Mekala, A. (2014) · International Journal of Innovative Research in Computer and Communication Engineering · Cited by 1
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],…”
MethodParallel Computation of Reverse PageRank Problem with Evaluating Single Page
Lai, S., Yang, Y., Guo, M., et al. (2016) · doi:10.1109/bdcloud-socialcom-sustaincom.2016.22 · Cited by 1
“There are mainly two ways to calculate PageRank values.”
BackgroundAnalysis of economic crisis based on double-layer network of international investment and trade
Wei, M., Zhang, S., & Wang, L. (2017) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2017.8027564 · Cited by 3
“We pick out the top 20 countries according to their values of PageRank in 2007 according to results in [19, 20], which could provide a rough estimation of how important a country is as proved in [21], and show their networks of international investment and trade respectively in 2008.”
BackgroundA Load Balancing Strategy for Monte Carlo Method in PageRank Problem
Shao, B., Lai, S., Yang, B., Xu, Y., & Lin, X. (2017) · Communications in computer and information science · doi:10.1007/978-981-10-6442-5_56 · Cited by 1
Text correlation calculation based on passage-level event representation
ZHENG, Z., Li, Y., Liu, M., Qin, B., & Yitong, L. I. U. (2020) · Scientia Sinica Informationis · doi:10.1360/ssi-2019-0272 · Cited by 2
Optimized Ranking-Based Community Detection
Pirouz, M. (2021) · International Conference on Computational Science and Computational Intelligence (CSCI) · doi:10.1109/csci54926.2021.00281 · Cited by 1
“There are several solutions, such as HubRank, developed by adapting the Monte Carlo method [7] [8] [9] [10].”
MethodSupporting secure dynamic alert zones using searchable encryption and graph embedding
Shaham, S., Ghinita, G., & Shahabi, C. (2023) · The VLDB Journal · doi:10.1007/s00778-023-00803-2 · Cited by 1
“The number of samples required to estimate the stationary distribution is shown to pessimistically be in the order O(n(2)), where n indicates the number of states; however, it is shown that n random walks are enough to provide a reasonable approximation of a stationary distribution [1].”
Random Walk Based Inverse Influence Research in Online Social Networks
Jin, Z., Wu, Q., Shi, D., et al. (2013) · doi:10.1109/hpcc.and.euc.2013.316 · Cited by 1
Two-hop walks indicate PageRank order
Tang, Y. (2019) · Pattern Recognition · doi:10.1016/j.patcog.2019.06.010 · Cited by 2
“Much effort for accelerating the PageRank algorithm has been carried out from different view, such as Monte Carlo method [16], random walk [17], power method or general linear system [18, 19], graph theory [20, 21, 22], Schrödinger equation [23], and quantum networks [24, 25].”
MethodWalking randomly, massively, and efficiently
Łącki, J., Mitrović, S., Onak, K., & Sankowski, P. (2020) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3357713.3384303 · Cited by 45
Discriminative Streaming Network Embedding
Qi, Y., Cheng, J., Chen, X., Cheng, R. C. K., Bifet, A., & Wang, P. (2019) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.105138
Biloshchytskyi, A. O., Kuchansky, A., Biloshchytska, S., et al. (2022) · Scientific Journal of Astana IT University · doi:10.37943/xtpk5061 · Cited by 1
Applications of Randomized Algorithms
Tempo, R., Calafiore, G. C., & Dabbene, F. (2012) · Communications and control engineering/Communications and control engineering series · doi:10.1007/978-1-4471-4610-0_19 · Cited by 1
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.



