An efficient elimination strategy for solving PageRank problems
MetadataShow full item record
SubjectPageRank; Elimination strategy; Row patterns; Sparsity; Spectral distribution Iterative methods
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. © 2016 Elsevier Inc.
Showing items related by title, author, creator and subject.
Shen ZL; Huang TZ; Carpentieri B; Wen C; Gu XM (2018)Recently, the adaptive algebraic aggregation multigrid method has been proposed for computing stationary distributions of Markov chains. This method updates aggregates on every iterative cycle to keep high accuracies of ...
Jaber M; Papapetrou P; Helmer S; Wood PT (Springer, 2014)We study the problem of detecting hierarchical ties in a social network by exploiting the interaction patterns between the actors (members) involved in the network. Motivated by earlier work using a rank-based approach, ...
Shen ZL; Huang TZ; Carpentieri B; Wen C; Gu XM; Tan XY (North-Holland, 2019)PageRank problem is the cornerstone of Google search engine and is usually stated as solving a huge linear system. Moreover, when the damping factor approaches 1, the spectrum properties of this system deteriorate rapidly ...