Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (1): 72-78.doi: 10.11896/jsjkx.181102109

• Computer Science Theory • Previous Articles     Next Articles

Quick Algorithm to Find an Approximate Maximum Clique in Undirected Graph by Using Local-limited Search Strategy

ZHONG Mao-sheng1,2,JIANG Chao2,TAO Lan2,HE Xiong2,LUO Yuan-sheng3   

  1. (School of Computer & Information Engineering,Jiangxi Normal University,Nanchang 330022,China)1;
    (School of Information Engineering,East China Jiaotong University,Nanchang 330013,China)2;
    (Center of Network Information Management,Jiangxi University of Finance and Economics,Nanchang 330013,China)3
  • Received:2018-11-15 Published:2020-01-19
  • About author:ZHONG Mao-sheng,Ph.D,professor,master supervisor.His research intere-sts include graph theory,algorithm design,social network and natural language processing.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61877031,61462027,61562031) and Science and Technology Project of Jiangxi Education Departmen (GJJ170206).

PDF (PC)

1082

Abstract: Finding the maximum clique is a well-known NP-complete problem,and the classical algorithms of finding the maximum clique basically use the exact search strategy.Because of the complexity of the NP-complete problem,these algorithms may only be applicable to some special small scale graphs,which are difficult to applied to the complex graphs with large scale vertices and edges.In this paper,aiming at the problem of executing much redundant and ineffective search after finding a maximum clique by using these classical algorithms,this paper proposed a new algorithm based on the partition & recursive and the local-limited search strategy to find a maximum clique in an undirected graph,that is,partitioning a graph into an adjacent sub-graph and suspended sub-graph,then finding recursively the maximum clique of the adjacent sub-graph and that of parts of sub-graph of the suspended sub-graph by setting a search range control function.The experiments in a benchmark data set DIMACS show that this algorithm can find the maximum clique in most of the experimental data,can find the approximate maximum clique in other experimental data that is very close to the maximum clique,and it is much faster than these classical algorithm.Therefore,in many cases with non-precise requirements for the maximum clique,this algorithm has better application value.

Key words: Adjacent sub-graph, Approximate maximum clique, Finding algorithm, Local-limited search, Suspended sub-graph

CLC Number: 

  • TP301.6
