基于剪枝的图漫游并行计算方法和应用

摘要

本发明公布了一种基于剪枝的图漫游并行计算方法和应用，涉及大规模数据并行计算和处理技术领域，该方法在共享内存系统上实现的基于剪枝的高效图漫游，在计算之前的预处理阶段，根据拓扑特征识别出图中的边界点，在此基础上计算过程中进行相应的剪枝计算操作。本发明通过剪去边界点，使得顶点的更新速度能够更快扩散，算法的收敛速度加快，从而减少迭代轮数；在并行计算中对任务进行划分时，剪去边界点使得任务划分更加均衡，以达到降低计算开销、提升计算性能的目的。

说明书

技术领域

本发明涉及大规模数据并行计算和处理技术领域，尤其涉及一种基于剪枝的图漫游并行 计算方法和应用。

背景技术

近年来，随着互联网的不断发展，越来越多的信息和数据需要运用图结构进行存储和计 算，例如，在线社交网络的好友关系、论文库中的引用关系、搜索引擎中记录的网站链接关 系以及维基百科中的知识图谱等。这些图计算往往数据规模庞大，点和边的数量达到 GB/TB/ZB级别，甚至更大。大规模图计算有着计算密度低、数据随机访问等难点。并行计 算是大规模图计算问题的一种常用技术手段。

图是一种数据结构，图G通常由一组顶点的集合V和顶点之间的边的集合E组成。任意 一条边e＝(u,v)表示存在一条从顶点u到顶点v的边，u称作v的父节点，v称作u的子节 点，e称作u的出边，v的入边。图计算模型中，V和E都包含计算状态数据。状态的更新是 通过在每个顶点上运行一系列的迭代计算来完成，计算结果是图中所有顶点和边的最终状态 的聚合。顶点计算依赖于自身顶点、邻居顶点以及边的状态，并可以更新这些状态。

图漫游是指对于图G，给出一定的约束条件，G中有任意顶点v不满足该约束条件时， 对顶点v进行更新操作，顶点v更新后的状态会通过出边影响到它的邻居顶点，引起邻居顶 点的更新，直到图G中所有顶点都满足约束条件，没有顶点需要再进行更新操作为止。其中， 更新操作是在图的顶点上根据算法执行计算。

现有图计算框架中，Pregel是一个用于分布式图计算的典型计算框架(GrzegorzMalewicz etal.Pregel:ASystemforLarge-ScaleGraphProcessing.ACMSIGMOD,2010)，主要用于图遍 历、最短路径、PageRank等计算。这是一个以顶点为中心的框架，顶点通过它们的边循环同 时发送信息给所有它们的外部邻居，目标顶点使用相关组合收集这些信息，系统是批量同步 的，所以接收的值只有在下一轮才能被看到。Pregel性能相对较慢，可能是由于框架开销以 及利用了分布式存储的机器。一方面，虽然分布式系统有更强的计算能力和存储能力，但对 于节点数量庞大的分布式系统来说，计算密度低和数据随机访问的特点导致计算过程中通信 开销很大，其处理图技术时带来的性能提升与系统成本的增加不匹配，计算能力无法完全发 挥；另一方面，Pregel对于输入的图直接进行计算，没有预处理机制，在实际的计算过程中 会有一些不必要的计算开销。

发明内容

为了克服上述现有技术的不足，本发明提供一种基于剪枝的图漫游并行计算方法和应用， 在共享内存系统上实现基于剪枝的高效图漫游，通过在计算之前的预处理阶段对图进行拓扑 特征识别，在此基础上，在计算过程中进行相应的剪枝操作，以降低计算开销。

