计算机科学 ›› 2020, Vol. 47 ›› Issue (1): 72-78.doi: 10.11896/jsjkx.181102109

• 计算机科学理论 • 上一篇    下一篇

基于局部有限搜索的无向图近似最大团快速求解算法

钟茂生1,2,江超2,陶兰2,何雄2,罗远胜3   

  1. (江西师范大学计算机信息工程学院 南昌330022)1;
    (华东交通大学信息工程学院 南昌330013)2;
    (江西财经大学网络信息管理中心 南昌330013)3
  • 收稿日期:2018-11-15 发布日期:2020-01-19
  • 通讯作者: 钟茂生(zhongmaosheng@sina.com)
  • 基金资助:
    国家自然科学基金(61877031,61462027,61562031);江西省教育厅科技计划项目(GJJ170206)

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).

摘要: 无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。

关键词: 近似最大团, 局部有限搜索, 邻接子图, 求解算法, 悬挂子图

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

中图分类号: 

  • 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] 许少华 庞跃武 何新贵.
一种基于过程神经网络的动态系统控制信号求解模型和算法
Control Signal Solving Model and Algorithm of Dynamic System Based on Process Neural Network
计算机科学, 2012, 39(1): 159-161.
[2] 郭平 侯睿 杨国洲 范丽.
方位关系约束满足问题的推理求解

计算机科学, 2005, 32(8): 170-172.
[3] 黄文奇 陈端兵.
一种求解矩形块布局问题的拟物拟人算法

计算机科学, 2005, 32(11): 182-186.
[4] 徐周波 古天龙 赵岭忠.
网络最大流问题求解的符号ADD增广路径算法

计算机科学, 2005, 32(10): 38-40.
[5] 李韶华 张健.
Survey Propagation:一种求解SAT的高效算法

计算机科学, 2005, 32(1): 132-137.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!