针对传统PageRank算法难以高效处理Web图数据网页排序问题,文章在不牺牲准确度的前提下,提出一种在MapReduce平台上基于改进PageRank的加速算法:topK-Rank.为识别出排名为前k的网页,通过在迭代过程中裁剪掉不必要的节点及边的形式,动态构建子图,由子图迭代计算出PageRank值的上下限.理论分析和实验结果表明:该算法不仅可以保证结果的准确性,还可以更快地找到用户所需网页数.%The traditional PageRank algorithm can not efficiently perform large data Webpage scheduling problem.This paper proposes an accelerated algorithm named topK-Rank,which is based on PageRank on the MapReduce platform.It can find top k nodes efficiently for a given graph without sacrificing accuracy.In order to identify top k nodes,topK-Rank algorithm prunes unnecessary nodes and edges in each iteration to dynamically construct subgraphs,and iteratively estimates lower/upper bounds of PageRank scores through subgraphs.Theoretical analysis shows that this method guarantees result exactness.Experiments show that topK-Rank algorithm can find k nodes much faster than the existing approaches.
展开▼
