A preconditioning approach to the pagerank computation problem

Francesco Tudisco, Carmine Di Fiore

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler–Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ERU method, and we observe that ERU can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ERU superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.
LanguageEnglish
Pages2222-2246
Number of pages25
JournalLinear Algebra and its Applications
Volume435
Issue number9
Early online date14 May 2011
DOIs
Publication statusPublished - 30 Nov 2011

Fingerprint

PageRank
Preconditioning
Storage allocation (computer)
Euler
Graph in graph theory
Preconditioner
Algebra
Oriented Graph
Transition Matrix
Iterative Scheme
Spectral Properties
Convergence Rate
Costs
Rate of Convergence
Choose

Keywords

  • pagerank
  • iterative method
  • preconditioning
  • eigenvalues
  • clustering
  • fast discrete transforms

Cite this

Tudisco, Francesco ; Di Fiore, Carmine. / A preconditioning approach to the pagerank computation problem. In: Linear Algebra and its Applications. 2011 ; Vol. 435, No. 9. pp. 2222-2246.
@article{34879a028c91486f833bddc13e49677f,
title = "A preconditioning approach to the pagerank computation problem",
abstract = "Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler–Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ERU method, and we observe that ERU can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ERU superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.",
keywords = "pagerank, iterative method, preconditioning, eigenvalues, clustering, fast discrete transforms",
author = "Francesco Tudisco and {Di Fiore}, Carmine",
year = "2011",
month = "11",
day = "30",
doi = "10.1016/j.laa.2011.04.018",
language = "English",
volume = "435",
pages = "2222--2246",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
number = "9",

}

A preconditioning approach to the pagerank computation problem. / Tudisco, Francesco; Di Fiore, Carmine.

In: Linear Algebra and its Applications, Vol. 435, No. 9, 30.11.2011, p. 2222-2246.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A preconditioning approach to the pagerank computation problem

AU - Tudisco, Francesco

AU - Di Fiore, Carmine

PY - 2011/11/30

Y1 - 2011/11/30

N2 - Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler–Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ERU method, and we observe that ERU can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ERU superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.

AB - Some spectral properties of the transition matrix of an oriented graph indicate the preconditioning of Euler–Richardson (ER) iterative scheme as a good way to compute efficiently the vertexrank vector associated with such graph. We choose the preconditioner from an algebra U of matrices, thereby obtaining an ERU method, and we observe that ERU can outperform ER in terms of rate of convergence. The proposed preconditioner can be updated at a very low cost whenever the graph changes, as is the case when it represents a generic set of information. The particular U utilized requires a surplus of operations per step and memory allocations, which make ERU superior to ER for not too wide graphs. However, the observed high improvement in convergence rate obtained by preconditioning and the general theory developed, are a reason for investigating different choices of U, more efficient for huge graphs.

KW - pagerank

KW - iterative method

KW - preconditioning

KW - eigenvalues

KW - clustering

KW - fast discrete transforms

UR - http://www.sciencedirect.com/science/journal/00243795

U2 - 10.1016/j.laa.2011.04.018

DO - 10.1016/j.laa.2011.04.018

M3 - Article

VL - 435

SP - 2222

EP - 2246

JO - Linear Algebra and its Applications

T2 - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

IS - 9

ER -