Parallel multi-layer graph partitioning method for solving maximum clique problems

doi:10.11772/j.issn.1001-9081.2018040934

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (12): 3425-3432.DOI: 10.11772/j.issn.1001-9081.2018040934

Previous Articles Next Articles

Parallel multi-layer graph partitioning method for solving maximum clique problems

GU Junhua¹, HUO Shijie¹, WU Junyan¹, YIN Jun¹, ZHANG Suqi²

1. School of Artificial Intelligence, Hebei University of Technology, Tianjin 300401, China;
2. School of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China

Received:2018-05-07 Revised:2018-07-10 Online:2018-12-10 Published:2018-12-15
Contact: 张素琪
Supported by:
This work is partially supported by the Science and Technology Project of Tianjin (16ZXHLSF0023), the Basic Research Project of Tianjin (17JCTPJC55400), the Science and Technology Project of Hebei (17210305D), the Natural Science Foundation of Hebei (F2016202144).

求解最大团问题的并行多层图划分方法

顾军华¹, 霍士杰¹, 武君艳¹, 尹君¹, 张素琪²

1. 河北工业大学人工智能与数据科学学院, 天津 300401;
2. 天津商业大学信息工程学院, 天津 300134

通讯作者: 张素琪
作者简介:顾军华(1966-),男,河北赵县人,教授,博士,CCF会员,主要研究方向:智能信息处理、数据挖掘;霍士杰(1993-),男,河北石家庄人,硕士研究生,CCF会员,主要研究方向:数据挖掘、计算机仿真;武君艳(1994-),女,山西晋中人,硕士研究生,主要研究方向:数据挖掘、计算机仿真;尹君(1990-),女,陕西铜川人,硕士研究生,主要研究方向:数据挖掘;张素琪(1980-),女,河北邢台人,讲师,博士,CCF会员,主要研究方向:智能信息处理、数据挖掘。
基金资助:
天津市科技计划项目（16ZXHLSF0023）；天津市基础研究计划项目（17JCTPJC55400）；河北省科技计划项目（17210305D）；河北省自然科学基金资助项目（F2016202144）。

Abstract

Abstract: In big data environment, the mass of nodes in graph and the complexity of analysis bring forward higher requirement for the speed and accuracy of maximum clique problems. In order to solve the problems, a Parallel Multi-layer Graph Partitioning method for Solving Maximum Clique (PMGP_SMC) was proposed. Firstly, a new Multi-layer Graph Partitioning method (MGP) was proposed, the large-scale graph partitioning was executed to generate subgraphs while the clique structure of the original graph was maintained and not destroyed. Large-scale subgraphs were divided into multi-level graphs to further reduce the size of subgraphs. The graph computing framework of GraphX was used to achieve MGP to form a Parallel Multi-layer Graph Partitioning (PMGP) method. Then, according to the size of partitioned subgraph, the iteration number of Local Search algorithm Based on Penalty value (PBLS) was reduced, and the PBLS based on Speed optimization (SPBLS) was proposed to solve the maximum clique of each subgraph. Finally, PMGP method and SPBLS were combined to form PMGP_SMC. The large-scale dataset of Stanford was used for running test. The experimental results show that, the proposed PMGP reduces the maximum subgraph size by more than 100 times and the average subgraph size by 2 times compared with Parallel Single Graph Partitioning method (PSGP). Compared with PSGP for Solving Maximum Clique (PSGP_SMC), the proposed PMGP_SMC reduces the overall time by about 100 times, and its accuracy is consistent with that of Parallel Multi-layer Graph Partitioning for solving maximum clique based on Maximal Clique Enumeration (PMGP_MCE) in solving the maximum clique. The proposed PMGP_SMC can solve the maximum clique of large-scale graph quickly and accurately.

Key words: big data, maximum clique, Spark, Multi-layer Graph Partitioning method (MGP), fast local search algorithm

