基于邻域的大规模图数据动态分割算法

• 作者: 张晓媛 张珩 翟健
• 来源期刊: 计算机系统应用
• 关键词: 图数据 动态图 图分割 负载均衡
• 年，卷（期）: 2016,（9）
• 所属期刊栏目: 软件技术?算法
• 页码范围: 193-199
• 页数: 7页
• 字数: 5859字
• 语种: 中文
• DOI: 10.15888/j.cnki.csa.005338

摘要

随着图数据的规模日益增大，出现大量以动态图数据为基础的分布式处理需求，划分问题在动态图数据分布式处理领域尤为重要。对大规模动态图数据上的划分问题进行研究，根据图结构性质及动态图特点，提出并实现基于邻域的动态图分割算法。算法分为静态切分和动态调整两个阶段，其中基于割边算法整合现有最优化策略提出了大规模图数据的静态切割算法。在优化后的静态切割算法的基础上，根据图数据的动态扩张的特性提出动态分割算法。根据迁移顶点所达到的最小负载值进行顶点迁移，并在此基础上进行性能及割边控制优化操作。最后，改进算法在各类图数据集上进行了验证，验证的结果显示在平衡度和割边等指标上优化后的算法效果显著，提高了划分的合理性，并且在保证割边不增加的情况下提高了图分割的平衡度。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张珩	中国科学院软件研究所基础软件国家工程研究中心	52	651	11.0	24.0
5	翟健	中国科学院软件研究所互联网软件技术实验室	8	25	3.0	5.0
6	张晓媛	中国科学院软件研究所互联网软件技术实验室	1	3	1.0	1.0