一种基于GN算法的动态图划分方法

• 作者: 罗晓霞 王佳 罗香玉 李嘉楠
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 动态图划分 GN算法 交叉边 负载均衡度
• 年，卷（期）: 2022,（2）
• 所属期刊栏目: 图形与图像
• 页码范围: 306-311
• 页数: 6页
• 分类号: TP399
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2022.02.016

摘要

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