Hadoop学习系列之PageRank

kidys

　　
　　昨晚上不想做其他的事，突然想起来好久都没更新博客了，shell也差不多学完了，只不过学习的时候都是只带着书出去了，改天总结总结。Hadoop么，黄宜华老师讲完了，自己也马马虎虎快学完了，也是没总结，那今天就写下前段时间写的一个关于英文Wiki的PageRank代码吧。
PageRank的ABC
什么是PageRank
　　PageRank是一种在搜索引擎中根据网页之间相互的链接关系计算网页排名的技术。
　　PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从1到10级，PR值越高说明该网页越受欢迎（越重要）。
　　
PageRank的基本设计思想和原则
　　被许多优质网页所链接的网页，多半也是优质网页。
　　一个网页要想拥有较高的PR值的条件：

• 有很多网页链接到它；
  
• 有高质量的网页链接到它
  

PageRank的简化模型
　　可以把互联网上的各个网页之间的链接关系看成一个有向图。
　　对于任意网页Pi，它的PageRank值可表示为：
　　

其中Bi为所有链接到网页i的网页集合，Lj为网页j的对外链接

简化模型面临的缺陷

  实际的网络超链接环境没有这么理想化，PageRank会面临两个问题：

• Rank leak：就是有的网页没有链出网页，使用上面的公式时，循环几次后所有的PageRank值都变为0
  
• Rank sink：整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Rank sink，即经过若干次循环后不在环中的网页的PR值会变为0
  

　　解决简化模型的缺陷的解决办法——采用随机浏览模型：

—  假定一个上网者从一个随机的网页开始浏览

—  上网者不断点击当前网页的链接开始下一次浏览

—  但是，上网者最终厌倦了，开始了一个随机的网页

—  随机上网者用以上方式访问一个新网页的概率就等于这个网页的PageRank值

—  这种随机模型更加接近于用户的浏览行为

采用随机浏览模型后的PR值计算公式变为：

其中d为按照超链进行浏览的概率，1-d即为用户随机跳转一个新网页的概率，显然跳转到每个网页的概率为(1-d)/N，N为所有网页的数目。

依据上述公式，一般经过10次左右的计算，每一个网页可以得到一个稳定的PR值（数学证明使用马尔可夫链收敛定理，不太懂，有兴趣的同学可以关注下）

使用MapReduce实现PageRank
　　显然这样一个需要进行大量累加计算的工作是适合用MapReduce来做的，那么怎么做呢？分三个阶段完成这个事情：
　　—  Phase1: GraphBuilder
　　—  建立网页之间的超链接图
　　—  Phase2: PageRankIter
　　—  迭代计算各个网页的PageRank值
　　—  Phase3: RankViewer
　　—  按PageRank值从大到小输
　　
　　具体设计：
　　En_wiki中每行对应于一个页面，页面的标题包含在“&lttitle&gtName of thearticle&lt/title&gt”中，每个页面的链出标题在一对双中括号中（"[[Name of other article]]"），我们需要做的就是用PageRank算法给出每个页面的重要性，并按重要程度从高到低输出。首先要做的就是构建每个页面的链接关系图，这个工作我们GraphBuilder类来实现，给出的结构类似于图的邻接表表示方式；第二步需要做的工作就是用PageRank算法经过一定次数的迭代，得出最终每个页面的PRValue，具体算法在PageRankler类中实现；第三步需要将结果展现出来，并按“PRvalue           title”的格式降序输出，类PageRankViewer实现该功能；最后，需要组织整个算法，这是main函数完成的功能。
　　以下具体阐述每个类的具体实现：
1.           整体类视图

2.           GraphBuilder类
　　map中完成链接图的构造。首先需解决的问题就是如何提取出title及linktitle，我们使用正则表达式来完成："(?