Chapter9—厦门大学—林子雨—大数据的技术原理与应用—第9章节—图计算.pptVIP

在Pregel计算模型中，图中的每个顶点会对应一个计算单元，每个计算单元包含三个成员变量： 顶点值（Vertex value）：顶点对应的PR值 出射边（Out edge）：只需要表示一条边，可以不取值 消息（Message）：传递的消息，因为需要将本顶点对其它顶点的PR贡献值，传递给目标顶点 每个计算单元包含一个成员函数Compute()，该函数定义了顶点上的运算，包括该顶点的PR值计算，以及从该顶点发送消息到其链出顶点 9.7.2 PageRank算法在Pregel中的实现 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 9.7.2 PageRank算法在Pregel中的实现 class PageRankVertex: public Vertexdouble, void, double { public: virtual void Compute(MessageIterator* msgs) { if (superstep() = 1) { double sum = 0; for (;!msgs-Done(); msgs-Next()) sum += msgs-Value(); *MutableValue() = 0.15 / NumVertices() + 0.85 * sum; } if (superstep() 30) { const int64 n = GetOutEdgeIterator().size(); SendMessageToAllNeighbors(GetValue()/ n); } else { VoteToHalt(); } } }; Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 9.7.2 PageRank算法在Pregel中的实现 PageRankVertex继承自Vertex类，顶点值类型是double，用来保存PageRank中间值，消息类型也是double，用来传输PageRank值，边的value类型是void，因为不需要存储任何信息 这里假设在第0个超步时，图中各顶点值被初始化为1/NumVertices()，其中，NumVertices()表示顶点数目 在前30个超步中，每个顶点都会沿着它的出射边，发送它的PageRank值除以出射边数目以后的结果值。从第1个超步开始，每个顶点会将到达的消息中的值加到sum值中，同时将它的PageRank值设为0.15/NumVertices()+0.85*sum 到了第30个超步后，就没有需要发送的消息了，同时所有的顶点停止计算，得到最终结果 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 《大数据技术原理与应用》 厦门大学计算机科学系 林子雨 ziyulin@ 厦门大学计算机科学系 2015年版 林子雨 厦门大学计算机科学系 E-mail: ziyulin@ 主页：/linziyu 第九章 图计算 （PPT版本号：2015年6月第1.0版） 《大数据技术原理与应用》 /post/bigdata 温馨提示：编辑幻灯片母版，可以修改每页PPT的厦大校徽和底部文字 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 提纲 9.1 图计算简介 9.2 Pregel简介 9.3 Pregel图计算模型 9.4 Pregel的C++ API 9.5 Pregel的体系结构 9.6 Pregel的应用实例 9.7 Pregel和MapReduce实现PageRank算法的对比 欢迎访问《大数据技术原理与应用》教材官方网站：