Title: Two Accelerated Non-backtracking PageRank Algorithms for Large-scale Networks

Abstract: 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 proposetwo 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.

Speaker: Prof. Gang Wu, School of Mathematics, China University of Mining and Technology.

Date: 10:00–11:00 AM, May 25, 2025
Venue: Room 208, School of Mathematical Sciences

Organizer: School of Mathematical Science

Inviter：Bo Feng

Students and teachers are welcome!