本发明的原理是：本发明提供的剪枝图漫游模型针对图中的“边界点”顶点进行剪枝操 作，从而优化计算过程，降低计算开销，提高计算效率。在图计算过程中，每个顶点v的状 态改变依赖于v的父节点的状态改变。根据图中每个点的入边和出边情况，可以对图中的点 进行分类，没有入边的点称为“输入点”，没有出边的点称为“输出点”，其他点称为“中间 点”。这样的分类方式可以作为图的一个拓扑特征。“输入点”和“输出点”相当于图的“边 界点”，它们在计算中会表现出与中间顶点不同的情况。对于没有入边的“输入点”来说，初 始化之后它的状态不会再更新；对没有出边的“输出点”来说，整个计算过程中虽然会被不 断更新，但由于它们没有出边，更新后的状态不会再传递到其他顶点，所以只有最终的更新 状态才是有意义的，过程中的更新并不必要。标准图、自然图中均存在大量“边界点”，这些 点的比例与图本身的特点相关，例如Friendster社交网络图中有44％的“边界点”，Twitter社 交网络图中有22％的“边界点”，维基百科关系图中有14％的“边界点”，均存在优化空间。 本发明提供的剪枝图漫游模型针对图中的“边界点”顶点进行剪枝操作，通过剪除边界点优 化计算过程，降低计算开销，提高计算效率。

本发明提供的技术方案是：

一种基于剪枝的图漫游并行计算方法，对图中顶点进行分类，针对图中的边界点进行剪 枝操作，通过剪除边界点来优化计算过程，包括预处理阶段、剪枝计算阶段、收尾补充计算 阶段；具体包括如下步骤：

1)在预处理阶段，识别图的拓扑特征，对图进行预处理操作；具体步骤如下：

11)读入图数据，根据图中顶点的拓扑特征进行搜索，得到边界点和非边界点；边界点 分为a类、b类、c类和d类；

a类：入边数量为0的顶点；

b类：入边、出边数量均为1的顶点，且该顶点的父节点u1符合条件b1或b2：

b1：u1的入边数量为0，出边数量为1；

b2：u1为b类顶点；

c类：出边数量为0的顶点；

d类：入边、出边数量均为1的顶点，且该顶点的子节点u2符合条件d1或d2：

d1：u2的出边数量为0，入边数量为1；

d2：u2为d类顶点。

12)对a类和b类边界点进行初始化，即根据选用的计算方法进行计算，得到相应边界 点的计算结果；

13)对于a类和b类边界点，当它们的子节点为非边界点时，将步骤12)的计算结果传 递给它们的子节点；

14)将a类和b类边界点与它们的子节点之间的边从图结构中删去；

上述步骤13)和14)可使得a类和b类边界点的子节点不必再访问相应的父节点(即相 应的a类和b类边界点)，可减少边的访问开销。

2)在计算阶段，对预处理后的图进行剪枝迭代计算；

21)依次访问图中的顶点，如果该顶点边界点，则跳过该顶点；否则对该顶点利用步骤 12)所述计算方法重新进行计算，得到新的计算结果，作为该顶点的计算结果；

22)顶点全部访问结束后，根据步骤12)所述计算方法所设定的收敛条件，当当前图中 所有顶点达到收敛条件时，结束剪枝计算；否则，重复21～22进行剪枝迭代计算；

3)在收尾阶段，进行补充计算；

对c类和d类边界点，根据步骤12)所述计算方法进行计算，得到计算结果，作为相应 边界点的结果。

针对上述基于剪枝的图漫游并行计算方法，进一步地，步骤12)所述计算方法为PageRank 算法或单源最短路径算法。所述单源最短路径算法为Dijkstra算法、Bellman-Ford算法或SPFA 算法。

上述基于剪枝图漫游模型的并行计算方法可应用于PageRank(网页排名)、基于图着色 问题的寄存器分配和最短路径获取等。其中，PageRank(网页排名)方法用来标识网页的等 级/重要性，通过网站之间的链接关系，计算出每个网站的重要程度。基于图着色问题的寄存 器分配方法，是对于给定的无向图G，给出一种着色方案，使任意相邻的顶点颜色不同，该 方法应用于寄存器分配技术可提高程序执行速度；最短路径旨在寻找图中两顶点之间的最短 路径，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题中最短路径的获取。

本发明还提供一种采用上述基于剪枝的图漫游并行计算方法实现的网页重要性排序方法， 通过PageRank方法计算获得网页的重要性排序结果，具体为如下过程：

61)将网页和网页之间的链接关系表示为图G，用图中顶点vi分别代表不同页面，用顶 点vi指向vj的箭头表示页面i中有指向页面j的超链接；

62)根据图中顶点的拓扑特征进行搜索，得到四种类型的边界点，分别为a类～d类；

63)针对a类和b类边界点，通过PageRank方法进行初始化，得到a类和b类边界点的 计算结果；

64)对于a类和b类边界点，当它的子节点为非边界点时，将相应计算结果传递给它的 子节点；

65)剪除a类和b类边界点与它们的子节点之间的边；

66)再针对图中不是边界点的其他所有顶点，通过PageRank方法进行迭代计算，图中所 有顶点达到设定的迭代收敛阈值时终止迭代；

67)再对c类和d类边界点通过PageRank方法进行计算，得到c类和d类边界点的计算 结果；

68)根据所有顶点的计算结果进行排序，得到网页的重要性排序结果。

针对上述网页重要性排序方法，进一步地，所述PageRank方法具体为：

设页面x的PageRank值为P(x)，页面x包含的超链接数量为N(x)，页面x所指向的所 有页面的集合为B(x)，通过式1计算得到任意页面i的PageRank值：

P(i)＝C1∑_j∈B(i)P(j)/N(j)+C2(式1)

式1中，i为任意页面；P(i)为页面i的PageRank值；C1、C2为常数，本实施例中，C1＝0.85， C2＝0.15；B(i)为页面i所指向的所有页面的集合；j为集合B(i)中任意页面；P(j)为页面j的 PageRank值；N(j)为页面j包含的超链接数量。

针对上述网页重要性排序方法，进一步地，所述PageRank方法的迭代收敛条件为图中所 有页面的PageRank值不再发生改变，表示为式2：

∑_i∈V(G)|P_new(i)-P_old(i)|＜ε(式2)

式2中，V(G)为图G中所有页面的集合，i为V(G)中任意页面，P_new(i)为当前一轮迭代 结束后页面i的PageRank值，P_old(i)为上一轮迭代结束后页面i的PageRank值，ε为数学意 义上的极小值。在本发明实施例中，ε取值为0.0000001。

与现有技术相比，本发明的有益效果是：

本发明提供一种基于共享存储系统的并行计算方法，利用本发明提供的技术方案，计算 过程中的剪枝会使得待计算的点数和边数减少，带来计算开销下降，计算性能提升；由于剪 去了这些“边界点”，顶点的更新速度能够更快的扩散，算法的收敛速度加快，可减少迭代轮 数；在并行计算中对任务进行划分时，剪去“边界点”能够使得任务划分更加均衡，从而达 到降低计算开销、提升计算性能的效果。

上述基于剪枝图漫游模型的并行计算方法可应用于PageRank(网页排名)、基于图着色 问题的寄存器分配和最短路径获取等。将本发明方法应用于网页重要性排序，通过PageRank 方法计算获得网页的重要性排序结果，相比不剪枝的计算方法，本发明提供方法无论是迭代 轮数还是每一轮中需要计算PageRank值的顶点数量均大为减少，极大的降低了计算开销，提 高了计算效率。

附图说明

图1是本发明提供的图漫游方法的流程框图。

图2是本发明实施例提供的PageRank算法示例图G；

其中，圆圈代表顶点，图G中包含v1-v7七个顶点；顶点之间的箭头代表边，vi指向vj 的箭头代表边(vi，vj)。

图3是本发明实施例中对示例图G进行预处理后得到的图G'；

其中，虚线圈与虚线分别表示被剪去的顶点v1、v2、v6、v7和边(v1，v2)、(v2，v3)、 (v5，v6)、(v6，v7)。

具体实施方式

下面结合附图，通过实施例进一步描述本发明，但不以任何方式限制本发明的范围。

本发明提供一种基于剪枝的图漫游并行计算方法，对图中顶点进行分类，针对图中的边 界点进行剪枝操作，通过剪除边界点来优化计算过程，包括如下步骤：

1)预处理阶段，识别图的拓扑特征，包括对边界点进行分类、初始化计算、对图进行预 处理操作；具体步骤如下：

11)读入图数据，根据顶点的拓扑特征进行搜索，得到边界点；边界点分为四类：

a类：入边数量为0的顶点；

b类：入边、出边数量均为1的顶点，且入边的起点u1(父节点)符合条件b1或b2：

b1：u1的入边数量为0，出边数量为1；

b2：u1为b类顶点；

c类：出边数量为0的顶点；

d类：入边、出边数量均为1的顶点，且出边的终点u2(子节点)符合条件d1或d2：

