基于结构感知的大规模动态图划分算法研究

With the coming of the era of distributed graph data processing, the partitioning of large-scale dynamic graphs attracts much attention. The performance of distributed graph data processing is severely hindered because of poor partitioning results with massive cut edges. Most existing partitioning algorithms work in an iterative style for optimization and they usually make decisions based on local information. Therefore, the algorithms cause high time complexity while only generate suboptimal partitions. In fact, the structure of the graph itself has great impacts on partitioning. This project proposes the idea of partitioning graphs based on structure perception. It mainly concentrates on the following three issues. Firstly, it states how to describe the structure of a graph and how to capture the structure in a dynamic way. Secondly, it proposes a structure-awareness partitioning algorithm with fixed partitioning parameters. Thirdly, it investigates the relationships between graph structure and optimal partitioning parameters, so that the algorithm could select proper parameters according to the structure characteristics. In all, the project aims at theoretical achievements in dynamic graph structure description, dynamic structure perception and the law of structures' effects on graph partitioning. Based on the theoretical achievements, the project proposes a partitioning algorithm with graph structure-awareness which can greatly decrease the number of cut edges while keeping load balance. The research will lay solid theoretical and technical foundations for high performance distributed graph processing.

随着分布式图数据处理时代的到来，大规模动态图的划分问题引起研究者的广泛关注。然而，现有划分算法大多基于局部信息进行迭代式优化，时间复杂度高且划分效果不理想。划分产生的大量交叉边直接制约着分布式图数据处理的性能。图的结构对划分具有至关重要的影响，本项目提出基于结构感知进行大规模动态图划分的研究思路，首先研究以划分支配因子为中心的大规模动态图结构的描述方法与动态感知方法；其次，基于结构感知信息，研究划分参数给定条件下的大规模动态图划分算法；最后研究结构特征与划分参数选择之间的关系，以根据结构特征选择最佳划分参数，实现划分效果的综合优化。本项目拟在大规模动态图结构的描述与感知、结构特征对划分的影响规律方面形成创新性理论成果，并基于上述理论成果，形成基于结构感知的大规模动态图划分算法，在保证负载均衡的同时，有效减少交叉边数量。本项目的研究将为大规模动态图的高效分布式处理奠定重要的理论和技术基础。

近年来，大规模图数据处理获得广泛关注。典型的大规模图数据包括Web图数据（如网页链接关系图）、社交网络数据、生物信息网络数据等。这些图数据的顶点数量可达数十亿以上规模，已远远超出单台计算机的处理能力，分布式的图数据处理成为业界和学术界共同关注的热点话题。分布式图数据处理的基本前提是实现大规模图数据的有效划分。现有划分算法一般不区分图的具体结构。图自身结构与划分之间的关系尚缺乏深入研究。然而，图划分与其自身结构存在紧密关系。本项目研究基于图结构感知的划分算法。首先，本项目提出了一种针对动态图的增量式划分算法。该算法的主要特点是利用了图演化过程中的局部性特征，一段时间内新增子图呈现显著的社区结构，对新增子图进行社区发现，然后基于社区发现结果进行划分。该算法能够支持不断演化动态图的实时在线划分，具有时间复杂度低和划分质量高的特点。其次，在图的结构特征方面，本项目提出了一种改进的动态图社区演化关系分析方法，提高了社区演化关系刻画的完备性。同时，研究了时间片设置对社区演化关系分析质量的影响。最后，在图的存储方法方面，本项目提出了一种支持高效历史查询的动态图存储方法。该方法能够以较低的存储开销实现对动态图演化过程的完整刻画，是进行动态图社区结构演化过程分析的基础。项目研究结果数据验证了大规模动态图演化过程中增量子图存在的社区结构，为高效增量式动态图划分算法的研究提供了新途径。