软件学报

作者：李贺，刘延娜，杨舒琪，黄健斌，乔少杰

单位：李贺，西安电子科技大学 计算机科学与技术学院, 陕西 西安 71012611,刘延娜，西安电子科技大学 计算机科学与技术学院, 陕西 西安 71012602,杨舒琪，西安电子科技大学 计算机科学与技术学院, 陕西 西安 71012603,黄健斌，西安电子科技大学 计算机科学与技术学院, 陕西 西安 71012604,乔少杰，成都信息工程大学 软件工程学院, 四川 成都 61010305

关键词：图划分;局部优化;动态增量图划分算法

基金：国家自然科学基金(61602354, 61876138)

图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上. 图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划分结果. 提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题. 在ED-IDGP算法中, 设计实时处理4种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量. 在ED-IDGP的局部优化器中, 利用基于改进标签传播算法的顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分区中做优化. 在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.

来源：2024年第4期

《软件学报》期刊编辑部

查看软件学报杂志2024年第4期