American Institute of Mathematical Sciences

Advanced
  • Previous Article
    On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems
  • NACO Home
  • This Issue
  • Next Article
    Newton-MHSS methods for solving systems of nonlinear equations with complex symmetric Jacobian matrices
2012, 2(4): 855-862. doi: 10.3934/naco.2012.2.855

On convergence of the inner-outer iteration method for computing PageRank

Zhong-Zhi Bai 1,

1. 

School of Mathematics and Computer Science, Guizhou Normal University, Guiyang 550001, China

Received  January 2012 Revised  October 2012 Published  November 2012

Without imposing any restriction on the damping factors and the stopping tolerances, we prove the overall convergence of the inner-outer iteration method for computing the PageRank vector, which was proposed by Gleich, Gray, Greif and Lau (SIAM J. Sci. Comput. 32(2010)349-371). Based on the formula of the contraction factor of the method, we discuss possible choices of the iteration parameters, which could be practically useful for accelerating the convergence rate of the inner-outer iteration method.
Keywords: inner-outer iteration, convergence., PageRank.
Mathematics Subject Classification: Primary: 65F10, 65F15; Secondary: 65C4.
Citation: Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855
References:
[1]

Z. -Z. Bai, J. -C. Sun and D. -R. Wang, A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations,, Computers Math. Appl., 32 (1996), 51.  doi: 10.1016/S0898-1221(96)00207-6.  Google Scholar

[2]

P. Berkhin, A survey on PageRank computing,, Internet Math., 2 (2005), 73.  doi: 10.1080/15427951.2005.10129098.  Google Scholar

[3]

A. N. Langville and C. D. Meyer, A survey of eigenvector methods for Web information retrieval,, SIAM Rev., 47 (2005), 135.  doi: 10.1137/S0036144503424786.  Google Scholar

[4]

L. Page, S. Brin, R. Motwani and T. Winograd, "The PageRank Citation Ranking: Bringing Order to the Web,", Stanford Digital Libraries SIDL-WP-1999-0120, (1999), 1999.   Google Scholar

[5]

D. F. Gleich, A. P. Gray, C. Greif and T. Lau, An inner-outer iteration for computing PageRank,, SIAM J. Sci. Comput., 32 (2010), 349.  doi: 10.1137/080727397.  Google Scholar

[6]

J. -F. Yin, G. -J. Yin and M. K. Ng, On adaptively accelerated Arnoldi method for computing PageRank,, Numer. Linear Algebra Appl., 19 (2012), 73.  doi: 10.1002/nla.789.  Google Scholar

show all references

References:
[1]

Z. -Z. Bai, J. -C. Sun and D. -R. Wang, A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations,, Computers Math. Appl., 32 (1996), 51.  doi: 10.1016/S0898-1221(96)00207-6.  Google Scholar

[2]

P. Berkhin, A survey on PageRank computing,, Internet Math., 2 (2005), 73.  doi: 10.1080/15427951.2005.10129098.  Google Scholar

[3]

A. N. Langville and C. D. Meyer, A survey of eigenvector methods for Web information retrieval,, SIAM Rev., 47 (2005), 135.  doi: 10.1137/S0036144503424786.  Google Scholar

[4]

L. Page, S. Brin, R. Motwani and T. Winograd, "The PageRank Citation Ranking: Bringing Order to the Web,", Stanford Digital Libraries SIDL-WP-1999-0120, (1999), 1999.   Google Scholar

[5]

D. F. Gleich, A. P. Gray, C. Greif and T. Lau, An inner-outer iteration for computing PageRank,, SIAM J. Sci. Comput., 32 (2010), 349.  doi: 10.1137/080727397.  Google Scholar

[6]

J. -F. Yin, G. -J. Yin and M. K. Ng, On adaptively accelerated Arnoldi method for computing PageRank,, Numer. Linear Algebra Appl., 19 (2012), 73.  doi: 10.1002/nla.789.  Google Scholar

[1]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[2]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[3]

George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003
[4]

Matania Ben–Artzi, Joseph Falcovitz, Jiequan Li. The convergence of the GRP scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 1-27. doi: 10.3934/dcds.2009.23.1
[5]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[6]

Philipp Harms. Strong convergence rates for markovian representations of fractional processes. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020367
[7]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[8]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[9]

Toshiko Ogiwara, Danielle Hilhorst, Hiroshi Matano. Convergence and structure theorems for order-preserving dynamical systems with mass conservation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3883-3907. doi: 10.3934/dcds.2020129
[10]

Xiuli Xu, Xueke Pu. Optimal convergence rates of the magnetohydrodynamic model for quantum plasmas with potential force. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 987-1010. doi: 10.3934/dcdsb.2020150
[11]

Takiko Sasaki. Convergence of a blow-up curve for a semilinear wave equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1133-1143. doi: 10.3934/dcdss.2020388
[12]

Matúš Tibenský, Angela Handlovičová. Convergence analysis of the discrete duality finite volume scheme for the regularised Heston model. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1181-1195. doi: 10.3934/dcdss.2020226
[13]

Thomas Frenzel, Matthias Liero. Effective diffusion in thin structures via generalized gradient systems and EDP-convergence. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 395-425. doi: 10.3934/dcdss.2020345
[14]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[15]

Yi-Long Luo, Yangjun Ma. Low Mach number limit for the compressible inertial Qian-Sheng model of liquid crystals: Convergence for classical solutions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 921-966. doi: 10.3934/dcds.2020304
[16]

Gheorghe Craciun, Jiaxin Jin, Casian Pantea, Adrian Tudorascu. Convergence to the complex balanced equilibrium for some chemical reaction-diffusion systems with boundary equilibria. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1305-1335. doi: 10.3934/dcdsb.2020164
[17]

Jan Březina, Eduard Feireisl, Antonín Novotný. On convergence to equilibria of flows of compressible viscous fluids under in/out–flux boundary conditions. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021009
[18]

Mario Bukal. Well-posedness and convergence of a numerical scheme for the corrected Derrida-Lebowitz-Speer-Spohn equation using the Hellinger distance. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021001
[19]

Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077
[20]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

 Impact Factor: 

Tools

Metrics

  • PDF downloads (37)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences