TY  - JOUR
T1  - Fast Personalized PageRank Computation on Very Large Graphs
AU  - Park, Sungchan 
AU  - Kim, Youna 
AU  - Lee, Sang-goo 
JO  - Journal of KIISE, JOK
PY  - 2022
DA  - 2022/1/14
DO  - 10.5626/JOK.2022.49.10.859
KW  - graph analysis
KW  - PageRank
KW  - personalized PageRank
KW  - random walk
KW  - power iteration
KW  - optimization
KW  - algorithm
AB  - Computation of Personalized PageRank (PPR) in graphs is an important function that is widely utilized in myriad application domains such as search, recommendation, and knowledge discovery. As the computation of PPR is an expensive process, a good number of innovative and efficient algorithms for computing PPR have been developed. However, efficient computation of PPR within very large graphs with over millions of nodes is still an open problem. Moreover, previously proposed algorithms cannot handle updates efficiently, thereby severely limiting their capability of handling dynamic graphs. In this paper, we present a fast converging algorithm that guarantees high and controlled precision. We attempted to improve the convergence rate of the traditional Power Iteration approximation methods and fully exact methods. The results revealed that the proposed algorithm is at least 20 times faster than the Power Iteration and outperforms other state-of-the-art algorithms in terms of computation time.