Two Parallel PageRank Algorithms via Improving Forward Push

Abstract PageRank, originally designed to rank web pages, has been widely applied in various fields. With the increasing scale of graphs, accelerating PageRank computation has become an urgent need, and designing parallel algorithms is a feasible solution. In this paper, we propose two parallel PageRank algorithms, IFP1 and IFP2, which are improvements upon the state-of-the-art Personalized PageRank algorithm, Forward Push. Theoretical analysis indicates that IFP1 can take advantage of the DAG structure of a graph, where dangling vertices can improve convergence rates and unreferenced vertices can decrease computation amount. IFP2 further improves upon IFP1 by pushing mass to dangling vertices only once but rather many times, decreasing computation amount even further. Experiments on six datasets illustrate that both IFP1 and IFP2 outperform the Power method, with IFP2 reaching up to 49 times faster than Power method with 38 parallelism.