The Optimization Of Maximal Clique Enumeration In Real-world Graphs

Graph could represent serval scenarios in the real world.The real-world graphs grow too big,and how to extract useful information from these graphs has become an important topic.Clique is a basic structure in graph and it is also a dense subgraph.Maximal Clique Enumeration is an important problem in graph theory,which focuses on finding all maximal cliques.The problem also has many applicable situations.Most state-of-the-art algorithms adopt graph partition to solve this problem.But the subgraphs after partitioning are mostly dense.And all current algorithms don't consider this phenomenon.They use “down-to-top” policy to enumerate all maximal cliques,which is inefficient in these dense subgraphs.Using a different enumeration strategy like “top-to-down”,a new algorithm BKrcd is proposed.BKrcd considers the input graph as a clique already,then removes the not fully connected vertices to get a real clique.Because BKrcd has a different suitable situation with classic ones,so a judgement between them is required to ensure the performance of different algorithms.With the judgement,a new hybrid approach could be implemented.On the other hand,the space complexity of the maximal clique enumeration is also high.It is necessary to maintain multiple sets each time the algorithm invokes recursive call,so,an efficent data structure can effectively reduce the memory space during the enumeration.With experiments on real real-world graphs,it can be verified that the new algorithm greatly improves the performance of the maximal clique enumeration in practical settings at most three times.