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

doi:10.19678/j.issn.1000-3428.0054077

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

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

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

辽宁工程技术大学软件学院, 辽宁葫芦岛 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

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

摘要/Abstract

摘要： 为提高大数据平台下大规模图例的最大团问题求解效率，提出一种基于并行约束规划的最大团识别算法。通过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

中图分类号:

TP301

肖成龙, 聂紫阳, 王宁, 张重鹏, 王珊珊. 基于并行约束规划的最大团识别研究[J]. 计算机工程, 2020, 46(4): 53-59,69.

XIAO Chenglong, NIE Ziyang, WANG Ning, ZHANG Zhongpeng, WANG Shanshan. Research on Maximum Clique Identification Based on Parallel Constraint Programming[J]. Computer Engineering, 2020, 46(4): 53-59,69.

https://www.ecice06.com/CN/Y2020/V46/I4/53

图/表 8

20200414123652

20200414123657

20200414123700

20200414123704

20200414123707

20200414123712

20200414123715

20200414123719

参考文献 21

[1]	CHEN Ping,LIU Zhen,QIAO Xiuquan,et al.The parallel algorithm of clique and its application on data mining grid system[C]//Proceedings of 2009 IEEE International Conference on Network Infrastructure and Digital Content.Washington D.C.,USA:IEEE Press,2009:340-343.
[2]	ROSSI R A,GLEICH D F,GEBREMEDHIN A H,et al.Parallel maximum clique algorithms with applications to network analysis and storage[J].SIAM Journal on Scientific Computing,2013,37(5):589-616.
[3]	SEGUNDO P,ARTIEDA J.A novel clique formulation for the visual feature matching problem[J].Applied Intelligence,2015,43(2):325-342.
[4]	PATTABIRAMAN B,PATWARY M M A.Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detection[J].Internet Mathematics,2015,11(4/5):421-448.
[5]	WU Qinghua,HAO Jinkao.Solving the winner determination problem via a weighted maximum clique heuristic[J].Expert Systems with Applications,2015,42(1):355-365.
[6]	BELSOM A,SCHNEIDER M,FISCHER L,et al.Serum albumin domain structures in human blood serum by mass spectrometry and computational biology[J].Molecular and Cellular Proteomics,2016,15(3):1105-1116.
[7]	ZHOU Benda,YUE Qin,CHEN Minghua.Immune genetic algorithm based on uniform design sampling for solving maximum clique problem[J].Computer Engineering,2010,36(18):229-231.(in Chinese) 周本达,岳芹,陈明华.求解最大团问题的均匀设计抽样免疫遗传算法[J].计算机工程,2010,36(18):229-231.
[8]	XIANG J,GUO C,ABOULNAGA A.Scalable maximum clique computation using MapReduce[C]//Proceedings of the 29th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2013:74-85.
[9]	BRIGHEN A,SLIMANI H,REZGUI A,et al.Listing all maximal cliques in large graphs on vertex-centric model[J].The Journal of Supercomputing,2019,75:4918-4946.
[10]	WU Bin,YANG Shengqi,ZHAO Haizhou,et al.A distributed algorithm to enumerate all maximal cliques in MapReduce[C]//Proceedings of the 4th International Conference on Frontier of Computer Science and Technology.Washington D.C.,USA:IEEE Press,2009:45-51.
[11]	XIANG J,GUO C,ABOULNAGA A.Scalable maximum clique computation using MapReduce[C]//Proceedings of IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2013:74-85.
[12]	YIN Jun.Research of the method for solving maximum clique problem based on the graph partitioning on big data platform[D].Tianjin:Hebei University of Technology,2015.(in Chinese) 尹君.大数据平台下基于图划分的最大团问题求解方法研究[D].天津:河北工业大学,2015.
[13]	ZHOU Xu,ZHOU Yantao,OUYANG Aijia,et al.An efficient tile assembly model for maximum clique problem[J].Journal of Computer Research and Development,2014,51(6):1253-1262.(in Chinese) 周旭,周炎涛,欧阳艾嘉,等.一种最大团问题的Tile自组装高效模型[J].计算机研究与发展,2014,51(6):1253-1262.
[14]	NING Aibing,LIU Yanfang,WANG Yinglei.Reduction algorithm for maximum clique problem[J].Journal of Chinese Computer Systems,2013,34(5):1137-1140.(in Chinese) 宁爱兵,刘艳芳,王英磊.最大团问题降阶算法[J].小型微型计算机系统,2013,34(5):1137-1140.
[15]	NARENDRA J,ROCHART G,LORCA X.Choco:an open source Java constraint programming library[C]//Proceedings of Workshop on Open-Source Software for Integer and Constraint Programming.Washington D.C.,USA:IEEE Press,2008:1-6.
[16]	FREUDER E C.Progress towards the Holy Grail[J].Constraints,2017,23:158-171.
[17]	LI Li.Research on parallel algorithm for solving the largest cluster problem based on OpenCL[D].Wuhan:Wuhan University of Science and Technology,2016.(in Chinese)李锂.基于OpenCL求解最大团问题的并行算法研究[D].武汉:武汉科技大学,2016.
[18]	ABOULNAGA A,XIANG J,GUO C.Scalable maximum clique computation using MapReduce[C]//Proceedings of IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2013:74-85.
[19]	MA Zhiyuan,WANG Pengfei,WU Zhiqiang,et al.A method for solving the refractive index temperature coefficient empirical formula constants of optical glasses based on 1stOpt[J].Acta Photonica Sinica,2017,46(6):74-80.(in Chinese)马志远,王鹏飞,吴志强,等.基于1stOpt求解光学玻璃折射率温度系数经验公式常量的方法[J].光子学报,2017,46(6):74-80.
[20]	QingCloud[EB/OL].[2019-01-14].https://www.qingcloud.com/.
[21]	WU Q,HAO J K.A review on algorithms for maximum clique problems[J].European Journal of Operational Research,2015,242(3):693-709.

