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-76. doi: 10.1016/S0898-1221(96)00207-6.  Google Scholar

[2]

P. Berkhin, A survey on PageRank computing, Internet Math., 2 (2005), 73-120. 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-161. 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, Stanford, 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-371. 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-85. 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-76. doi: 10.1016/S0898-1221(96)00207-6.  Google Scholar

[2]

P. Berkhin, A survey on PageRank computing, Internet Math., 2 (2005), 73-120. 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-161. 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, Stanford, 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-371. 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-85. doi: 10.1002/nla.789.  Google Scholar

[1]

Paola Favati, Grazia Lotti, Ornella Menchi, Francesco Romani. An inner-outer regularizing method for ill-posed problems. Inverse Problems & Imaging, 2014, 8 (2) : 409-420. doi: 10.3934/ipi.2014.8.409
[2]

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
[3]

Olivier Bokanowski, Maurizio Falcone, Roberto Ferretti, Lars Grüne, Dante Kalise, Hasnaa Zidani. Value iteration convergence of $\epsilon$-monotone schemes for stationary Hamilton-Jacobi equations. Discrete & Continuous Dynamical Systems, 2015, 35 (9) : 4041-4070. doi: 10.3934/dcds.2015.35.4041
[4]

B. S. Lee, Arif Rafiq. Strong convergence of an implicit iteration process for a finite family of Lipschitz $\phi -$uniformly pseudocontractive mappings in Banach spaces. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 287-293. doi: 10.3934/naco.2014.4.287
[5]

Byung-Soo Lee. Strong convergence theorems with three-step iteration in star-shaped metric spaces. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 371-379. doi: 10.3934/naco.2011.1.371
[6]

Richard Evan Schwartz. Outer billiards and the pinwheel map. Journal of Modern Dynamics, 2011, 5 (2) : 255-283. doi: 10.3934/jmd.2011.5.255
[7]

Richard Evan Schwartz. Unbounded orbits for outer billiards I. Journal of Modern Dynamics, 2007, 1 (3) : 371-424. doi: 10.3934/jmd.2007.1.371
[8]

Inês Cruz, M. Esmeralda Sousa-Dias. Reduction of cluster iteration maps. Journal of Geometric Mechanics, 2014, 6 (3) : 297-318. doi: 10.3934/jgm.2014.6.297
[9]

Pau Martín, David Sauzin, Tere M. Seara. Resurgence of inner solutions for perturbations of the McMillan map. Discrete & Continuous Dynamical Systems, 2011, 31 (1) : 165-207. doi: 10.3934/dcds.2011.31.165
[10]

Daniel Genin. Research announcement: Boundedness of orbits for trapezoidal outer billiards. Electronic Research Announcements, 2008, 15: 71-78. doi: 10.3934/era.2008.15.71
[11]

Richard Evan Schwartz. Research announcement: unbounded orbits for outer billiards. Electronic Research Announcements, 2007, 14: 1-6. doi: 10.3934/era.2007.14.1
[12]

Richard Evan Schwartz. Outer billiards on the Penrose kite: Compactification and renormalization. Journal of Modern Dynamics, 2011, 5 (3) : 473-581. doi: 10.3934/jmd.2011.5.473
[13]

David Maxwell. Kozlov-Maz'ya iteration as a form of Landweber iteration. Inverse Problems & Imaging, 2014, 8 (2) : 537-560. doi: 10.3934/ipi.2014.8.537
[14]

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
[15]

Linhua Zhou, Meng Fan, Qiang Hou, Zhen Jin, Xiangdong Sun. Transmission dynamics and optimal control of brucellosis in Inner Mongolia of China. Mathematical Biosciences & Engineering, 2018, 15 (2) : 543-567. doi: 10.3934/mbe.2018025
[16]

I. Baldomá, Tere M. Seara. The inner equation for generic analytic unfoldings of the Hopf-zero singularity. Discrete & Continuous Dynamical Systems - B, 2008, 10 (2&3, September) : 323-347. doi: 10.3934/dcdsb.2008.10.323
[17]

Xiaoping Fang, Youjun Deng. Uniqueness on recovery of piecewise constant conductivity and inner core with one measurement. Inverse Problems & Imaging, 2018, 12 (3) : 733-743. doi: 10.3934/ipi.2018031
[18]

Mingtao Li, Guiquan Sun, Juan Zhang, Zhen Jin, Xiangdong Sun, Youming Wang, Baoxu Huang, Yaohui Zheng. Transmission dynamics and control for a brucellosis model in Hinggan League of Inner Mongolia, China. Mathematical Biosciences & Engineering, 2014, 11 (5) : 1115-1137. doi: 10.3934/mbe.2014.11.1115
[19]

Fang Li, Jie Pan. On inner Poisson structures of a quantum cluster algebra without coefficients. Electronic Research Archive, , () : -. doi: 10.3934/era.2021021
[20]

Mark Comerford, Todd Woodard. Orbit portraits in non-autonomous iteration. Discrete & Continuous Dynamical Systems - S, 2019, 12 (8) : 2253-2277. doi: 10.3934/dcdss.2019144

 Impact Factor: 

Tools

Metrics

  • PDF downloads (52)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences