基于BFS结果集的可达性保持图并行计算

谢 羿（沈阳黎明航空发动机（集团）有限责任公司，辽宁 沈阳 110043）



基于BFS结果集的可达性保持图并行计算

谢 羿
（沈阳黎明航空发动机（集团）有限责任公司，辽宁 沈阳 110043）

摘 要：传统计算可达性保持图的方法通常基于单机模式，针对小规模数据集进行计算。在处理大规模图数据以及大量中间数据时，传统方法将面临内存容量和计算速度的瓶颈问题。为了解决上述问题，本文提出了基于BFS结果集的可达性保持图并行计算方法。

关键词：图数据；可达；MapReduce；并行化；保持图

0 引言

可达性保持图实质上是一种在可达性查询方面与原始图等价的压缩图。其目的是获取可达性保持图，以解决直接基于原始图进行可达性查询开销过大的问题。算法首先使用广度优先遍历（BFS）获得原始图中每个顶点的所有祖先顶点和后代顶点，然后通过基于类似邻居匹配的方法匹配原始图中各顶点的祖先顶点集和后代顶点集来寻找等价类，并对等价类进行压缩处理。

1 基于BFS结果集的可达性保持图并行计算

1.1 基于BFS结果集的SCC并行查找算法

定理1：强连通分量内的任意两顶点相互可达。

根据定理1，我们可以推出：对于某一强连通分量SCC内的任意一个顶点v，SCC中除v之外的其他顶点既包含于v的向后BFS结果集N-，又包含于v的向前BFS结果集N+。本文不考虑单一顶点作为强连通分量进行处理，对于可达性等价类的处理同样也不考虑将单一顶点作为等价类处理。基于BFS结果集的SCC查找算法如下：

（1）输入每个顶点v的向后BFS结果集N-和向前BFS结果集N+；

（2）对同一个顶点v，求temp=N-（v）∩N+（v）；

（3）如果|temp|＞0，则SCC= temp∪｛v｝，输出SCC；否则，返回步骤1，计算下一个顶点。

（4）对所有输出的SCC去重，得到最终的全部SCC结果集。

1.2 基于标签传递更新的SCC压缩算法

压缩强连通分量后，为不影响图中各顶点与强连通分量之间的可达性，我们提出了基于标签传递更新的强连通分量压缩算法。

对于图1（a），我们选取本体点v5作为传递标签，删除所有自指边后得到的更新图为图1（b）。

图1标签传递更新SCC

需要注意的是，原始图中的SCC将被表示为超点（本体点），传递更新后并不影响图中其他顶点到超点的可达性关系，因此满足可达性等价条件。标签传递更新SCC后获得的压缩图为可达性保持图。基于标签传递更新的SCC压缩算法描述如下：

（1）选取SCC传递标签；因为SCC内的顶点已经排序，所以选择标签值最小的点（本体点）作为标签传递起始点。

（2）对属于同一个SCC的其他所有顶点，传递更新其标签为本体点标签；同一个SCC内的各顶点之间的相关边将转换为自指边。超点（本体点）将继承原SCC与外部相关联的边。

（3）遍历原始图中的边，如果存在自指边则删除。

（4）输出更新图。

2 仿真实验和分析

实验使用6台P C机搭建的基于Hadoop2.4.0版本的计算集群。其中1台作为Master节点，另外5台作为Slave节点。

算法的有效性：我们通过计算压缩比来评估可达性保持图压缩获取的有效性。压缩比的计算公式为CPR=|Gr|/|G|，其中|G|表示原始图的规模，|Gr|表示可达性保持图（压缩图）的规模。实验首先基于标签传递更新SCC压缩算法获得原始图的可达性保持图，并计算了可达性保持图相对于原始图的压缩比CPRLS。在标签传递更新SCC后的可达性保持图基础上，我们通过压缩并更新可达性等价类来进一步获取可达性保持图，并计算出最终的可达性保持图相对于原始图的压缩比CPRLSEQ。压缩比越小，表明压缩方案的压缩效果越好，即最终获得的可达性保持图的规模越小。

表1可达性保持图相对于原始图的压缩比

从表1可以看出，各数据集在标签传递更新SCC后所获得的可达性保持图从整体上达到了较好的压缩效果。在压缩更新可达性等价类后获得的可达性保持图的规模进一步减小。对于同一类型的网络图，如p2p网络，可达性等价类压缩更新方法可将可达性保持图的压缩比平均降低21个百分点。

查询性能分析：本组实验通过对原始图和可达性保持图中的所有顶点分别进行BFS遍历来对比在两种图数据上的查询性能。

如图2所示，在可达性保持图上的查询时间明显少于在原始图上的查询时间，进一步证明了本文可达性保持图的有效性。

加速比实验分析：加速比可以作为衡量并行计算相对于串行计算性能提升的指标。加速比越大说明并行计算效率越好。

由图3可以看出，随着计算节点的增加，测试集的加速比逐渐增大。但由于计算节点数的增加导致节点间的数据传输量增加，会产生额外的网络传输时间，因此加速比的增长趋势逐渐平缓。

图2查询性能对比

图3加速比实验

结语

为解决大规模图数据的存储和可达性保持图在单机计算方面产生的瓶颈问题，本文着重研究了基于BFS的结果集的可达性保持图并行计算方法，并利用Map Reduce模型实现了分布式、并行计算可达性保持图。实验表明，本文可达性保持图计算方法是有效的。在保证可达性查询等价的同时，可达性保持图具有更好的压缩比和查询性能。在基于分布式的计算平台上，本文计算方案表现出较好的加速比。

参考文献

［1］ Fan W，Li J，Wang X， et al. Query preserving graph compression［C］.Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. ACM， 2012： 157-168.

［2］ Elberfeld M， Bafna V， Gamzu I， et al. On the approximability of reachability-preserving network orientations［J］. Internet Mathematics， 2011， 7（4）： 209-232.

［3］ Liu X， Wang B， Yang X. Efficiently anonymizing social networks with reachability preservation［C］.Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM，2013： 1613-1618.

［4］ WILKINSON B， ALLEN M.陆鑫达，译.并行程序设计［M］. 北京：机械工业出版社，2002.

中图分类号：TP301

文献标识码：A