Chapter9-厦门大学-林子雨-大数据技术原理与应用-第九章-图计算44

1、厦门大学计算机科学系 2015年版第九章 图计算 （PPT版本号：2015年6月第1.0版） 大数据技术原理与应用/post/bigdata温馨提示：编辑幻灯片母版，可以修改每页PPT的厦大校徽和底部文字提纲9.1图计算简简介9.2Pregel简介9.3Pregel图计算模模型9.4Pregel的C+API9.5Pregel的体系结结构9.6Pregel的应用实实例9.7Pregel和MapReduce实现PageRank算法的对对比欢迎访问问大数据技技术原理理与应用用教材官方方网站：http:/dblab./post/bigdata本PPT是如下教教材的配配套讲义义：21世纪高等等教育计计算

2、机规规划教材材大数据技技术原理理与应用用概念、存存储、处处理、分分析与应应用（2015年6月第1版）厦门大学学 林子子雨编编著，人人民邮电电出版社社ISBN:978-7-115-39287-99.1图图计算算简介9.1.1传统图计计算解决决方案的的不足之之处9.1.2图计算通通用软件件9.1.1传传统图计计算解决决方案的的不足之之处很多传统统的图计计算算法法都存在在以下几几个典型型问题：（1）常常表表现出比比较差的的内存访访问局部部性；（2）针对单单个顶点点的处理理工作过过少；（3）计算过过程中伴伴随着并并行度的的改变。针对大型型图（比比如社交交网络和和网络图图）的计计算问题题，可能能的解决决

3、方案及及其不足足之处具具体如下下：为特定的的图应用用定制相相应的分分布式实实现：通通用性不不好基于现有有的分布布式计算算平台进进行图计计算：在在性能和和易用性性方面往往往无法法达到最最优使用单机机的图算算法库：在可以以解决的的问题的的规模方方面具有有很大的的局限性性使用已有有的并行行图计算算系统：对大规规模分布布式系统统非常重重要的一一些方面面（比如如容错），无法法提供较较好的支支持9.1.2图图计算通通用软件件一次BSP计算过程程包括一一系列全全局超步步（所谓谓的超步步就是计计算中的的一次迭迭代），每个超超步主要要包括三三个组件件：局部计算算：每个参参与的处处理器都都有自身身的计算算任务，它

4、们只只读取存存储在本本地内存存中的值值，不同同处理器器的计算算任务都都是异步步并且独独立的通讯：处理器器群相互互交换数数据，交交换的形形式是，由一方方发起推推送(put)和获取(get)操作栅栏同步步(BarrierSynchronization)：当一个个处理器器遇到“路障”（或栅栅栏），会等到到其他所所有处理理器完成成它们的的计算步步骤；每每一次同同步也是是一个超超步的完完成和下下一个超超步的开开始。图图9-1是一个超超步的垂垂直结构构图图91 一个个超步的的垂直结结构图9.2Pregel简介Pregel是一种基基于BSP模型实现现的并行行图处理理系统为了解决决大型图图的分布布式计算算问题

5、，Pregel搭建了一一套可扩扩展的、有容错错机制的的平台，该平台台提供了了一套非非常灵活活的API，可以描描述各种种各样的的图计算算Pregel作为分布布式图计计算的计计算框架架，主要要用于图图遍历、最短路路径、PageRank计算等等等9.3Pregel图计算算模型9.3.1有向图和和顶点9.3.2顶点之间间的消息息传递9.3.3Pregel的计算过过程9.3.4实例9.3.1有有向图和和顶点Pregel计算模型型以有向向图作为为输入，有向图图的每个个顶点都都有一个个String类型的顶顶点ID，每个顶顶点都有有一个可可修改的的用户自自定义值值与之关关联，每每条有向向边都和和其源顶顶点关联

6、联，并记记录了其其目标顶顶点ID，边上有有一个可可修改的的用户自自定义值值与之关关联在每个超超步S中，图中中的所有有顶点都都会并行行执行相相同的用用户自定定义函数数。每个个顶点可可以接收收前一个个超步(S-1)中发送给给它的消消息，修修改其自自身及其其出射边边的状态态，并发发送消息息给其他他顶点，甚至是是修改整整个图的的拓扑结结构。需需要指出出的是，在这种种计算模模式中，边并不不是核心心对象，在边上上面不会会运行相相应的计计算，只只有顶点点才会执执行用户户自定义义函数进进行相应应计算9.3.2顶顶点之间间的消息息传递图92 纯消消息传递递模型图图采用消息息传递模模型主要要基于以以下两个个原因：

