Strongly connected components based efficient computation of page rank

• Published in: Frontiers of Computer Science 2018-12, Vol.12 (6), p.1208-1219
• Main Authors: YANG, Hongguo, SHEN, Derong, KOU, Yue, NIE, Tiezhen, YU, Ge
• Format: Article
• Language: English
• Subjects: Algorithms; Computational efficiency; Computer Science; Efficiency; Graph theory; I/Os; page rank; power method; Research Article; strongly connected component
• ISSN: 2095-2228; 2095-2236
• DOI: 10.1007/s11704-016-6168-0

In this paper, an efficient page rank (PR) exact algorithm is proposed, which can improve the computation efficiency without sacrificing results accuracy. The existing exact algorithms are generally based on the original power method (PM). In order to reduce the number of I/Os required to improve efficiency, they partition the big graph into multiple smaller ones that can be totally fitted in memory. The algorithmproposed in this paper can further reduce the required number of I/Os. Instead of partitioning the graph into the general subgraphs, our algorithm partitions graph into a special kind of subgraphs: SCCs (strongly connected components), the nodes in which are reachable to each other. By exploiting the property of SCC, some theories are proposed, based on which the computation iterations can be constrained on these SCC subgraphs. Our algorithm can reduce lots of I/Os and save a large amount of computations, as well as keeping the results accuracy. In a word, our algorithm is more efficient among the existing exact algorithms. The experiments demonstrate that the algorithms proposed in this paper can make an obvious efficiency improvement and can attain high accurate results.