一、同步图运算系统 1、图算法 （1）PageRank Google用于对网页重要性打分的算法。
顶点：网页 边：超链接
（2）计算方法 初始化：所有顶点的PageRank为1/N 迭代：用公式迭代直至收敛
迭代公式：
Ru：所求u的PageRank Rv：顶点v的PageRank Lv：顶点v的出度（出边的条数） Bu：顶点u的入邻居集合 d：damping factor N：总顶点个数 （3）出现问题 由于N很大，造成的数据精度可能不够。 所以Ru’=NRu，
改进算法计算方法： 初始化：所有顶点的PageRank为1 迭代：用新公式迭代直至收敛
新的迭代公式：
Ru：所求u的PageRank*N Rv：顶点v的PageRank*N Lv：顶点v的出度（出边的条数） Bu：顶点u的入邻居集合 d：damping factor N：总顶点个数
2、同步图运算 （1）图计算模型 运算分成多个超步。 超步内，并行执行每个顶点。 超步间，全局同步。
顶点算法通常步骤： 接收上个超步发出的in-neighbor的消息。 计算当前顶点的值。 向out-neighbor发消息。 （2）图计算模型的特点 特点1：BSP模型 Bulk Synchronous Processing
特点2：基于顶点的编程模型 每个顶点有一个value。 顶点为中心的运算：程序员实现一个compute函数。在每个超步中，同步图系统对每一个顶点调用一次Compute。Compute通常接收消息，计算，发送消息。 （3）图计算如何结束 顶点有两种状态： 活跃态：图系统只对活跃顶点调用Compute；顶点初始状态均为活跃态。 非活跃态：Compute调用Vote to halt时，顶点变为非活跃态；非活跃态的顶点也可以重新变为活跃态。
当所有的顶点处于非活跃状态时，图系统结束本次图运算。
3、图计算编程 GraphLite编程 实现class Vertex的一个子类 class Vertex中有两类函数： （1）图计算程序员需要实现的：Compute() （2）系统提供的，可以在Compute调用的。例如： getValue(),mutableValue(), getOutEdgeIterator(),sendMessageTo(),sendMessageToAllNeighbors(), voteToHalt() superstep()：获取当前超步数：从0开始计数 acculate(),getAggregate()：全局统计量
4、系统实现 master worker 每个worker对应一个graph partition。
5、小结 •基于BSP模型实现同步图运算 •运算在内存中完成 •容错依靠定期地把图状态写入硬盘生成检查点：在一个超步开始时，master可以要求所有的worker都进行检查点操作。 •可以比较容易地表达一些图操作
二、异步图运算系统 可以用来实现一些机器学习算法。允许不同的顶点有不同的更新速度；一个顶点的更新，它的邻居顶点立即可见，而不是等到下一个超步开始。从而可以更快读地收敛。
1、数据模型 （1）Data graph G=(V,E) 每个顶点、每条边都可以有数据D （2）全局数据表（SDT，shared data table） SDT[key] -> value 可以定义全局可见的数据
2、计算过程 Dscopev = update(Dscopev; SDT) update：类似compute，程序员定义的顶点运算 Dscopev：顶点运算设计的范围。包括顶点v，v的相邻边，v的相邻顶点。