7、（1）消息传传递具有有足够的的表达能能力，没没有必要要使用远远程读取取或共享享内存的的方式（2）有助于于提升系系统整体体性能9.3.3Pregel的的计算过过程图93一个简单单的状态态机图Pregel的计算过过程是由由一系列列被称为为“超步步”的迭迭代组成成的。在在每个超超步中，每个顶顶点上面面都会并并行执行行用户自自定义的的函数，该函数数描述了了一个顶顶点V在一个超超步S中需要执执行的操操作。该该函数可可以读取取前一个个超步(S-1)中其他顶顶点发送送给顶点点V的消息，执行相相应计算算后，修修改顶点点V及其出射射边的状状态，然然后沿着着顶点V的出射边边发送消消息给其其他顶点点，而且且，一个个

8、消息可可能经过过多条边边的传递递后被发发送到任任意已知知ID的目标顶顶点上去去。这些些消息将将会在下下一个超超步(S+1)中被目标标顶点接接收，然然后像上上述过程程一样开开始下一一个超步步(S+1)的迭代过过程在Pregel计算过程程中，一一个算法法什么时时候可以以结束，是由所所有顶点点的状态态决定的的，当图图中所有有的顶点点都已经经标识其其自身达达到“非非活跃（inactive）”状态态时，算算法就可可以停止止运行9.3.4实实例图94 一个个求最大大值的Pregel计计算过程程图9.4Pregel的C+APIPregel已经预先先定义好好一个基基类Vertex类：template clas

9、s Vertex public:virtual void Compute(MessageIterator* msgs) = 0;const string& vertex_id() const;int64 superstep() const;const VertexValue& GetValue();VertexValue* MutableValue();OutEdgeIterator GetOutEdgeIterator();void SendMessageTo(const string& dest_vertex,const MessageValue& message);void VoteTo

10、Halt(); ;在Vetex类中，定定义了三三个值类类型参数数，分别别表示顶顶点、边边和消息息。每一一个顶点点都有一一个给定定类型的的值与之之对应编写Pregel程序时，需要继继承Vertex类，并且且覆写Vertex类的虚函函数Compute()9.4Pregel的C+API9.4.1消息传递递机制9.4.2Combiner9.4.3Aggregator9.4.4拓扑改变变9.4.5输入和输输出9.4.1消消息传递递机制顶点之间间的通讯讯是借助助于消息息传递机机制来实实现的，每条消消息都包包含了消消息值和和需要到到达的目目标顶点点ID。用户可可以通过过Vertex类的模板板参数来来设定消消

11、息值的的数据类类型在一个超超步S中，一个个顶点可可以发送送任意数数量的消消息，这这些消息息将在下下一个超超步（S+1）中被其其他顶点点接收一个顶点点V通过与之之关联的的出射边边向外发发送消息息，并且且，消息息要到达达的目标标顶点并并不一定定是与顶顶点V相邻的顶顶点，一一个消息息可以连连续经过过多条连连通的边边到达某某个与顶顶点V不相邻的的顶点U，U可以从接接收的消消息中获获取到与与其不相相邻的顶顶点V的ID9.4.2CombinerPregel计算框架架在消息息发出去去之前，Combiner可以将发发往同一一个顶点点的多个个整型值值进行求求和得到到一个值值，只需需向外发发送这个个“求和和结果”

12、，从而而实现了了由多个个消息合合并成一一个消息息，大大大减少了了传输和和缓存的的开销在默认情情况下，Pregel计算框架架并不会会开启Combiner功能，因因为，通通常很难难找到一一种对所所有顶点点的Compute()函数都合合适的Combiner当用户打打算开启启Combiner功能时，可以继继承Combiner类并覆写写虚函数数Combine()此外，通通常只对对那些满满足交换换律和结结合律的的操作才才可以去去开启Combiner功能，因因为，Pregel计算框架架无法保保证哪些些消息会会被合并并，也无无法保证证消息传传递给Combine()的顺序和和合并操操作执行行的顺序序图9-5Co

