计算机工程与科学

作者：罗晓霞, 王佳, 罗香玉, 李嘉楠

单位：（西安科技大学计算机科学与技术学院，陕西 西安 710054）

关键词：动态图划分,GN算法,交叉边,负载均衡度,

基金：国家自然科学基金（61702408,51634007）；陕西省自然科学基础研究计划（2019JM-020）

随着图规模的急剧增长，对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的，直接用其处理动态图会带来较大的通信开销。针对该问题，提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点；然后，利用GN算法对这些新加入的顶点进行预划分，产生若干个内部联系紧密的社区；最后，将预划分产生的社区结果插入到已经划分好的当前图中。实验从交叉边数和负载均衡度两方面将该方法与传统流式划分方法进行比较，结果表明，在公开数据集上，该方法的交叉边数降低了13%，负载均衡度减少了42.3%。由此可见，该方法的划分质量明显优于传统的流式划分方法。

来源：2022年第2期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2022年第2期