Exploiting Common Structures Across Multiple Network Propagation Schemes
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.
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License.
Rights for Collection: Masters Theses
Works are deposited here by their authors, and represent their research and opinions, not that of Duke University. Some materials and descriptions may include offensive content. More info