An efficient elimination strategy for solving PageRank problems
Autor: | Zhao-Li Shen, Chun Wen, Ting-Zhu Huang, Xian-Ming Gu, Bruno Carpentieri |
---|---|
Přispěvatelé: | Computational and Numerical Mathematics |
Jazyk: | angličtina |
Rok vydání: | 2017 |
Předmět: |
PageRank
Mathematical optimization Iterative method Iterative methods Computer Science::Information Retrieval Applied Mathematics Stochastic matrix 010103 numerical & computational mathematics Link (geometry) Row patterns Hyperlink Elimination strategy 01 natural sciences Spectral distribution law.invention WEB 010101 applied mathematics Computational Mathematics Operator (computer programming) law ALGORITHM 0101 mathematics Sparsity Mathematics |
Zdroj: | Applied Mathematics and Computation, 298, 111-122. ELSEVIER SCIENCE INC |
ISSN: | 0096-3003 |
Popis: | 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. (C) 2016 Elsevier Inc. All rights reserved. |
Databáze: | OpenAIRE |
Externí odkaz: |