动态图划分算法研究综述

Research on Dynamic Graph Partitioning Algorithms:A Survey

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.

Graph partitioning is the primary work of large-scale distributed graph processing,which plays a fundamental role in storage,query,processing,and mining of graph applications.Since graph data in the real world are always dynamic,the research of dynamic graph partitioning is a hot topic.This study systematically introduces the current algorithms for dynamic graph partitioning,which including streaming graph partitioning algorithm,incremental graph partitioning algorithm,and graph repartitioning algorithm.Firstly,the study introduces three different partitioning strategies,two different dynamic sources of graph and dynamic graph partitioning problem.Then,three different streaming graph partitioning algorithms are introduced,including hash algorithm,neighbor distribution-based algorithm,and novel algorithm.Secondly,two different incremental graph partitioning algorithms,single element incremental graph partitioning,and batch incremental graph partitioning are introduced.Thirdly,the repartitioning algorithm for graph structure and the repartitioning algorithm for graph computation are introduced,respectively.Finally,based on the analysis and comparison of the existing methods,the main challenges of dynamic graph partitioning are summarized and the corresponding research problems are proposed.