摘要： 在当今大数据环境下，针对图中节点的海量性和分析的复杂性对最大团问题的研究在速度和精度上都提出了更高要求的问题，提出求解最大团问题的并行多层图划分方法（PMGP_SMC）。首先，提出一种新的多层图划分（MGP）方法，在保持原有图的团结构不被破坏的情况下对大规模图例划分产生子图，并对规模较大的子图进行多层图划分，进一步缩小子图规模，并且应用GraphX图计算框架实现MGP，形成并行MGP（PMGP）方法；然后，依据划分后的子图规模，减少了惩罚值局部搜索算法（PBLS）的迭代次数，提出基于速度优化的PBLS（SPBLS）来求解划分后的各个子图的最大团；最后，将PMGP和SPBLS相结合形成PMGP_SMC。采用Stanford大规模数据集运行测试，实验结果表明，PMGP相比并行单层图划分方法（PSGP），求得的最大子图规模能缩小至原来的1/100，平均子图规模能缩小至原来的1/2；PMGP_SMC相比求解最大团问题的PSGP（PSGP_SMC），总体时间缩短至原来的1/100，并且PMGP_SMC求解最大团的精度和基于极大团枚举求解最大团问题的并行多层图划分方法（PMGP_MCE）一致。PMGP_SMC能够快速精准地求解大规模图例的最大团。

关键词: 大数据, 最大团, Spark, 多层图划分方法, 快速局部搜索算法

CLC Number:

TP305

GU Junhua, HUO Shijie, WU Junyan, YIN Jun, ZHANG Suqi. Parallel multi-layer graph partitioning method for solving maximum clique problems[J]. Journal of Computer Applications, 2018, 38(12): 3425-3432.

顾军华, 霍士杰, 武君艳, 尹君, 张素琪. 求解最大团问题的并行多层图划分方法[J]. 计算机应用, 2018, 38(12): 3425-3432.

References

[1] MICHAEL R G, DAVID S J. Computers and intractability:a guide to the theory of NP-completeness[M]. San Francisco:W. H. Freeman and Company,1979:17-38.
[2] SONKA M, HLAVAC V, BOYLE R. Image Processing, Analysis, and Machine Vision[M]. 4th edition. Boston:Springer, 2014:422-442.
[3] BELSOM A, SCHNEIDER M, FISCHER L, et al. Serum albumin domain structures in human blood serum by mass spectrometry and computational biology[J]. Molecular & Cellular Proteomics, 2016, 15(3):1105-1116.
[4] WESCOTT M P, KUFAREVA I, PAES C, et al. Signal transmission through the CXC chemokine receptor 4(CXCR4) transmembrane helices[J]. Proceedings of the National Academy of Sciences, 2016, 113(35):9928-9933.
[5] KIM J, HASTAK M. Social network analysis:characteristics of online social networks after a disaster[J]. International Journal of Information Management, 2018, 38(1):86-96.
[6] YIN S, ZHU X P, KAYNAK O. Improved PLS focused on key-performance-indicator-related fault diagnosis[J]. IEEE Transactions on Industrial Electronics, 2015, 62(3):1651-1658.
[7] NUGROHO A T, WU Z. Inexact Newton backtracking method for solving microwave tomography inverse problem[C]//Proceedings of the 2015 IEEE International Conference on Imaging Systems and Techniques. Piscataway, NJ:IEEE, 2015:1-6.
[8] KARIMI N, DAVOUDPOUR H. A branch and bound method for solving multi-factory supply chain scheduling with batch delivery[J]. Expert Systems with Applications, 2015, 42(1):238-245.
[9] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. The Bell System Technical Journal, 1970, 49(2):291-307.
[10] KUMAR R, MOSELEY B, VASSILVITSKⅡ S, et al. Fast greedy algorithms in MapReduce and streaming[C]//Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures. New York:ACM, 2015:1-10.
[11] MILLS K L, FILLIBEN J J, HAINES A L. Determining relative importance and effective settings for genetic algorithm control parameters[J]. Evolutionary Computation, 2015, 23(2):309-342.
[12] KERNIGHAN B W, LIN S. An efficient heuristic procedure for partitioning graphs[J]. The Bell System Technical Journal, 1970, 49(2):291-307.
[13] FIDUCCIA C M, MATTHEYSES R M. A linear-time heuristic for improving network partitions[C]//Proceeding of the 19th Design Automation Conference. Piscataway, NJ:IEEE, 1982:175-181.
[14] KARYPIS G, KUMAR V. A fast and high quality multilevel scheme for partitioning irregular graphs[J]. SIAM Journal on Scientific Computing, 1998, 20(1):359-392.
[15] WU B, YANG S Q, ZHAO H Z, 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. Piscataway, NJ:IEEE, 2009:45-51.
[16] XIANG J G, GUO C, ABOULNAGA A. Scalable maximum clique computation using MapReduce[C]//Proceedings of the 29th International Conference on Data Engineering. Piscataway, NJ:IEEE, 2013:74-85.
[17] SVENDSEN M, MUKHERJEE A P, TIRTHAPURA S. Mining maximal cliques from a large graph using MapReduce:tackling highly uneven subproblem sizes[J]. Journal of Parallel and Distributed Computing, 2015, 79/80:104-114.
[18] MUKHERJEE A P, TIRTHAPURA S. Enumerating maximal bicliques from a large graph using MapReduce[J]. IEEE Transactions on Services Computing, 2017, 10(5):771-784.
[19] LIU T, FANG Z, ZHAO C, et al. Parallelization of a series of extreme learning machine algorithms based on Spark[C]//Proceedings of the 2016 IEEE/ACIS 15th International Conference on Computer and Information Science. Piscataway, NJ:IEEE, 2016:1-5.
[20] 张素琪.案例推理关键技术研究及其在电信告警和故障诊断中的应用[D].天津:天津大学,2014:59-81..(ZHANG S Q. Research on the key technologies of case-based reasoning and its application in telecommunication alarm and fault diagnosis[D]. Tianjin:Tianjin University, 2014:59-81.)
[21] BENLIC U, HAO J K. Breakout local search for maximum clique problems[J]. Computers and Operations Research, 2013, 40(1):192-206.