13、mbiner应用的例例子9.4.3AggregatorAggregator提供了一一种全局局通信、监控和和数据查查看的机机制在一个超超步S中，每一一个顶点点都可以以向一个个Aggregator提供一个个数据，Pregel计算框架架会对这这些值进进行聚合合操作产产生一个个值，在在下一个个超步（S+1）中，图图中的所所有顶点点都可以以看见这这个值Aggregator的聚合功功能，允允许在整整型和字字符串类类型上执执行最大大值、最最小值、求和操操作Pregel计算框架架预定义义了一个个Aggregator类，编写写程序时时需要继继承这个个类，并并定义在在第一次次接收到到输入值值后如何何初始化化，以及

14、及如何将将接收到到的多个个值最后后聚合成成一个值值为了保证证得到正正确的结结果，Aggregator操作也应应该满足足交换律律和结合合律9.4.4拓拓扑改变变Pregel计算框架架允许用用户在自自定义函函数Compute()中定义操操作，修修改图的的拓扑结结构，比比如在图图中增加加（或删删除）边边或顶点点Pregel采用两种种机制来来解决这这类冲突突：局部部有序和和Handler（1）局部有有序：拓拓扑改变变的请求求是通过过消息发发送的，在执行行一个超超步时，所有的的拓扑改改变会在在调用Compute()函数之前前完成（2）Handler：对于“局部无无序”机机制无法法解决的的那些操操作冲突突

15、，就需需要借助助于用户户自定义义的Handler来解决，包括解解决由于于多个顶顶点删除除请求或或多个边边增加请请求（或或删除请请求）而而造成的的冲突9.4.5输输入和输输出在Pregel计算框架架中，图图的保存存格式多多种多样样，包括括文本文文件、关关系数据据库或键键值数据据库等在Pregel中，“从从输入文文件生成成得到图图结构”和“执执行图计计算”这这两个过过程是分分离的，从而不不会限制制输入文文件的格格式对于输出出，Pregel也采用了了灵活的的方式，可以以以多种方方式进行行输出9.5Pregel的体系系结构9.5.1Pregel的执行过过程9.5.2容错性9.5.3Worker9.5.

16、4Master9.5.5Aggregator9.5.1Pregel的的执行过过程图9-6图的划分分图在Pregel计算框架架中，一一个大型型图会被被划分成成许多个个分区，每个分分区都包包含了一一部分顶顶点以及及以其为为起点的的边一个顶点点应该被被分配到到哪个分分区上，是由一一个函数数决定的的，系统统默认函函数为hash(ID)modN，其中，N为所有分分区总数数，ID是这个顶顶点的标标识符；当然，用户也也可以自自己定义义这个函函数这样，无无论在哪哪台机器器上，都都可以简简单根据据顶点ID判断出该该顶点属属于哪个个分区，即使该该顶点可可能已经经不存在在了9.5.1Pregel的的执行过过程图9-

17、7 Pregel的执执行过程程图在理想的的情况下下（不发发生任何何错误），一个个Pregel用户程程序的执执行过程程如下：（1）选选择集群群中的多多台机器器执行图图计算任任务，每每台机器器上运行行用户程程序的一一个副本本，其中中，有一一台机器器会被选选为Master，其其他机器器作为Worker（2）Master把把一个图图分成多多个分区区，并把把分区分分配到多多个Worker（3）Master会会把用户户输入划划分成多多个部分分，通常常是基于于文件边边界进行行划分（4）Master向每个Worker发送指令令，Worker收到指令令后，开开始运行行一个超超步。当完成成以后，Worker会通知

18、Master，并把自自己在下下一个超超步还处处于“活活跃”状状态的顶顶点的数数量报告告给Master。上述步步骤会被被不断重重复，直直到所有有顶点都都不再活活跃并且且系统中中不会有有任何消消息在传传输，这这时，执执行过程程才会结结束（5）计算过过程结束束后，Master会给所有有的Worker发送指令令，通知知每个Worker对自己的的计算结结果进行行持久化化存储9.5.2容容错性Pregel采用检查查点机制制来实现现容错。在每个个超步的的开始，Master会通知所所有的Worker把自己管管辖的分分区的状状态（包包括顶点点值、边边值以及及接收到到的消息息），写写入到持持久化存存储设备备Mas

