DisHAP:基于层次亲和聚类的分布式大图划分算法OA北大核心CSCDCSTPCD
DisHAP:A Distributed Partition Algorithm for Large Scale Graphs Based on Hierarchical Affinity Clustering
平衡图划分是改善并行图计算性能的关键.一个良好的划分算法应保证划分后的子图在负载均衡的前提下,减少子图之间的交互边(切割边)规模,从而减少网络通信.对此,本文设计一种基于层次亲和聚类的分布式大图划分算法(DisHAP).该算法采用亲和聚类的思想,将图初始划分为规模相等的k个子图;再将结果映射成顶点序列,以线性嵌入顺序处理节点,通过局部交换策略优化割边率;最后将DisHAP应用在MapReduce框架中,使用多种真实及理论图数据,与现有的大图划分算法做比较分析.以Twitter图为例,划分2,4,8,16,32个子区,相较于现有的大图划分算法(LDG,BLP,Spinner,Fennel,ParMetis及PSA-MIR算法),割边率减少1.7％～30.2％,说明了该算法的优越性.同时该算法具有良好的可扩展性,划分的子区数量及图的规模对划分时间具有较低的影响.
柳菁;李琪
绍兴文理学院计算机科学与工程系,浙江绍兴312000绍兴文理学院计算机科学与工程系,浙江绍兴312000
信息技术与安全科学
分布式大图划分层次聚类局部优化分布式图计算平衡划分
《电子学报》 2021 (10)
2002-2011,10
国家自然科学基金青年科学基金(No.62002226)
评论