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

发布时间：2018-03-27 06:47

本文选题：个性化的网页排名　切入点：分布式算法　出处：《计算机学报》2017年03期

【摘要】：个性化的网页排名(PPR)是一种常用的图结点排名方法.随着图的规模变得越来越大,如何快速地计算出PPR逐渐成为大家研究的关注热点.该文的最终目的即是为了提高PPR的计算效率.现有的各种优化算法可大体分为分布式算法和串行算法,其主要思路均是通过将大图上的计算分割到多个小子图上进行计算,但不同分块间的数据通信量往往很大而且通信次数频繁.该文提出的基于强连通分量的算法可有效解决此类问题.其主要计算过程为,首先快速将大量与计算无关的结点和边剪切掉,其次通过某种策略将在大图上的计算转化到多个强连通分量子图上计算,使得各分量子图之间的数据传递只需一次即可完成.该文基于强连通分量算法,不仅减少了分布式算法子图间的通信量,而且降低了串行算法的磁盘读写I/O频率,同时还保证了算法的准确度几乎不受损失.实验结果表明该文提出的算法可显著提高PPR的计算效率.
[Abstract]:Personalized Page ranking (PPRR) is a common method of ranking graph nodes. How to calculate PPR quickly has gradually become the focus of attention. The ultimate purpose of this paper is to improve the computational efficiency of PPR. The existing optimization algorithms can be divided into distributed algorithm and serial algorithm. The main idea is to divide the calculation on the large graph into several small graphs for calculation. However, the data traffic between different blocks is often very large and the communication times are frequent. The algorithm based on strongly connected components can effectively solve this kind of problems. The main calculation process is as follows:. Firstly, a large number of computationally independent nodes and edges are cut off quickly, and then the computation on a large graph is transformed into several strongly connected quantum graphs by some strategy. In this paper, based on the strong connected component algorithm, not only the communication between the subgraphs of the distributed algorithm is reduced, but also the I / O frequency of the serial algorithm is reduced. The experimental results show that the proposed algorithm can significantly improve the computational efficiency of PPR.
【作者单位】：东北大学计算机科学与工程学院;
【基金】：国家“九七三”重点基础研究发展规划项目基金(2012CB316201) 国家自然科学基金面上项目(61472070)资助~~
【分类号】：TP301.6

【相似文献】