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

摘要

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

主权项

一种基于顶点切割与社区聚集的大规模图划分方法，应用于包括网页数据和网络文献关系在内的大规模迭代图，包括以下步骤：(1)初始化划分集群，包括设定集群软硬件的参数，启动集群，划分算法代码部署；(2)定时检测划分节点，利用定时间隔的心跳检测，查看各个计算节点是否在线，确保集群运行正常，并将待划分图发送到集群中；(3)统计待划分图的顶点度数分布，得到该待划分图的分布特性，即其Power‑Law分布参数，根据该分布参数得到具体的顶点切割方案；(4)根据切割方案进行顶点切割，得到切割图；(5)获取切割完成后的图；(6)对切割之后的图迭代地进行标签传播处理；(7)获取标签传播图，并进行MGP划分，以巩固顶点切割以及社区聚类的效率；(8)重复步骤(3)至步骤(7)直到迭代次数达到预定次数；其中，所述步骤(4)具体包括：(4‑1)初始化参数，包括要切割的顶点集V、顶点之间的关联，即边集E、已经分配的边集E'和切割的顶点集合标号，也即集群的节点集合K＝{1,2,…,k},对顶点为u，v的任意边，即(u,v)←e，初始化将顶点u已经被放置的所有的节点的集合初始化为空集，且(4‑2)读取所述顶点为u，v的边，对其两顶点的已分配集合即A(u)，A(v)做出如下决策：若两者均非空且无交集，则选择两者并集中负载最小的一个节点作为顶点分割后将要分配到的节点；若两者中有一个为空，则选择不为空集合中负载最小的节点；若两者均不为空且有交集时，则选择交集中负载最小的节点；(4‑3)根据上一步骤的决策进行顶点切割，也即将顶点切割出一个镜像，连同该边连着的另一个顶点，一同分配到步骤(4‑2)中决策所选择的计算节点中；(4‑4)动态更新顶点的已分配集合A(u)，A(v)，作为下一次分配的输入参数；(4‑5)重复执行步骤(4‑2)至(4‑4)，直到所有的顶点完成切割及所在的边完成分配，即可获得切割完成之后的分布式图；(4‑6)整理切割完毕之后的图，作为标签传播的输入。