On Effectively Finding Maximal Quasi-Cliques in Graphs

The problem of finding a maximum clique in a graph is prototypical for many clustering and similarity problems; however, in many real-world scenarios, the classical problem of finding a complete subgraph needs to be relaxed to finding an almost complete subgraph, a so-called quasi-clique. In this work, we demonstrate how two previously existing definitions of quasi-cliques can be unified and how the resulting, more general quasi-clique finding problem can be solved by extending two state-of-the-art stochastic local search algorithms for the classical maximum clique problem. Preliminary results for these algorithms applied to both, artificial and real-world problem instances demonstrate the usefulness of the new quasi-clique definition and the effectiveness of our algorithms. © 2008 Springer Berlin Heidelberg.