Parallel multi-layer graph partitioning method for solving maximum clique problems

求解最大团问题的并行多层图划分方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	ZHOU Xiang, ZHAI Junhai, HUANG Yajie, SHEN Ruicai, HOU Yingzhen. Instance selection algorithm for big data based on random forest and voting mechanism [J]. Journal of Computer Applications, 2021, 41(1): 74-80.
[2]	CAO Cejun, LIU Ju. Overview of modeling method of emergency organization decision in disaster operations management [J]. Journal of Computer Applications, 2020, 40(7): 2142-2149.
[3]	ZHU Xiaojie, ZHAO Zihao, DU Yi. PiFlow: model driven big data pipeline framework [J]. Journal of Computer Applications, 2020, 40(6): 1638-1647.
[4]	GU Junhua, WANG Feng, QI Yongjun, SUN Zheran, TIAN Zepei, ZHANG Yajuan. Retrieval method of pulmonary nodule images based on multi-scale convolution feature fusion [J]. Journal of Computer Applications, 2020, 40(2): 561-565.
[5]	ZHANG Xiajie, ZHU Jinghua, CHEN Yang. Distributed rough set attribute reduction algorithm under Spark [J]. Journal of Computer Applications, 2020, 40(2): 518-523.
[6]	WU Wenli, LIU Guohua, ZHANG Junbao. Complexity analysis of functional query answering on big data [J]. Journal of Computer Applications, 2020, 40(2): 416-419.
[7]	LIU Bin, HE Jinrong, LI Yuancheng, HAN Hong. Apple price prediction method based on distributed neural network [J]. Journal of Computer Applications, 2020, 40(2): 369-374.
[8]	LI Ziying, SHI Zhenguo. Scheduling method for big data tasks [J]. Journal of Computer Applications, 2020, 40(10): 2923-2928.
[9]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[10]	CHENG Wenliang, WANG Zhihong, ZHOU Yu, GUO Yi, ZHAO Junfeng. Design of distributed computing framework for foreign exchange market monitoring [J]. Journal of Computer Applications, 2020, 40(1): 173-180.
[11]	ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms [J]. Journal of Computer Applications, 2019, 39(7): 1869-1882.
[12]	MA Jiangang, MA Yinglong. Semantic-driven learning and classification method of judicial documents [J]. Journal of Computer Applications, 2019, 39(6): 1696-1700.
[13]	JI Lina, CHEN Kai, YU Yanwei, SONG Peng, WANG Shuying, WANG Chenrui. Vehicle type mining and application analysis based on urban traffic big data [J]. Journal of Computer Applications, 2019, 39(5): 1343-1350.
[14]	ZHANG Yitian, YU Jiong, LU Liang, LI Ziyang. Task scheduling strategy based on data stream classification in Heron [J]. Journal of Computer Applications, 2019, 39(4): 1106-1116.
[15]	ZHU Yuelong, ZHU Xiaoxiao, WANG Jimin. Time series motif discovery algorithm based on subsequence full join and maximum clique [J]. Journal of Computer Applications, 2019, 39(2): 414-420.