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

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.