19、ter会周期性性地向每每个Worker发送ping消息，Worker收到ping消息后会会给Master发送反馈馈消息。如果Master在指定时时间间隔隔内没有有收到某某个Worker的反馈消消息，就就会把该该Worker标记为“失效”。同样样地，如如果一个个Worker在指定的的时间间间隔内没没有收到到来自Master的ping消息，该该Worker也会停止止工作每个Worker上都保存存了一个个或多个个分区的的状态信信息，当当一个Worker发生故障障时，它它所负责责维护的的分区的的当前状状态信息息就会丢丢失。Master监测到一一个Worker发生故障障“失效效”后，会把失失效Worke

20、r所分配到到的分区区，重新新分配到到其他处处于正常常工作状状态的Worker集合上，然后，所有这这些分区区会从最最近的某某超步S开始时写写出的检检查点中中，重新新加载状状态信息息。很显显然，这这个超步步S可能会比比失效Worker上最后运运行的超超步S1要早好几几个阶段段，因此此，为了了恢复到到最新的的正确状状态，需需要重新新执行从从超步S到超步S1的所有操操作9.5.3Worker在一个Worker中，它所所管辖的的分区的的状态信信息是保保存在内内存中的的。分区区中的顶顶点的状状态信息息包括：顶点的当当前值以该顶点点为起点点的出射射边列表表，每条条出射边边包含了了目标顶顶点ID和边的值值消息

21、队列列，包含含了所有有接收到到的、发发送给该该顶点的的消息标志位，用来标标记顶点点是否处处于活跃跃状态在每个超超步中，Worker会对自己己所管辖辖的分区区中的每每个顶点点进行遍遍历，并并调用顶顶点上的的Compute()函数，在在调用时时，会把把以下三三个参数数传递进进去：该顶点的的当前值值一个接收收到的消消息的迭迭代器一个出射射边的迭迭代器9.5.4MasterMaster主要负责责协调各各个Worker执行任务务，每个个Worker会借助于于名称服服务系统统定位到到Master的位置，并向Master发送自己己的注册册信息，Master会为每个个Worker分配一个个唯一的的IDMast

22、er维护着关关于当前前处于“有效”状态的的所有Worker的各种信信息，包包括每个个Worker的ID和地址信信息，以以及每个个Worker被分配到到的分区区信息一个大规规模图计计算任务务会被Master分解到多多个Worker去执行，如果参参与任务务执行的的多个Worker中的任意意一个发发生了故故障失效效，Master就会进入入恢复模模式Master在内部运运行了一一个HTTP服务器来来显示图图计算过过程的各各种信息息，用户户可以通通过网页页随时监监控图计计算执行行过程各各个细节节9.5.5Aggregator每个用户户自定义义的Aggregator都会采用用聚合函函数对一一个值集集合进行

23、行聚合计计算得到到一个全全局值每个Worker都保存了了一个Aggregator的实例集集，其中中的每个个实例都都是由类类型名称称和实例例名称来来标识的的在执行图图计算过过程的某某个超步步S中，每个个Worker会利用一一个Aggregator对当前本本地分区区中包含含的所有有顶点的的值进行行归约，得到一一个本地地的局部部归约值值在超步S结束时，所有Worker会将所有有包含局局部归约约值的Aggregator的值进行行最后的的汇总，得到全全局值，然后提提交给Master在下一个个超步S+1开始时，Master就会将Aggregator的全局值值发送给给每个Worker9.6Pregel的应用

