大数据时代,很多问题的底层数据模型是顶点或边的数据规模达到千万甚至上亿级别,且顶点和边实时变化的大规模动态图,例如,社交网络图、Web网页图等等。为了高效地进行大规模动态图的分布式/并行计算,必须对大规模动态图进行均衡合理划分,高效的大规模动态图划分是高效的大规模动态图分布式/并行计算的基础和前提。一般而言,高效的大规模动态图划分算法需要满足以下3个要求:1)划分的各分区间的通信代价尽可能小;2)各分区内的顶点/边的数量应尽可能均衡;3)大规模动态图划分算法是大规模动态图分布式/并行计算的预处理,所以大规模动态图划分算法应具有较好的时间性能。由于大规模动态图划分问题的复杂性,它是一个亟待解决的NP难问题。近年来,许多学者开始关注并研究大规模动态图划分问题,也开始涌现了一些创新性的大规模动态图划分算法,但是现有算法普遍存在以下缺陷:1)算法时间性能有待于提高;2)算法不能实时应对大规模动态图中边/顶点的变化;3)现有的算法仅考虑了各个分区上顶点/边的均衡问题,没有考虑动态图中各分区的活跃顶点/边在图计算中的均衡问题;4)算法需要较大的辅助空间。因此,创新研究与实现高效的大规模动态图划分算法,具有重要的理论与现实意义。论文选题来源于国家自然科学基金面上项目,创新研究并实现新的高效的大规模动态图处理框架及划分算法。针对现有算法的缺陷,本文提出了一种高效的大规模动态图处理框架DynGraphX,并基于该框架,提出了一种基于图中顶点中心性的哈希大规模动态图分布式划分算法CBH-DGP。论文的主要工作及创新如下:1)提出了一种新的顶点中心性,即一个顶点在网络中的重要程度。顶点中心性度量方法,它能高效实时地识别大规模动态图中的活跃高中心性顶点;2)提出了一种基于顶点中心性的边散列策略,将活跃的中心顶点尽量散列开,以避免大规模动态图划分计算过程中,各分区上顶点的计算量不均衡问题;3)针对现在尚无公开的适合大规模动态图处理框架问题,基于大规模静态图处理框架GraphX,创新设计并实现了一种新的高效的大规模动态图处理框架DynGraphX。并基于该框架设计与实现了高效的分布式大规模动态图划分算法CBHDGP;4)在大量的大规模动态图数据集上,对所提出的大规模动态图处理框架DynGraphX,以及所提出并实现的大规模动态图分布式划分算法CBH-DGP进行了较充分地仿真实验。大量的实验结果表明:所提出的大规模动态图处理框架DynGraphX可行、高效;所提出并实现的大规模动态图分布式划分算法CBH-DGP优于目前最好的大规模动态图划分算法,其划分质量高,划分速度快,并且可显著提高大规模动态图计算性能。目前算法还存在未充分考虑有向图结构特征和低中心性顶点之间的连接关系等问题。作者后期将进一步改进与完善当前算法,充分考虑有向图结构,使之能在有向图上有更好的划分质量。并且充分考虑低中心性顶点之间的连接关系,进一步降低通信代价。