[1]LUCE R D,PERRY A D.A method of matrix analysis of group structure [J].Psychometrika,1949,14(2):95-116.
[2]GAREY M R,JOHNSON D S.Computers and Intractability:A guide to the Theory of NP-Completeness [M]∥Computers and Intractability:A Guide to the Theory of NP-Completeness.New York:Freeman,1979.
[3]PATRICK P.Exact Algorithms for Maximum Clique:A Computational Study[J].Algorithms,2012,5(4):545-587.
[4]PAULL M C,UNGER S H.Minimizing the Number of States in Incompletely Specified Sequential Switching Functions[J].IRE Transactions on Electronic Computers,1959,EC-8(3):356-367.
[5]Bonner R E.On some clustering techniques[J].IBM Journal of Research and Development,1964,8(1):22-32.
[6]BEDNAREK A R,TAULBEE O E.On maximal chains[J].Re- vue Roumaine des Mathematiques Pures et Appliquees,1966,11(1):23-25.
[7]PARDOLOS P M,RODGERS G P.A branch and bound algorithm for the maximum clique problem[J].Computer & OR,1992,19:363-375.
[8]TOMITA E,SEKI T.An efficient branch-and-bound algorithm for finding a maximum clique and computational experiments[M]∥Discrete Mathematics and Theoretical Computer Science.Berlin:Springer,2003:278-289.
[9]KONC J.An improved branch and bound algorithm for the maximum clique problem[J].MATCH Commun.in Mathematical and in Computer Chemistry,2007,58(3):569-590.
[10]SEGUNDO P S,TAPIA C.A new Implicit Branching Strategy for Exact Maximum Clique[C]∥XXII IEEE International Conference onTools with Artificial Intelligence (ICTAI).IEEE,2010:352-357.
[11]TOMITA E,SUTANI Y,HIGASHI T,et al.A Simple and Faster Branch-and-Bound Algorithm for Finding Maximum Clique[M]∥WALCOM:Algorithms and Computation.Berlin:Sprin-ger,2010:191-203.
[12]PATTABIRAMAN B,PATWARY M M A,GEBREMEDHIN A H,et al.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.
[13]MIKHAIL B,BORIS G,EVGENY M,et al.Improvements to MCS algorithm for the maximum clique problem[J].Journal of Combinatorial Optimization,2014,27(2):397-416.
[14]MCCREESH C,PROSSER P.Reducing the Branching in a Branch and Bound Algorithm for the Maximum Clique Problem[C]∥International Conference on Principles and Practice of Constraint Programming.Cham:Springer,2014.
[15]ÖSTERG;ÅRD,PATRIC R J.A fast algorithm for the maximum clique problem[M].Elsevier Science Publishers B.V.,2002.
[16]RÉGIN J C.Using Constraint Programming to Solve the Maximum Clique Problem[C]∥International Conference on Principles & Practice of Constraint Programming.Springer Berlin Heidelberg,2003.
[17]LI C M,QUAN Z.An Efficient Branch-and-Bound Algorithm Based on MaxSAT for the Maximum Clique Problem[C]∥Twenty-fourth Aaai Conference on Artificial Intelligence.DBLP,2010.
[18]LI C M,FANG Z,XU K.Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem[C]∥2013 IEEE 25th International Conference on Tools with Artificial Intelligence.IEEE,2014.
[19]BOMZE I M,BUDINICH M,PARDALOS P M,et al.The maximum clique problem [M]∥Handbook of Combinatorial Optimization 4.Kluwer Academic Publishers,1999:1-74.
[20]FEO T A,RESENDE M G C,SMITH S H.A Greedy Randomi- zed Adaptive Search Procedure for Maximum Independent Set[J].Operations Research,1994,42(5):860-878.
[21]BUI T N,EPPLEY P H.A Hybrid Genetic Algorithm for the Maximum Clique Problem[C]∥International Conference on Genetic Algorithms.DBLP,1995.
[22]MARCHIORI E.Genetic,Iterated and Multistart Local Search for the Maximum Clique Problem[C]∥Applications of Evolutionary Computing,EvoWorkshops 2002.Berlin:Springer,2002.
[23] ZHANG Q,SUN J,TSANG E.An Evolutionary Algorithm With Guided Mutation for the Maximum Clique Problem[J].IEEE Transactions on Evolutionary Computation,2005,9(2):192-200.
[24]BUI T N,JR J R R.Finding Maximum Cliques with Distributed Ants[J].Gecco Lecture Notes in Computer Science,2004,3102:24-35.
[25]YIN H,SONG H.The Research of Ant Colony Optimization Algorithm for Maximum Clique Problem[J].Journal of University of South China(Science and Technology),2017,31(3):81-85.
[26]SEGUNDO P S,DIEGO R L,JIMÉNEZ A.An exact bit-parallel algorithm for the maximum clique problem[J].Computers & Operations Research,2011,38:571-581.
[27]XIANG J,GUO C,ABOULNAGA A.Scalable maximum clique computation using MapReduce[C]∥2013 IEEE 29th International Conference on Data Engineering (ICDE).IEEE,2013.
[28]MCCREESH C,PROSSER P.Multi-Threading a State-of-the- Art Maximum Clique Algorithm[J].Algorithms,2013,6(4):618-635.
[29]GU J H,HUO S J,WU J Y,et al.Parallel multi-layer graph partitioning method for solving maximum clique problems[J].Journal of Computer Applications,2018,38(12):3425-3432.
[30]MCCREESH C,PROSSER P.The Shape of the Search Tree for the Maximum Clique Problem,and the Implications for Parallel Branch and Bound[J].Acm Transactions on Parallel Computing,2014,2(1):1-27.
[31]ZHONG S,XIE L.An Algorithm Computing the Maximum Clique in a Graph[J].Journal Of Software,1999,10(3):288-292.
[32]LI Y.Genetic algorithm in DNA computing:A solution to the maximal clique problem[J].Chinese Science Bulletin,2004,49(9):967.
[33]ZHOU X D,SUN C Y,LI W J.Solving Maximum Clique Problem by MEC[C]∥Advance of China Artificial Intelligence (2003).Beijing:Beijing University of Post and Telecommunication,2003.
[34]JIA X F,GUO T H,XU X X.A New Algotithm for the Maximum Clique Problem[J].Journal of North University of China(Natural Science Edition),2006,27(2):180-182.
[35]HE K,ZOU S H,ZHOU J R.Enumerating maximal cliques in large sparse graphs[J].Journal of Huazhong & Technology (Natural Science Edition),2017,45(12):1-6.
[36]HUANG F,NING A B,LIU Z M,et al.Measure and Conquer Approach for the Maximum Vertex Weightet Clique Problem[J].Mathematical Theory and Applications,2017,37(2):97-104.
[1] SHAO Zi-hao, YANG Shi-yu, MA Guo-jie. Foundation of Indoor Information Services:A Survey of Low-cost Localization Techniques [J]. Computer Science, 2022, 49(9): 228-235.
[2] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[3] LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[4] HU Cong, HE Xiao-hui, SHAO Fa-ming, ZHANG Yan-wu, LU Guan-lin, WANG Jin-kang. Traffic Sign Detection Based on MSERs and SVM [J]. Computer Science, 2022, 49(6A): 325-330.
[5] YANG Jian-nan, ZHANG Fan. Classification Method for Small Crops Combining Dual Attention Mechanisms and Hierarchical Network Structure [J]. Computer Science, 2022, 49(6A): 353-357.
[6] ZHANG Jia-hao, LIU Feng, QI Jia-yin. Lightweight Micro-expression Recognition Architecture Based on Bottleneck Transformer [J]. Computer Science, 2022, 49(6A): 370-377.
[7] WANG Fang-hong, FAN Xing-gang, YANG Jing-jing, ZHOU Jie, WANG De-en. Strong Barrier Construction Algorithm Based on Adjustment of Directional Sensing Area [J]. Computer Science, 2022, 49(6A): 612-618.
[8] ZHANG Zhi-long, SHI Xian-jun, QIN Yu-feng. Diagnosis Strategy Optimization Method Based on Improved Quasi Depth Algorithm [J]. Computer Science, 2022, 49(6A): 729-732.
[9] GAO Yuan-hao, LUO Xiao-qing, ZHANG Zhan-cheng. Infrared and Visible Image Fusion Based on Feature Separation [J]. Computer Science, 2022, 49(5): 58-63.
[10] LIU Yang, LI Fan-zhang. Fiber Bundle Meta-learning Algorithm Based on Variational Bayes [J]. Computer Science, 2022, 49(3): 225-231.
[11] QIAO Jie, CAI Rui-chu, HAO Zhi-feng. Mining Causality via Information Bottleneck [J]. Computer Science, 2022, 49(2): 198-203.
[12] ZHAO Xue-lei, JI Xin-sheng, LIU Shu-xin, LI Ying-le, LI Hai-tao. Link Prediction Method for Directed Networks Based on Path Connection Strength [J]. Computer Science, 2022, 49(2): 216-222.
[13] WEI Xin, FENG Feng. Optimization of Empire Competition Algorithm Based on Gauss-Cauchy Mutation [J]. Computer Science, 2021, 48(11A): 142-146.
[14] WANG You-wei, ZHU Chen, ZHU Jian-ming, LI Yang, FENG Li-zhou, LIU Jiang-chun. User Interest Dictionary and LSTM Based Method for Personalized Emotion Classification [J]. Computer Science, 2021, 48(11A): 251-257.
[15] XIAO Man, LI Wei-dong. Semi-online Algorithms for Mixed Ring with Two Nodes [J]. Computer Science, 2021, 48(11A): 441-445.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.