24、用实例9.6.1单源最短短路径9.6.2二分匹配配9.6.1单单源最短短路径Pregel非常适合合用来解解决单源源最短路路径问题题，实现现代码如如下：class ShortestPathVertex : public Vertex void Compute(MessageIterator* msgs) int mindist = IsSource(vertex_id() ? 0 : INF; for (; !msgs-Done(); msgs-Next() mindist = min(mindist, msgs-Value(); if (mindist GetValue() *MutableV

25、alue() = mindist; OutEdgeIterator iter = GetOutEdgeIterator(); for (; !iter.Done(); iter.Next() SendMessageTo(iter.Target(), mindist + iter.GetValue(); VoteToHalt(); ;9.6.2二二分匹配配程序的执执行过程程是由四四个阶段段组成的的多个循循环组成成的，当当程序执执行到超超步S时，Smod4就可以得得到当前前超步处处于循环环的哪个个阶段。每个循循环的四四个阶段段如下：（1）阶段0：对于左左集合中中的任意意顶点V，如果V还没有被被匹配

26、，就发送送消息给给它的每每个邻居居顶点请请求匹配配，然后后，顶点点V会调用VoteToHalt()进入“非非活跃”状态。如果顶顶点V已经找到到了匹配配，或者者V没有找到到匹配但但是没有有出射边边，那么么，顶点点V就不会发发送消息息。当顶顶点V没有发送送消息，或者顶顶点V发送了消消息但是是所有的的消息接接收者都都已经被被匹配，那么，该顶点点就不会会再变为为“活跃跃（active）”状态态（2）阶段1：对于右右集合中中的任意意顶点U，如果它它还没有有被匹配配，则会会随机选选择它接接收到的的消息中中的其中中一个，并向左左集合中中的消息息发送者者发送消消息表示示接受该该匹配请请求，然然后给左左集合中中

27、的其他他请求者者发送拒拒绝消息息；然后后，顶点点U会调用VoteToHalt()进入“非非活跃”状态（3）阶段2：左集合合中那些些还未被被匹配的的顶点，会从它它所收到到的、右右集合发发送过来来的接受受请求中中，选择择其中一一个给予予确认，并发送送一个确确认消息息。对于于左集合合中已经经匹配的的顶点而而言，因因为它们们在阶段段0不会向右右集合发发送任何何匹配请请求消息息，因而而也不会会接收到到任何来来自右集集合的匹匹配接受受消息，因此，是不会会执行阶阶段2的（4）阶段3：右集合合中还未未被匹配配的任意意顶点U，会收到到来自左左集合的的匹配确确认消息息，但是是，每个个未匹配配的顶点点U，最多会会收

28、到一一个确认认消息。然后，顶点U会调用VoteToHalt()进入“非非活跃”状态，完成它它自身的的匹配工工作9.7Pregel和MapReduce实现现PageRank算算法的对对比9.7.1PageRank算法9.7.2PageRank算法在Pregel中的实现现9.7.3PageRank算法在MapReduce中的实现现9.7.4PageRank算法在Pregel和MapReduce中实现的的比较PageRank是一个函函数，它它为网络络中每个个网页赋赋一个权权值。通通过该权权值来判判断该网网页的重重要性该权值分分配的方方法并不不是固定定的，对对PageRank算法的一一些简单单变形都都

29、会改变变网页的的相对PageRank值（PR值）PageRank作为谷歌歌的网页页链接排排名算法法，基本本公式如如下：对于任意意一个网网页链接接，其PR值为链入入到该链链接的源源链接的的PR值对该链链接的贡贡献和，其中，N表示该网网络中所所有网页页的数量量，Ni为第i个源链接接的链出出度，PRi表示第i个源链接接的PR值9.7.1PageRank算法9.7.1PageRank算法网络链接接之间的的关系可可以用一一个连通通图来表表示，下下图就是是四个网网页（A,B,C,D）互相链链入链出出组成的的连通图图，从中中可以看看出，网网页A中包含指指向网页页B、C和D的外链，网页B和D是网页A的源链接接

30、在Pregel计算模型型中，图图中的每每个顶点点会对应应一个计计算单元元，每个个计算单单元包含含三个成成员变量量：顶点值（Vertexvalue）：顶点点对应的的PR值出射边（Outedge）：只需需要表示示一条边边，可以以不取值值消息（Message）：传递递的消息息，因为为需要将将本顶点点对其它它顶点的的PR贡献值，传递给给目标顶顶点每个计算算单元包包含一个个成员函函数Compute()，该函数数定义了了顶点上上的运算算，包括括该顶点点的PR值计算，以及从从该顶点点发送消消息到其其链出顶顶点9.7.2PageRank算法在Pregel中的实现现9.7.2PageRank算法在Pregel中

31、的实现现class PageRankVertex: public Vertex 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(); SendM

32、essageToAllNeighbors(GetValue()/ n); else VoteToHalt();9.7.2PageRank算法在Pregel中的实现现PageRankVertex继承自Vertex类，顶点点值类型型是double，用来保保存PageRank中间值，消息类类型也是是double，用来传传输PageRank值，边的的value类型是void，因为不不需要存存储任何何信息这里假设设在第0个超步时时，图中中各顶点点值被初初始化为为1/NumVertices()，其中，NumVertices()表示顶点点数目在前30个超步中中，每个个顶点都都会沿着着它的出出射边，发送它它的

33、PageRank值除以出出射边数数目以后后的结果果值。从从第1个超步开开始，每每个顶点点会将到到达的消消息中的的值加到到sum值中，同同时将它它的PageRank值设为0.15/NumVertices()+0.85*sum到了第30个超步后后，就没没有需要要发送的的消息了了，同时时所有的的顶点停停止计算算，得到到最终结结果MapReduce也是谷歌歌公司提提出的一一种计算算模型，它是为为全量计计算而设设计采用MapReduce实现PageRank的计算过过程包括括三个阶阶段：第一阶段段：解析析网页第二阶段段：PageRank分配第三阶段段：收敛敛阶段9.7.3PageRank算法在MapRed

34、uce中的实现现9.7.3PageRank算法在MapReduce中的实现现该阶段的的任务就就是分析析一个页页面的链链接数并并赋初值值。一个网页页可以表表示为由由网址和和内容构构成的键键值对，作为Map任务的输输入。阶阶段1的Map任务把映射为URL，后进行输输出，其其中，PRinit是该URL页面对应应的PageRank初始值，url_list包含了该该URL页面中的的外链所所指向的的所有URL。Reduce任务只是是恒等函函数，输输入和输输出相同同。对右图，每个网网页的初初始PageRank值为1/4。它在该该阶段中中:Map任务的输输入为：Map任务的输输出为：AURL，1/4，BURL

35、，1/4，CURL，DURL，1/4，1.阶段1：解析网网页9.7.3PageRank算法在MapReduce中的实现现该阶段的的任务就就是多次次迭代计计算页面面的PageRank值。在该阶段段中，Map任务的输输入是URL，其中，cur_rank是该URL页面对应应的PageRank当前值，url_list包含了该该URL页面中的的外链所所指向的的所有URL。对于url_list中的每个个元素u，Map任务输出出u，（其中，|url_list|表示外链链的个数数），并并输出链链接关系系。每个页面面的PageRank当前值被被平均分分配给了了它们的的每个外外链。Map任务的输输出会作作为下面面

36、Reduce任务的输输入。对对下图第第一次迭迭代Map任务的输输入输出出如下：输入为：输出为：BURL，CURL，DURL，AURL，AURL，CURL，BURL，DURL，AURL，BURL，DURL，2.阶段2：PageRank分配9.7.3PageRank算法在MapReduce中的实现现然后，在在该阶段段的Reduce阶段，Reduce任务会获获得和u，Reduce任务对于于具有相相同key值的value进行汇总总，并把把汇总结结果乘以以d，得到每每个网页页的新的的PageRank值new_rank，然后输输出URL，作为下下一次迭迭代过程程的输入入。Reduce任务把第第一次迭迭代后

37、Map任务的输输出作为为自己的的输入，经过处处理后，阶段2的Reduce输出为：AURL，0.2500，BURL，0.2147，CURL，DURL，0.3206，经过本轮轮迭代，每个网网页都计计算得到到了新的的PageRank值。下次次迭代阶阶段2的Reduce输出为：AURL，0.2200，BURL，0.1996，CURL，DURL，0.3808，2.阶段2：PageRank分配（Reduce阶段）9.7.3PageRank算法在MapReduce中的实现现Mapper函数的伪伪码：input-PageA,PageB,PageC./PageN外链指向向PageA,PageB,PageC.be

38、ginNn:=thenumber of outlinks forPageN;foreachoutlink PageKoutputPageK-outputPageN-PageA, PageB,PageC./同时输出出链接关关系，用用于迭代代end/*Mapper输出如下下（已经经排序，所以PageK的数据排排在一起起，最后后一行则则是链接接关系对对）：PageK-PageK-.PageK-Reducer函数的伪伪码：inputmappersoutputbeginRankK:=(1-beta)/N;/N为整个网网络的网网页总数数foreachinlinkPageNiRankK+=RankNi/Nni *beta/输出PageK及其新的的PageRank值用于下下次迭代代output-end该阶段是一个多次迭代代过程，迭代多多次后，当PageRank值趋于稳稳定时，就得得出了较较为精确确的PageRank值。9.7.3PageRank算法在MapReduce中的实现现该阶段的的任务就就是由一一个非并并行组件件决定是是否达到到收敛，如果达达到收敛敛，就写写出PageR