Ch.8. 基于MapReduce的图算法 MapReduce海量数据并行处理 南京大学计算机科学与技术系 主讲人：黄宜华，刘长辉 2011年春季学期 鸣谢：本课程得到Google公司(北京） 中国大学合作部精品课程计划资助

Ch.8. 基于MapReduce的图算法 1.图的表示 2.PageRank 3.最短路径 4.广度优先遍历 5. 实验4：Wiki百科网页数据PageRank

图问题与MapReduce 一些图问题： 关键问题： 最短路径 最小生成树 广度优先搜索 PageRank

图表示方法 G = (V, E) 两种常见的表示方法 邻接矩阵 邻接表

邻接矩阵 用一个 n x n 的矩阵 M 来表示图： n = |V| Mij = 1 表示一条i到j的边 2 1 3 4

邻接矩阵 优点: 便于数学操作 遍历一行可得到出度信息，遍历一列可以得到入度信息 缺点: 对于稀疏矩阵浪费内存

邻接表 只保存邻接矩阵中不为零的节点 1 2 3 4 1: 2, 4 2: 1, 3, 4 3: 1 4: 1, 3

邻接表 优点: 表示更加紧凑 容易得到出度信息 缺点: 不方便得出入度信息

PageRank内容概述 什么是PageRank PageRank的简化模型 PageRank的随机浏览模型 PageRank的MapReduce实现

什么是PageRank PageRank PageRank是一种由搜索引擎根据网页之间相互的超链 接计算的网页排名技术。 PageRank是Google用于用来标识网页的等级或重要性 的一种方法。其级别从1到10级，PR值越高说明该网 页越受欢迎（越重要）。

PageRank的基本设计思想和设计原则 从许多优质的网 页链接过来的网 页，必定还是优 质网页。一个网 页要想拥有较高 的PR值的条件： 有很多网页链接 到它； 有高质量的网页 链接到它。

PageRank的简化模型 可以把互联网上的各个网页之间的链接关系看成一个有向图。 对于任意网页Pi，它的PageRank值可表示为： 其中Bi为所有链接到网页i的网页集 合， Lj为网页j的对外链接数（出度）。

简化模型的矩阵表示

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

Rank leak PR(A) PR(B) PR(C) PR(D) 初始 0.25 一次迭代 0.125 二次迭代 三次迭代 … n次迭代 Rank leak：一个独立的网页如果没有外出的链接就产生等级泄漏 解决办法： 1.将无出度的节点递归的从图中去掉，待其他节点计算完毕后再添加。 2.对无出度的节点添加一条边，指向那些指向它的顶点。

Rank sink Rank sink：整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Rank sink。 PR(A) PR(B) PR(C) PR(D) 初始 0.25 一次迭代 0.375 二次迭代 三次迭代 四次迭代 五次迭代 … Rank sink：整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Rank sink。 从而引入随机浏览模型。

PageRank的随机浏览模型 假定一个上网者从一个随机的网页开始浏览 上网者不断点击当前网页的链接开始下一次浏览。 但是，上网者最终厌倦了，开始了一个随机的网页。 随机上网者访问一个新网页的概率就等于这个网页 的PageRank值。因此这个模型更加接近于用户的行 为。

随机浏览模型的图表示 设定任意两个顶点之间都有直接通路， 在每个顶点处以概率d按原来蓝色方向转移，以概率1-d按红色方向转移。

随机浏览模型的矩阵表示 回顾简单模型的矩阵表示： 随机浏览模型的矩阵表示： R = HR 随机浏览模型的矩阵表示： 令：H’ = d*H + (1-d)*[1/N]N×N 则： R= H’ R 其中R为列向量，代表PageRank值；H’代表转移矩阵；d代表阻尼因子，通常设为 0.85。 由于等式R=HR满足马尔可夫链的性质，如果马尔 可夫链收敛，则可R存在唯一解

马尔可夫链收敛定理

随机浏览模型的邻接表表示 由于网页数目巨大，网页之间的连接关系的邻接矩 阵是一个很大的稀疏矩阵。 采用邻接表来表示网页之间的连接关系。 随机浏览模型的PageRank公式： 通过迭代计算得到所有节点的PageRank值。

随机浏览模型 随机浏览模型的优点： 更加符合用户的行为 一定程度上解决了rank sink问题 保证PageRank存在唯一值。

用MapReduce实现PageRank Phase1: GraphBuilder 建立网页之间的超链接图 Phase2: PageRankIter 迭代计算各个网页的PageRank值 Phase3: RankViewer 按PageRank值从大到小输出

Phase1：GraphBuilder 原始数据集：维基百科各网页间的链接信息。文本文 件，共11.2G。每行包含一个网页名，及其所链接的 全部网页名。 GraphBuilder目标：分析原始数据，建立各个网页之间 的链接关系。 Map：逐行分析原始数据, 输出<URL ,(PR_init, link_list)> 其中网页的URL作为key, PageRank初始值（PR_init）和网页的出度 列表一起作为value,以字符串表示value，用特定的符号将二者分开。 Reduce: 输出<URL, (PR_init, link_list)> 该阶段的Reduce不需要做任何处理

Phase2：PageRankIter PageRankIer：迭代计算PR值，直到PR值收敛或迭代预定次数。 Map对上阶段的 <URL, (cur_rank, link_list)>产生两种<key, value> 对： 1 For each u in link_list, 输出 <u, cur_rank/|link_list|> 其中u代表当前URL所链接到网页ID，并作为key； Cur_rank为当前URL的PageRank值， |link_list|为当前URL的出度数量， , cur_rank/|link_list|作为value。 2 同时在迭代过程中，传递每个网页的链接信息<URL, link_list> 在迭代过程中，必须保留网页的局部链出信息，以维护图的结构。

Phase2：PageRankIter Reduce 对 Map输出的<URL, url_list> 和多个 <URL, val>做如下 处理： 其中<URL, url_list> 为当前URL的链出信息； <URL, val>为当前URL的链入网页对其贡献的PageRank值 计算所有val的和，并乘上d，在加上常数(1-d) /N得到new_rank。 输出 (URL, (new_rank, url_list))。 迭代计算公式： PR(A) = (1-d) /N+ d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

PageRank in MapReduce Map Reduce n1 [n2, n4] n2 [n3, n5] n3 [n4]

Phase2：PageRankIter PageRankIter伪代码

Phase3：Rankviewer PageRankViewer：将最终结果排序输出。 PageRankViewer从最后一次迭代的结果读出文件，并将文件名和 其PR值读出，并以PR值为key网页名为value，并且以PR值从大到 小的顺序输出。 排序过程中可以采用框架自身的排序处理，重载key的比较 函数，使其经过shuffle和sort后反序（从大到小）输出 public static class DecFloatWritable extends FloatWritable { … @Override public int compareTo(Object o) { return -super.compareTo(o); }

PageRank迭代终止条件 可选的终止条件： 各网页的PageRank值不再改变； 各网页的PageRank值排序不再变化； 迭代至固定次数；

多趟MapReduce的处理 public class PageRankDriver { private static int times = 10; public static void main(String args[]) throws Exception String[] forGB = {"", args[1]+"/Data0"}; forGB[0] = args[0]; GraphBuilder.main(forGB); String[] forItr = {"Data","Data"}; for (int i=0; i<times; i++) { forItr[0] = args[1]+"/Data"+(i); forItr[1] = args[1]+"/Data"+(i+1); PageRankIter.main(forItr); } String[] forRV = {args[1]+"/Data"+times, args[1]+"/FinalRank"}; PageRankViewer.main(forRV); 也可以使用org.apache.hadoop.util.ProgramDriver

单源最短路径 问题: 在图中寻找一个起始点到一个或多个目标点 之间的最短路径 串行算法： Dijkstra算法 最短路径通常指最小的权重或最少代价。 串行算法： Dijkstra算法 MapReduce：并行广度优先 (BFS)

Dijkstra最短路径算法   1 10 2 3 9 4 6 5 7   2 Example from CLR

Dijkstra最短路径算法 10  1 10 2 3 9 4 6 5 7 5  2 Example from CLR

Dijkstra最短路径算法 8 14 1 10 2 3 9 4 6 5 7 5 7 2 Example from CLR

Dijkstra最短路径算法 8 13 1 10 2 3 9 4 6 5 7 5 7 2 Example from CLR

Dijkstra最短路径算法 8 9 1 1 10 2 3 9 4 6 5 7 5 7 2 Example from CLR

Dijkstra最短路径算法 8 9 1 10 2 3 9 4 6 5 7 5 7 2 Example from CLR

Dijkstra最短路径算法 Dijkstra最短路径基于维持一个全局的优先队列 每次迭代都是从队列中找出距离最小的点，并更新它可到达的点。 存在问题：在集群分布处理环境下难以维持全局的优先队列，因而基于单机的Dijkstra算法无法实现MapReduce并行化 解决方法：可以基于并行的广度优先遍历来解决最短路径问题。

广度优先遍历的并行化 1.同一层之间的节点可并行执行； 2.每一趟MapReduce过程处理一层； 4.迭代终止：没有距离为无穷大的顶点。

广度优先遍历的MapReduce实现

最短路径的并行算法 并行的最短路径算法 基于广度优先遍历 与广度优先遍历不同： 终止条件 广度优先：所有节点都 更新过一遍； 最短路径：所有节点的 距离不再变化；

基于MapReduce的图算法总结 通常采用邻接表来表示图 通常将一个完整的图结构，分解成若干个局部的子 结构，对每个子结构进行并行处理。 在map阶段对邻接点产生<key,value>对，经过Shuffle 和sort后，在reduce阶段更新节点信息。 图算法通常是一个迭代过程，上一步的输出作为下 一步的输入，由额外的“driver”控制。

5. 实验4：Wiki网页PageRank算法 实验内容与要求 1. 在Eclipse环境下编写实现Wiki网页数据集的PageRank算法，实验数 据从FTP上下载 2. 在集群上运行程序，对Wiki网页数据集进行处理 3. 实验结果提交：要求书写一个实验报告，其中包括： 实验设计说明，包括主要设计思路、算法设计、程序和各个类的设计说明 程序运行和实验结果说明和分析,包括前30个最高Rank的网页信息输出列表 性能、扩展性等方面存在的不足和可能的改进之处 源程序 ，执行程序 运行结果文件 实验报告文件命名规则：MPLab4-学号-姓名.doc 实验报告提交至：FTP：114.212.209.146 用户名：hadoop 口令：hadoop 实验完成时间：5月18日前完成并提交报告

Reference 1. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Sergey Brin and Lawrence Page. 2. Ecient Computation of PageRank . Taher H. Haveliwala. 3. The PageRank Citation Ranking:Bring Order to the Web 4. Data-Intensive Text Processing with MapReduce Jimmy Lin and Chris Dyer

谢谢！