异构集群下基于标签传播的大规模图划分算法

近年来,大规模图数据处理在众多领域得到广泛应用,图划分算法是分布式图计算系统的基础,但大规模图在异构集群中的划分尚未得到充分研究。为此,针对异构集群,提出基于标签传播的大规模图划分算法(heterogeneous label propagation, HLP),根据计算节点负载能力进行图划分,以实现负载均衡和边割率最小化为目标。HLP算法规避了传统标签传播中顶点迁移的步骤,提高了算法效率。实验结果表明,HLP算法在分区质量以及划分效率方面均有较好表现。