d1：u2的出边数量为0，入边数量为1；

d2：u2为d类顶点。

12)将上述a类、b类、c类和d类顶点均标记为边界点；对a类和b类边界点进行初始 化，即根据选用的计算方法(如：PageRank算法或单源最短路径算法)对这些点(a类和b 类边界点)进行计算，得到初始化结果；

其中，Dijkstra算法是单源最短路径问题的经典算法之一，目前有Dijkstra算法、 Bellman-Ford算法、SPFA算法等。

13)对于a类和b类边界点，当它们的子节点未被标记为边界点时，将步骤12)的计算 结果传递给它们的子节点，以便计算阶段使用，因此需为这些子节点创建数据结构，用于存 储其父节点的计算结果；

当它们的子节点被标记为边界点时，它们不属于步骤2中需要计算的顶点，不需要被传 值；

14)将a类和b类边界点与它们的子节点之间的边从图结构中删去；

上述步骤13)和14)可使得a类和b类边界点的子节点不必再访问相应的父节点(即相 应的a类和b类边界点)，可减少边的访问开销。

2)计算阶段，对预处理后的图进行剪枝计算；

21)依次访问图中的顶点，如果该顶点被标记为“边界点”，则跳过该顶点；否则对该顶 点重新计算，得到新的计算结果，用新的计算结果替换该顶点的之前的计算结果；

22)顶点全部访问结束后，根据选用的计算方法所设定的收敛条件，判断当前图中所有 顶点是否达到收敛条件，如果是，则计算阶段结束；否则，重复21～22的过程；

3)收尾阶段进行补充计算；

在计算阶段结束后的收尾阶段，依据具体所实施的算法对c类和d类顶点进行计算，得 到计算结果，即为相应顶点的计算结果。

由此得到所有顶点的最终状态。

下面通过实施例对本发明做进一步说明。

以下实施例通过采用PageRank算法对网络页面的重要性进行排序，本实施例中，网络页 面为七个，页面之间存在链接关系；七个页面和页面之间的链接关系可以表示为图2中的图 G；其中v1-v7分别代表七个页面，vi指向vj的箭头代表页面i中有指向页面j的超链接。利 用本发明提供的基于剪枝图模型的图漫游方法，在图2中的图G上执行PageRank算法对网 络页面的重要性进行排序，获得排序结果。

PageRank算法的计算过程如下：

设页面x的PageRank值为P(x)，页面x包含的超链接数量(即顶点x的出边数量)为 N(x)，页面x所指向的所有页面(即顶点x的子节点)的集合为B(x)，则对于任意页面i：

P(i)＝C1∑_j∈B(i)P(j)/N(j)+C2(式1)

式1中，i为任意页面；P(i)为页面i的PageRank值；C1、C2为常数，本实施例中，C1＝0.85， C2＝0.15；B(i)为页面i所指向的所有页面的集合；j为集合B(i)中任意页面；P(j)为页面j的 PageRank值；N(j)为页面j包含的超链接数量；

初始时，所有页面的PageRank值初始赋值为1，然后开始按照上述公式(式1)进行迭 代计算；算法的收敛条件为图中所有页面的PageRank值不再发生改变，表示为式2：

∑_i∈v(G)|P_new(i)-P_old(i)|＜ε(式2)

式2中，V(G)为图G中所有页面的集合，i为V(G)中任意页面，P_new(i)为当前一轮迭代 结束后页面i的PageRank值，P_old(i)为上一轮迭代结束后页面i的PageRank值，ε为数学意 义上的极小值，本实施例中，取ε＝0.0000001。

利用本发明提供的基于剪枝图模型的图漫游方法，在图2中的图G上执行PageRank算 法对网络页面的重要性进行排序，通过以下计算过程获得排序结果：

1)预处理阶段，识别图的拓扑特征：

11)读入图G中的数据，图G表示了七个页面和页面之间的链接关系，对“边界点”拓 扑特征进行搜索和标记；图2中的“边界点”分别为页面(表示为顶点)v1、v2、v6、v7， 其中v1为a类边界点，v2为b类边界点，v6为d类边界点，v7为c类边界点；

12)对于上述边界点v1、v2、v6、v7做标记；对a/b类边界点v1、v2，通过式1进行初 始化计算，得到如下结果：