选择文件类型/文献管理软件名称

选择包含的内容

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

Research on Maximum Clique Identification Based on Parallel Constraint Programming

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 21

相关文章 15

编辑推荐

Metrics

本文评价

[1]	雷斗威, 何德彪, 罗敏, 彭聪. 基于AVX512的格密码高速并行实现[J]. 计算机工程, 2024, 50(2): 15-24.
[2]	彭世明, 林士飏, 贾硕, 杨苗会. 基于负载预测的多目标优化任务卸载策略[J]. 计算机工程, 2024, 50(1): 206-215.
[3]	刘向举, 赵犇, 方贤进, 徐杨洋. SDN中基于过程优化的动态负载均衡策略[J]. 计算机工程, 2023, 49(8): 137-145.
[4]	王其涵, 庞建民, 岳峰, 祝迪, 沈莉, 肖谦. 面向申威架构的KNN并行算法实现与优化[J]. 计算机工程, 2023, 49(5): 286-294.
[5]	夏立斌, 刘晓宇, 姜晓巍, 孙功星. 基于分布式数据集的并行计算框架内存优化方法[J]. 计算机工程, 2023, 49(4): 43-51.
[6]	房俊, 薛晓东, 周云亮. 基于深度生成模型的聚合查询区间估计方法[J]. 计算机工程, 2023, 49(11): 284-292, 301.
[7]	王晓峰, 于卓, 赵健, 曹泽轩. 大规模图例的最大团问题算法分析[J]. 计算机工程, 2022, 48(6): 182-192,199.
[8]	王奎宇, 宋晓勤, 缪娟娟, 张昕婷, 雷磊. 基于SDN的高性能QoS保障低轨道卫星星间路由算法[J]. 计算机工程, 2022, 48(5): 185-190,199.
[9]	贺鹏飞, 范鹏飞, 尹千慧, 王中训, 张桐敬, 梁大伟. 基于负载均衡算法的Hyperledger Fabric共识机制研究[J]. 计算机工程, 2022, 48(11): 170-176.
[10]	李亚朋, 庞建民, 徐金龙, 聂凯. 一种针对线性循环结构的非线性静态调度策略[J]. 计算机工程, 2022, 48(1): 155-162.
[11]	施凌鹏, 朱征, 周俊松, 李鑫, 李静. 面向微服务架构的云系统负载均衡机制[J]. 计算机工程, 2021, 47(9): 44-50,58.
[12]	左攀, 束永安. DCN中基于前馈神经网络的动态多路径负载均衡方法[J]. 计算机工程, 2021, 47(9): 113-119.
[13]	黄瑞, 金光浩, 李磊, 姜文超, 宋庆增. 轻量化神经网络加速器的设计与实现[J]. 计算机工程, 2021, 47(9): 185-190,196.
[14]	易培淮, 李卫东, 林韬, 邹佳恒, 邓子艳, 刘言. GPU在缪子快速模拟中的应用[J]. 计算机工程, 2021, 47(8): 100-108.
[15]	杨海竹, 孙长印, 吴维超, 徐文军. 毫米波微波网络基于匹配算法的小区关联方法[J]. 计算机工程, 2021, 47(8): 210-215,223.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Research on Maximum Clique Identification Based on Parallel Constraint Programming

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 21

相关文章 15

编辑推荐

Metrics

本文评价