Euler-Richardson method preconditioned by weakly stochastic matrix algebras: a potential contribution to Pagerank computation

Stefano Cipolla, Carmine Di Fiore, Francesco Tudisco

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Let S be a column stochastic matrix with at least one full row. Then S describes a Pagerank-like random walk since the computation of the Perron vector x of S can be tackled by solving a suitable M-matrix linear system Mx = y, where M = I − τ A, A is a column stochastic matrix and τ is a positive coefficient smaller than one. The Pagerank centrality index on graphs is a relevant example where these two formulations appear. Previous investigations have shown that the Euler- Richardson (ER) method can be considered in order to approach the Pagerank computation problem by means of preconditioning strategies. In this work, it is observed indeed that the classical power method can be embedded into the ER scheme, through a suitable simple preconditioner. Therefore, a new preconditioner is proposed based on fast Householder transformations and the concept of low complexity weakly stochastic algebras, which gives rise to an effective alternative to the power method for large-scale sparse problems. Detailed mathematical reasonings for this choice are given and the convergence properties discussed. Numerical tests performed on real-world datasets are presented, showing the advantages given by the use of the proposed Householder-Richardson method.
LanguageEnglish
Article number20
Number of pages19
JournalThe Electronic Journal of Linear Algebra
Volume32
DOIs
Publication statusPublished - 1 Aug 2017

Fingerprint

Stochastic Matrix
PageRank
Matrix Algebra
Euler
Power Method
Preconditioner
Perron Vector
Householder Transformation
Mathematical reasoning
Centrality
M-matrix
Preconditioning
Convergence Properties
Low Complexity
Random walk
Linear Systems
Algebra
Formulation
Alternatives
Coefficient

Keywords

  • matrix algebras
  • preconditioning
  • nonnegative matrices
  • Pagerank

Cite this

@article{aa011b57772e4145985b7deb9f03e207,
title = "Euler-Richardson method preconditioned by weakly stochastic matrix algebras: a potential contribution to Pagerank computation",
abstract = "Let S be a column stochastic matrix with at least one full row. Then S describes a Pagerank-like random walk since the computation of the Perron vector x of S can be tackled by solving a suitable M-matrix linear system Mx = y, where M = I − τ A, A is a column stochastic matrix and τ is a positive coefficient smaller than one. The Pagerank centrality index on graphs is a relevant example where these two formulations appear. Previous investigations have shown that the Euler- Richardson (ER) method can be considered in order to approach the Pagerank computation problem by means of preconditioning strategies. In this work, it is observed indeed that the classical power method can be embedded into the ER scheme, through a suitable simple preconditioner. Therefore, a new preconditioner is proposed based on fast Householder transformations and the concept of low complexity weakly stochastic algebras, which gives rise to an effective alternative to the power method for large-scale sparse problems. Detailed mathematical reasonings for this choice are given and the convergence properties discussed. Numerical tests performed on real-world datasets are presented, showing the advantages given by the use of the proposed Householder-Richardson method.",
keywords = "matrix algebras, preconditioning, nonnegative matrices, Pagerank",
author = "Stefano Cipolla and {Di Fiore}, Carmine and Francesco Tudisco",
year = "2017",
month = "8",
day = "1",
doi = "10.13001/1081-3810.3343",
language = "English",
volume = "32",
journal = "The Electronic Journal of Linear Algebra",
issn = "1081-3810",

}

Euler-Richardson method preconditioned by weakly stochastic matrix algebras : a potential contribution to Pagerank computation. / Cipolla, Stefano; Di Fiore, Carmine; Tudisco, Francesco.

In: The Electronic Journal of Linear Algebra, Vol. 32, 20, 01.08.2017.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Euler-Richardson method preconditioned by weakly stochastic matrix algebras

T2 - The Electronic Journal of Linear Algebra

AU - Cipolla, Stefano

AU - Di Fiore, Carmine

AU - Tudisco, Francesco

PY - 2017/8/1

Y1 - 2017/8/1

N2 - Let S be a column stochastic matrix with at least one full row. Then S describes a Pagerank-like random walk since the computation of the Perron vector x of S can be tackled by solving a suitable M-matrix linear system Mx = y, where M = I − τ A, A is a column stochastic matrix and τ is a positive coefficient smaller than one. The Pagerank centrality index on graphs is a relevant example where these two formulations appear. Previous investigations have shown that the Euler- Richardson (ER) method can be considered in order to approach the Pagerank computation problem by means of preconditioning strategies. In this work, it is observed indeed that the classical power method can be embedded into the ER scheme, through a suitable simple preconditioner. Therefore, a new preconditioner is proposed based on fast Householder transformations and the concept of low complexity weakly stochastic algebras, which gives rise to an effective alternative to the power method for large-scale sparse problems. Detailed mathematical reasonings for this choice are given and the convergence properties discussed. Numerical tests performed on real-world datasets are presented, showing the advantages given by the use of the proposed Householder-Richardson method.

AB - Let S be a column stochastic matrix with at least one full row. Then S describes a Pagerank-like random walk since the computation of the Perron vector x of S can be tackled by solving a suitable M-matrix linear system Mx = y, where M = I − τ A, A is a column stochastic matrix and τ is a positive coefficient smaller than one. The Pagerank centrality index on graphs is a relevant example where these two formulations appear. Previous investigations have shown that the Euler- Richardson (ER) method can be considered in order to approach the Pagerank computation problem by means of preconditioning strategies. In this work, it is observed indeed that the classical power method can be embedded into the ER scheme, through a suitable simple preconditioner. Therefore, a new preconditioner is proposed based on fast Householder transformations and the concept of low complexity weakly stochastic algebras, which gives rise to an effective alternative to the power method for large-scale sparse problems. Detailed mathematical reasonings for this choice are given and the convergence properties discussed. Numerical tests performed on real-world datasets are presented, showing the advantages given by the use of the proposed Householder-Richardson method.

KW - matrix algebras

KW - preconditioning

KW - nonnegative matrices

KW - Pagerank

U2 - 10.13001/1081-3810.3343

DO - 10.13001/1081-3810.3343

M3 - Article

VL - 32

JO - The Electronic Journal of Linear Algebra

JF - The Electronic Journal of Linear Algebra

SN - 1081-3810

M1 - 20

ER -