A Survey on Personalized PageRank Computation Algorithms

Information

Title A Survey on Personalized PageRank Computation Algorithms
Authors
Sungchan Park, Wonseok Lee, Byeongseo Choe, Sang-goo Lee
Year 2019 / 11
Keywords Personalized PageRank, Graph Data Mining, Graph Analysis
Acknowledgement KOCCA
Publication Type International Journal
Publication IEEE Access, Volume 7, pp. 163049-163062
Link url doi

Abstract

Personalized PageRank (PPR) is an important variation of PageRank, which is a widely applied popularity measure for Web search. Unlike the original PageRank, PPR is a node proximity measure that represents the degree of closeness among multiple nodes within a graph. It is also widely applied to diverse domains, such as information retrieval, recommendations, and knowledge discovery, due to its theoretical simplicity and flexibility. However, computing PPR in large graphs using naïve algorithms such as iterative matrix multiplication and matrix inversion is not fast enough for many of these applications. Therefore, devising efficient PPR algorithms has been one of the most important subjects in large-scale graph processing. In this paper, we review the algorithms for efficient PPR computations, organizing them into five categories based on their core ideas. Along with detailed explanations including recent advances and their applications, we provide a multifaceted comparison of the algorithms.