摘要
随着网络的快速发展，以网络为载体的信息量迅速增长，使得图的规模也随之扩大。由于大规模图数据无法使用单机环境进行处理，因此分布式图计算应运而生。分布式图计算需要将图数据合理地分布到每个节点，对图进行合理划分是实现分布式图计算的前提。现实世界的图处于不断的动态演化之中，如何对动态图进行合理划分是当前的一个研究热点。针对动态图划分问题，本文的主要研究内容如下: 首先，研究新增图社区性对动态图划分质量的影响。将给定数量的动态图中更新的顶点看成一张新增图，采用不同的社区发现算法对其进行划分，得到模块度不同的子图。通过实验，将使用不同社区发现算法产生的划分结果进行对比，结果表明，新增图划分后的模块度越大，社区性越强，对动态图的划分质量越好。由此证明，新增图的社区性强弱影响动态图的划分质量，为下一步设计动态图划分方法奠定了基础。 其次，针对动态图划分问题，提出了一种基于社区发现的划分方法。其基本思想是收集给定数量的图更新操作，对于顶点的加入操作，利用社区发现算法对这些顶点进行预划分，将预划分产生的社区结果插入到已经划分好的当前图中，其余的顶点删除、边的加入/删除操作，分别根据收集的信息依次更新。在公开数据集上进行实验，从交叉边数和负载均衡度两方面将本方法与传统流式划分方法进行比较，结果表明，本方法的交叉边数降低了13％，负载均衡度减少了42.3％。由此可得，本方法的划分质量明显优于传统的流式划分方法，能够对动态图进行高效处理，降低子图之间的通信开销。 最后，为了对动态图的划分结果进一步优化，使划分后的子图内部联系紧密，子图之间耦合度低，又避免对整个动态图重新划分，提出了一种基于模拟退火的动态图顶点更新方法。传统顶点更新方法仅根据相邻节点判断顶点位置是否转移，会造成局部最优。本方法在传统顶点更新方法基础上加入了随机扰动的因素，通过对能量函数、更新概率、冷却计划的设计，避免顶点更新陷入局部最优的后果，使得各个子图之间的交叉边数最少，达到全局最优的效果。通过实验，将本方法与传统的顶点更新方法和基于社区发现的动态图划分方法进行比较，结果表明，本方法比传统顶点更新方法交叉边数降低了12.4％，负载均衡度减少了11.7％，比基于社区发现的动态图划分方法交叉边数降低了9.3％，负载均衡度减少了2.2％，由此可得，优化后的方法只通过部分顶点位置更新实现对动态图的划分，能够有效避免对整个动态图进行重新划分，提高了图的划分质量。
NETL