Exploiting Common Structures Across Multiple Network Propagation Schemes

Abstract

PageRank is arguably the most popular graph-node ranking algorithm which has been used to analyze large networks. This paper presents how to utilize common structures across multiple damping schemes in PageRank algorithm and its variants to improve computation efficiency. One contribution we have made is to make use of Krylov subspaces to fast approximate PageRank of the same graph, same personalized distribution vector across different damping factors. In the first run we compute an invariant subspace, which is the major time cost of our algorithm. The original network connection matrix is represented in the invariant subspace by a small matrix.Afterward, for each different damping factor only the small matrix is involved, followed by a single matrix-vector multiplication. Another contribution is to re-index graph nodes, based on graph spectral method to improve data locality, and accelerate sparse matrix-vector multiplication. We applied the new method to large real-world network graphs and make comparisons between existing iterative methods and our method. Our algorithm has substantial lower cost in amortized time when multiple damping factors are used for network analysis.