mapreducePageRank算法.doc

Mapreduce 程序设计报告姓名: 学号: 题目: Wiki 网页 PageRank 算法 1、实验环境联想 pc机虚拟机: VM 操作系统: Centos Hadoop 版本: hadoop Jdk 版本: jdk-7u25 Eclipse 版本: eclipse-SDK--linux-gtk-x86_64 2 、实验设计及源程序 实验说明 PageRank 是 Google 的专有算法,用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。 PageRank 实现了将链接价值概念作为排名因素。 PageRank 是一种由搜索引擎根据网页之间相互的超链接计算的网页排名技术,是 Googl e 用于用来标识网页的等级或重要性的一种方法。其级别从 1到 10 级, PR 值越高说明该网页越受欢迎、越重要。本次程序根据各网页之间的超链接关系和初始 PR 值,最终得到各网页的 PR 值,并按 PR 值排序。 PR 值高的网页说明有许多优质网页链接过来。每个网页的 PR 值可由公式 得到。() ( ) 1 ( ) ( ) ( ) pj M pi d PR pj PR pi d N L pj ??? ??其中, pj 为链接到网页 i 的所有网页。 d 表示阻尼因子,通常设为 。公式的前半部分表示一个上网者从一个随机网页开始浏览, 随机浏览模型更符合用户的行为, 一定程度上解决了 rank sink 的问题并且保证 PageRank 存在唯一值。公式的后半部分即表示由其他网页链接到网页 i的 PR 值。 实验设计本实验由3个 mapreduc e 程序完成, 分别为 GraphBuilder , PageRankIter , PageRankViewer , PageRankDriver 。 GraphBuilder GraphBuilder 主要用来分析原始数据,建立各个网页之间的链接关系。 GraphBuilderMap 这个类实现的 map 方法是逐行分析原始数据, 输出<URL,(PR_init,link_list)> , 其中网页的 URL 作为 key , PageRank 初始值(PR_init) 和网页的出度列表一起作为 value ,以字符串表示 value ,用特定的符号,如”:”将两者分开。 static class GraphBuilder_Mapper extends Mapper<LongWritable,Text,Text,Text> { private Text url = new Text(); private Text url_list = new Text(); public void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException { String vals[] = ().split("\\s+"); (vals[0]); (