基于标签传播与沙丘猫优化的属性图划分算法

作     者：崔焕庆 吴一凡 董柯桢 周升庆 

作者机构：山东科技大学计算机科学与工程学院 高效能服务器和存储技术国家重点实验室 齐鲁工业大学(山东省科学院)山东省人工智能研究院 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2024年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：山东省自然科学基金联合基金“分布式图神经网络异构加速平台”(No.ZR2022MF274) “多元算力架构下大规模人工智能模型协同分布式技术研究”(No.ZR2023LZH009) 教育部人文社会科学研究规划基金(23YJAZH192) 

主　　题：图划分 属性图 负载均衡 标签传播 沙丘猫优化算法 

摘      要：图在社交网络、通信网络等领域有着广泛应用，而且随着图规模日益增长，分布式图处理系统成为处理、分析大规模图数据的主要手段。图划分算法是此类系统的基础。目前提出的图划分算法通常假定顶点和边无属性，在对属性图进行划分时，易出现负载不均衡的问题。为此，本文将负载均衡分为图规模均衡和存储容量均衡，将属性图划分问题建模为一个带约束的单目标优化问题，进而提出一种基于标签传播和沙丘猫优化的属性图划分算法。该算法首先利用标签传播算法将图进行均匀划分，使划分结果达到图规模和存储容量上的负载均衡；然后改进了沙丘猫优化算法，使其能够求解组合优化问题，并基于改进的沙丘猫优化算法求解最优顶点迁移策略，以优化分区质量，实现在负载均衡的基础上达到最小化割边率的目标。实验结果显示，相较于基线算法，本文提出的算法在存储容量负载均衡率上最多降低了33%，同时在割边率和图规模负载均衡率方面与基线算法的差距均保持在9%以内。此外，该算法在真实属性图结构上也展现出了良好的可扩展性。