报告题目：Two Accelerated Non-backtracking PageRank Algorithms for Large-scale Networks

报 告 人：吴钢 教授 （中国矿业大学）

报告时间：2025年4月20日（星期日） 16:00-17:00

报告地点：数学科学学院114      

校内联系人： 杜磊 副教授       联系方式：84708351-8606

报告摘要：Non-backtracking PageRank is a variation of Google’s PageRank, which is based on non-backtracking random walk. However, if the number of dangling nodes of a graph is large, the non-backtracking PageRank algorithm may suffer from huge memory requirements and heavy computational costs. Thus, the non-backtracking PageRank algorithm is only applicable to small-scale or medium-sized graphs with few dangling nodes. In this work, we first consider how to compute the non-backtracking PageRank vector efficiently by using the Jacobi iteration, and then propose two strategies to speed up the computation of non-backtracking PageRank, in which we add some edges to a graph in a randomized and a fixed way, respectively. The computational issues are discussed in detail. The advantages of the proposed algorithms are two-fold. First, the sizes of the matrix computation problems are much smaller than that of the original one. Second, there is no kronecker product in the involved non-backtracking edge matrices, and the structures of the non-backtracking PageRank problems are greatly simplified. Comprehensive numerical experiments are performed on some real-world network matrices, which show that the solutions obtained from the two proposed algorithms and that from the original non-backtracking PageRank algorithm are highly correlated, while the two proposed algorithms can be tens or even hundreds times faster than their original counterpart.

报告人简介：吴钢，博士、中国矿业大学数学学院教授、博士生导师，江苏省“333工程”中青年科学技术带头人，江苏省“青蓝工程”中青年学术带头人，现任江苏省计算数学学会副理事长。主要研究方向：大规模科学与工程计算、数值代数、机器学习与数据挖掘等。先后主持国家自然科学基金项目、江苏省省自然科学基金项目多项，在国际知名期刊SIAM Journal on Numerical Analysis, SIAM Journal on Matrix Analysis and Applications, SIAM Journal on Scientific Computing, IMA Journal of Numerical Analysis, Pattern Recognition, Machine Learning等发表学术论文多篇。