An efficient elimination strategy for solving PageRank problems

Zhao-Li Shen, Ting-Zhu Huang, Bruno Carpentieri, Xian-Ming Gu and Chun Wen

Applied Mathematics and Computation, 2017, vol. 298, issue C, 111-122

Abstract: In Web link structures, similar link distributions often occur, especially for pages from same hosts. For PageRank problems, similar in-link distributions of pages result in similar row patterns of the transition matrix. We demonstrate that common row patterns in the transition matrix determine identical sub-rows. Thus the identical sub-rows with a large proportion of nonzeros can be eliminated to decrease the density of PageRank problems. We propose an elimination strategy that exploits such identical sub-rows and generates an elimination operator for transferring the problem to an equivalent but more sparse problem. Numerical experiments are reported to illustrate the effectiveness of this strategy for decreasing the computational cost of solving PageRank problems.

Keywords: PageRank; Elimination strategy; Row patterns; Sparsity; Spectral distribution; Iterative methods (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300316306385
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:298:y:2017:i:c:p:111-122

DOI: 10.1016/j.amc.2016.10.031

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().