计算机工程

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

单位：1. 山东科技大学计算机科学与工程学院，山东 青岛 2665902. 高效能服务器和存储技术国家重点实验室，山东 济南 2500143. 齐鲁工业大学(山东省科学院)山东省人工智能研究院，山东 济南 250014

关键词：图划分,属性图,负载均衡,标签传播,沙丘猫群优化算法

基金：山东省自然科学基金联合基金(ZR2022MF274); 山东省自然科学基金联合基金(ZR2023LZH009); 教育部人文社会科学研究规划基金(23YJAZH192)

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

来源：2025年第12期

《计算机工程》期刊编辑部

查看计算机工程杂志2025年第12期