P(v1)＝0.15；

P(v2)＝0.85*P(1)/1+0.15＝0.28；

13)v2的子节点v3不是边界点，所以v2的计算结果需要传递给v3。

如式1中所示，计算v3的PageRank值需要先对v3所有父节点的P(j)/N(j)值进行求和， 去掉v2后，需要把v2的P(j)/N(j)值存储在v3的数据结构中，以便v3在计算时可以调用该 数值，存储值为P(v2)/N(v2)＝0.28/1＝0.28。

14)将边(v2，v3)从图结构中去掉，则访问v3的父节点时不会再访问到顶点v2。

2)正式计算阶段，对图进行剪枝计算：

21)依次访问图中的顶点v1-v7，其中v1、v2、v6、v7被标记，跳过不访问；对v3、v4、 v5分别通过式1进行计算(保留两位小数)：

如图3中所示，预处理后的图G’中v3没有父节点，而v3中存储有v2的计算结果0.28， 因此第一轮迭代中，P(v3)＝0.85*P(2)+0.15＝0.39；之后由于没有父节点的新值传给v3，P(v3) 保持不变；

v4的父节点为v3，每一轮迭代中，v4取P(v3)的上一轮结果通过式1进行计算；v5的父 节点为v3和v4，每一轮迭代中，P(v5)取P(v3)和P(v4)的上一轮结果通过式1进行计算；具 体计算结果见下表1：

表1剪枝计算对非边界点迭代计算过程中的得到的PageRank值

P(v3) P(v4) P(v5) 初始值 1.00 1.00 1.00 1轮迭代 0.39 0.58 1.42 2轮迭代 0.39 0.31 0.56 3轮迭代 0.39 0.31 0.58 4轮迭代 0.39 0.31 0.58

根据式2判断是否达到收敛条件，本实施例中，式2中取ε＝0.0000001。第4轮迭代后， |P_new(v3)-P_old(v3)|+|P_new(v4)-P_old(v4)|+|P_new(v5)-P_old(v5)|＝0<ε，达到了收敛条件， 算法结束。

3)收尾阶段的补充计算：

对v6、v7通过式1进行更新计算：

P(v6)＝0.85*P(5)/1+0.15＝0.64

P(v7)＝0.85*P(6)/1+0.15＝0.69

所以最终结果为：

表2剪枝计算得到的PageRank值最终结果

P(v1) P(v2) P(v3) P(v4) P(v5) P(v6) P(v7) 0.15 0.28 0.39 0.31 0.58 0.64 0.69

由此，利用本发明提供的基于剪枝图模型的图漫游方法，在图2中的图G上执行PageRank 算法对网络页面的重要性进行排序，获得的页面重要性排序结果为：v7>v6>v5>v3>v4> v2>v1。

为说明本发明方法能够降低计算开销的效果，以下列出采用现有的不剪枝方法直接对图 2进行PageRank计算的迭代过程，作为对照。采用现有的不剪枝方法直接对图2进行PageRank 计算的迭代过程如表2所示：

表2

P(v1) P(v2) P(v3) P(v4) P(v5) P(v6) P(v7) 初始值 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1轮迭代 0.15 1.00 1.00 0.58 1.43 1.00 1.00 2轮迭代 0.15 0.28 1.00 0.58 1.06 1.36 0.58 3轮迭代 0.15 0.28 0.39 0.58 1.06 1.05 1.31 4轮迭代 0.15 0.28 0.39 0.31 0.81 0.58 1.05 5轮迭代 0.15 0.28 0.39 0.31 0.58 0.84 1.05 6轮迭代 0.15 0.28 0.39 0.31 0.58 0.64 0.86 7轮迭代 0.15 0.28 0.39 0.31 0.58 0.64 0.69 8轮迭代 0.15 0.28 0.39 0.31 0.58 0.64 0.69

可以看出，最终计算结果一致。采用现有的不剪枝方法的迭代轮数为8轮，而采用本发 明方法使得剪枝后的迭代轮数只有4轮，且每一轮中只需要计算三个顶点的PageRank值，极 大的降低了计算开销。

需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员 可以理解：在不脱离本发明及所附权利要求的精神和范围内，各种替换和修改都是可能的。 因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的 范围为准。