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

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

Abstract
Related Papers

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 and 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.
[2]	P. Berkhin, A survey on PageRank computing, Internet Math., 2 (2005), 73-120. doi: 10.1080/15427951.2005.10129098.
[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.
[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.
[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.
[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.

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.
[2]	P. Berkhin, A survey on PageRank computing, Internet Math., 2 (2005), 73-120. doi: 10.1080/15427951.2005.10129098.
[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.
[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.
[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.
[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.

[1]	Paola Favati, Grazia Lotti, Ornella Menchi, Francesco Romani. An inner-outer regularizing method for ill-posed problems. Inverse Problems and 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 and 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 and 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 and 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 and 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]	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
[10]	Richard Evan Schwartz. Research announcement: unbounded orbits for outer billiards. Electronic Research Announcements, 2007, 14: 1-6. doi: 10.3934/era.2007.14.1
[11]	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
[12]	Pau Martín, David Sauzin, Tere M. Seara. Resurgence of inner solutions for perturbations of the McMillan map. Discrete and Continuous Dynamical Systems, 2011, 31 (1) : 165-207. doi: 10.3934/dcds.2011.31.165
[13]	David Maxwell. Kozlov-Maz'ya iteration as a form of Landweber iteration. Inverse Problems and 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 and 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 and 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 and 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, 2021, 29 (5) : 2959-2972. doi: 10.3934/era.2021021
[20]	Mark Comerford, Todd Woodard. Orbit portraits in non-autonomous iteration. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2253-2277. doi: 10.3934/dcdss.2019144

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Zhong-Zhi Bai
on Google Scholar
Zhong-Zhi Bai

[Back to Top]