摘要
随着图规模的急剧增长,对动态图进行实时处理的需求日益增加。大多现有的算法针对静态图划分是有效的,直接用其处理动态图会带来较大的通信开销。针对该问题,提出一种基于GN算法的动态图划分方法。首先收集一段时间内加入动态图中的顶点;然后,利用GN算法对这些新加入的顶点进行预划分,产生若干个内部联系紧密的社区;最后,将预划分产生的社区结果插入到已经划分好的当前图中。实验从交叉边数和负载均衡度两方面将该方法与传统流式划分方法进行比较,结果表明,在公开数据集上,该方法的交叉边数降低了13%,负载均衡度减少了42.3%。由此可见,该方法的划分质量明显优于传统的流式划分方法。
With the rapid growth of graph scale,the demand for real-time processing of dynamic graphs is increasing.Most of the existing algorithms are effective for static graph partitioning,but directly using them to process dynamic graphs will bring greater communication overheads.To solve this problem,a dynamic graph partitioning method based on GN algorithm is proposed.Firstly,the vertices to be inserted in the dynamic graph over a period of time are collected.Then,the GN algorithm is used to pre-partition these newly inserted vertices to generate several internally connected communities.Finally,the community results generated by the pre-partitioning are inserted into the current graph that has been partitioned.Through experiments,the proposed method is compared with the traditional streaming partitioning method in terms of crossed edges and load balance.The results show that,on the public datasets,The proposed method can reduce the number of crossed edges by 13%,and the load balance by 42.3%.It can be seen that,compared with the streaming partitioning method,the proposed method can significantly improve the quality of dynamic graph partitioning.
作者
罗晓霞
王佳
罗香玉
李嘉楠
LUO Xiao-xia;WANG Jia;LUO Xiang-yu;LI Jia-nan(College of Computer Science and Technology,Xi’an University of Science and Technology,Xi’an 710054,China)
出处
《计算机工程与科学》
CSCD
北大核心
2022年第2期306-311,共6页
Computer Engineering & Science
基金
国家自然科学基金(61702408,51634007)
陕西省自然科学基础研究计划(2019JM-020)。
关键词
动态图划分
GN算法
交叉边
负载均衡度
dynamic graph partitioning
GN algorithm
crossed edge
load balance
