On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology

Abstract

The efficient enumeration of maximal cliques has applications in microarray analysis and a number of other foundational problems of computational biology. In this paper, we analyze and test existing maximal clique enumeration algorithms for various classes of graphs. The classic branch and bound algorithm of Bron and Kerbosch proves to be relatively fast for sparse graphs, but slows considerably as edge density increases. Attempts to improve this algorithm are discussed. Experimental results demonstrate the difficulty of making improvements, especially when analyzing the overlap between cliques. Novel strategies for maximal clique enumeration algorithms are also described and placed in the context of ongoing research.