An efficient elimination strategy for solving PageRank problems

详细信息    查看全文

• 作者：Zhao-Li Shen^a ; ^b ; ^{szlxiaoyao@163.com} ; Ting-Zhu Huang ; ^a ; ^{tingzhuhuang@126.com} ; Bruno Carpentieri^c ; ^{bcarpentieri@gmail.com} ; Xian-Ming Gu^a ; ^b ; ^{guxianming@live.cn} ; Chun Wen^a ; ^{wchun17@163.com}
• 关键词：PageRank ; Elimination strategy ; Row patterns ; Sparsity ; Spectral distribution ; Iterative methods
• 刊名：Applied Mathematics and Computation
• 出版年：2017
• 出版时间：1 April 2017
• 年：2017
• 卷：298
• 期：Complete
• 页码：111-122
• 全文大小：2583 K
• 卷排序：298

文摘

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.