基于强连通分量的个性化的网页排名高效算法

Strongly Connected Components Based Efficient PPR Algorithms

个性化的网页排名(PPR)是一种常用的图结点排名方法.随着图的规模变得越来越大,如何快速地计算出PPR逐渐成为大家研究的关注热点.该文的最终目的即是为了提高PPR的计算效率.现有的各种优化算法可大体分为分布式算法和串行算法,其主要思路均是通过将大图上的计算分割到多个小子图上进行计算,但不同分块间的数据通信量往往很大而且通信次数频繁.该文提出的基于强连通分量的算法可有效解决此类问题.其主要计算过程为,首先快速将大量与计算无关的结点和边剪切掉,其次通过某种策略将在大图上的计算转化到多个强连通分量子图上计算,使得各分量子图之间的数据传递只需一次即可完成.该文基于强连通分量算法,不仅减少了分布式算法子图间的通信量,而且降低了串行算法的磁盘读写I/O频率,同时还保证了算法的准确度几乎不受损失.实验结果表明该文提出的算法可显著提高PPR的计算效率.

Personalized PageRank （PPR） is usually employed to rank the nodes of graphs. Due to the ever increasing volume of graph, how to improve the efficiency of PPR computations has become a research focus. Thus the purpose of this paper is to improve the efficiency of PPR computations. The existing optimization algorithms can he generally classified into two categories： distributed algorithm and serial algorithm, and the general approach of them is mainly through partitioning the computations on the big graph into computations on multiple smaller sub-graphs, but the communication between sub-graphs usually involve a large amount of data and is of a high frequency. The SCC （Strongly Connected Component） based algorithms proposed in this paper can resolve these problems effectively. The main computation steps of them is： first identify and remove volumes of unrelated nodes and edges quickly before PPR computation, then transform the PPR computations on big graph into that on multiple SCC sub-graphs, which make the multiple data communications between sub-graphs turn into one time communication. The SCC based algorithm in this paper can reduce not only the communication amount between SCCs but also the storage I/O frequency, while keeping high algorithm accuracy. The experiments demonstrate that the algorithms proposed in this paper can make obvious improvements for the PPR computation efficiency.