作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (4): 53-59,69. doi: 10.19678/j.issn.1000-3428.0054077

• 人工智能与模式识别 • 上一篇    下一篇

基于并行约束规划的最大团识别研究

肖成龙, 聂紫阳, 王宁, 张重鹏, 王珊珊   

  1. 辽宁工程技术大学 软件学院, 辽宁 葫芦岛 125105
  • 收稿日期:2019-03-04 修回日期:2019-04-17 出版日期:2020-04-15 发布日期:2019-06-03
  • 作者简介:肖成龙(1984-),男,副教授、博士,主研方向为软硬件协同、专用处理器、深度学习;聂紫阳、王宁、张重鹏,硕士研究生;王珊珊,副教授、博士。
  • 基金资助:
    国家自然科学基金(61404069);辽宁省教育厅科学研究项目(LJYL048);辽宁省教育厅青年项目(LJ2017QL033)。

Research on Maximum Clique Identification Based on Parallel Constraint Programming

XIAO Chenglong, NIE Ziyang, WANG Ning, ZHANG Zhongpeng, WANG Shanshan   

  1. College of Software, Liaoning Technical University, Huludao, Liaoning 125105, China
  • Received:2019-03-04 Revised:2019-04-17 Online:2020-04-15 Published:2019-06-03

摘要: 为提高大数据平台下大规模图例的最大团问题求解效率,提出一种基于并行约束规划的最大团识别算法。通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图,并将其分配给Spark集群中的计算节点,每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解,实现最大团问题的并行化处理。引入时间预测模型,设计基于任务运行时间预测模型的并行图划分方法,从而有效解决计算节点的负载均衡问题。实验结果表明,与基于BMC图划分策略的最大团并行识别算法相比,该算法具有更高的求解效率,可取得近似线性的加速比。

关键词: 最大团问题, 约束规划, 负载均衡, 并行计算, BMT图划分策略

Abstract: To improve the efficiency of solving the Maximum Clique Problem(MCP) of large-scale legends on big data platforms,this paper proposes a maximum clique identification algorithm based on parallel constraint programming.The BMT graph division strategy is used to divide a complex graph into several sub-graphs,and the sub-graphs are assigned to computing nodes in the Spark cluster for independent calculation.Each computing node in the cluster uses the constraint programming method to model and solve the sub-problems generated by the segmentation.Thus,the parallel processing of the MCP can be realized.Secondly,a parallel graph partitioning method is designed based on the prediction model of task running time.So,the load balancing problem of computing nodes can be effectively solved.Experimental results show that compared with the identification method for maximum clique based on BMC graph division,the proposed algorithm is more efficient,and can obtain a nearly linear speed-up.

Key words: Maximum Clique Problem(MCP), constraint programming, load balancing, parallel computing, BMT graph division strategy

中图分类号: