面向增量的大规模图划分方法研究

摘要

针对现阶段图划分技术仍主要针对静态图划分，无法满足图的动态变化，提出一种面向增量的大规模图划分算法。首先，该算法在增量图划分阶段分析了增量与子图的关联性；其次，同时计算了紧密度和各个子图的负载值，赋予权重，根据权重之和判定增量节点或者增量边应该进入哪个子图，保证子图之间的低耦合和子图内部的高内聚以及各个子图的负载值近似相等实现负载均衡；最后，通过实验得出该方法可以在增量图划分时均衡各子图的负载。