子图估算PageRank网页排序算法研究  

Research of Subgraph Estimation Page Rank Algorithm for Web Page Rank

作　　者：李兰英[1] 周秋丽[1] 孔银[1] 董义明[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,黑龙江哈尔滨150080

出　　处：《哈尔滨理工大学学报》2017年第2期117-123,共7页Journal of Harbin University of Science and Technology

基　　金：黑龙江省教育厅科学技术研究项目(12531107)

摘　　要：针对传统PageRank算法难以高效处理Web图数据网页排序问题,文章在不牺牲准确度的前提下,提出一种在MapReduce平台上基于改进PageRank的加速算法:top K-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.

关 键 词：web图数据 网页排序 PAGERANK算法 MAPREDUCE 子图 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]