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

摘要

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

主权项

一种基于顶点切割与社区聚集的大规模图划分方法，应用于包括网页数据和网络文献关系在内的大规模迭代图，包括以下步骤：（1）初始化划分集群，包括设定集群软硬件的参数，启动集群，划分算法代码部署；（2）定时检测划分节点，利用定时间隔的心跳检测，查看各个计算节点是否在线，确保集群运行正常，并将待划分图发送到集群中；（3）统计待划分图的顶点度数分布，得到该待划分图的分布特性，即其Power‑Law分布参数，根据该分布参数得到具体的顶点切割方案；（4）根据切割方案进行顶点切割，得到切割图；（5）获取切割完成后的图；（6）对切割之后的图迭代地进行标签传播处理；（7）获取标签传播图，并进行MGP划分，以巩固顶点切割以及社区聚类的效率；（8）重复步骤（3）至步骤（7）直到迭代次数达到预定次数。