A Hessenberg-type algorithm for computing PageRank Problems

被引：10

作者：

Gu, Xian-Ming ^{[1
,2
]}

Lei, Siu-Long ^{[3
]}

Zhang, Ke ^{[4
]}

Shen, Zhao-Li ^{[5
]}

Wen, Chun ^{[6
]}

Carpentieri, Bruno ^{[7
]}

机构：

[1] Southwestern Univ Finance & Econ, Sch Econ Math, Inst Math, Chengdu 611130, Sichuan, Peoples R China

[2] Univ Groningen, Bernoulli Inst Math Comp Sci & Artificial Intelli, Nijenborgh 9,POB 407, NL-9700 AK Groningen, Netherlands

[3] Univ Macau, Fac Sci & Technol, Dept Math, Ave Univ, Macau, Peoples R China

[4] Shanghai Maritime Univ, Coll Arts & Sci, Shanghai 201306, Peoples R China

[5] Sichuan Agr Univ, Coll Sci, Dept Appl Math, Yaan 625014, Sichuan, Peoples R China

[6] Univ Elect Sci & Technol China, Sch Math Sci, Chengdu 611731, Sichuan, Peoples R China

[7] Libera Univ Bolzano, Fac Sci & Tecnol Informat, Dominikanerpl 3 Piazza Domenicani,3 Italy, I-39100 Bozen Bolzano, Italy

来源：

NUMERICAL ALGORITHMS | 2022年 / 89卷 / 04期

关键词：

PageRank vector; Hessenberg process; Arnoldi process; Krylov subspace method; Ritz values; NONSYMMETRIC LINEAR-SYSTEMS; BLOCK CMRH METHOD; GLOBAL HESSENBERG; ARNOLDI METHOD; MATRIX; ITERATION; EIGENVECTOR; COMPUTATION;

D O I：

10.1007/s11075-021-01175-w

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

PageRank is a widespread model for analysing the relative relevance of nodes within large graphs arising in several applications. In the current paper, we present a cost-effective Hessenberg-type method built upon the Hessenberg process for the solution of difficult PageRank problems. The new method is very competitive with other popular algorithms in this field, such as Arnoldi-type methods, especially when the damping factor is close to 1 and the dimension of the search subspace is large. The convergence and the complexity of the proposed algorithm are investigated. Numerical experiments are reported to show the efficiency of the new solver for practical PageRank computations.

引用

页码：1845 / 1863

页数：19

共 53 条

[1]

Addam M, 2017, ELECTRON T NUMER ANA, V46, P460

[2] Weighted and flexible versions of block CMRH method for solving nonsymmetric linear systems with multiple right-hand sides [J].

Amini, S. ;

Toutounian, F. .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2018, 76 (08) :2011-2021

[3] The block CMRH method for solving nonsymmetric linear systems with multiple right-hand sides [J].

Amini, S. ;

Toutounian, F. ;

Gachpazan, M. .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2018, 337 :166-174

[4] A restarted Induced Dimension Reduction method to approximate eigenpairs of large unsymmetric matrices [J].

Astudillo, R. ;

van Gijzen, M. B. .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2016, 296 :24-35

[5] Monte Carlo methods in pagerank computation: When one iteration is sufficient [J].

Avrachenkov, K. ;

Litvak, N. ;

Nemirovsky, D. ;

Osipova, N. .

SIAM JOURNAL ON NUMERICAL ANALYSIS, 2007, 45 (02) :890-904

[6] A Survey on PageRank Computing [J].

Berkhin, Pavel .

INTERNET MATHEMATICS, 2005, 2 (01) :73-120

[7] The $25,000,000,000 eigenvector: The linear algebra behind google [J].

Bryan, Kurt ;

Leise, Tanya .

SIAM REVIEW, 2006, 48 (03) :569-581

[8] REDUCING A MATRIX TO HESSENBERG FORM [J].

BUSINGER, PA .

MATHEMATICS OF COMPUTATION, 1969, 23 (108) :819-&

[9] Google PageRanking problem: The model and the analysis [J].

Cicone, Antonio ;

Serra-Capizzano, Stefano .

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2010, 234 (11) :3140-3169

[10] On the Use of Two QMR Algorithms for Solving Singular Systems and Applications in Markov Chain Modeling [J].

Freund, Roland W. ;

Hochbruck, Marlis .

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, 1994, 1 (04) :403-420

← 1 2 3 4 5 6 →