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

摘要：

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

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

所属期刊栏目：44

分类号：TP399(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;陕西省自然科学基础研究计划

在线出版日期：2022-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：306-311