一种基于顶点切割与社区聚集的大规模图划分方法

摘要

本发明公开了一种基于顶点切割（vertex cut）和社区聚集（community detection）的多层k路（k-way）图划分的方法，包括：根据统计分析特性考虑自然图本身的分布，提出相应的顶点切割算法将影响任务完成时间较大的一些顶点进行切割，然后利用基于标签传播的社区聚集算法迭代地将切割之后的图进行标签传播，将图的各个顶点的标签确定，即得到该顶点所在社区，最后用传统的多层k-way图划分算法进行划分，巩固效率。本发明对于大规模迭代图处理中的大部分应用，能够使得分布式计算节点满足负载均衡的同时，极大地减少相邻迭代处理步骤之间各个处理原节点由于迭代依赖必要而产生的额外通信量，大大地提高图处理框架的任务运行效率，增大任务的吞吐量。