Exact approaches for finding maximum quasi-cliques and dense clusters/subgraphs

Abstract: The concept of a clique is used in a number of application areas due to its elegance and inherent ability to logically represent cohesive subgroups  and clusters, of “tightly knit” elements (i.e., nodes). However, in many real-life applications, using cliques for discovering large cohesive clusters is impractical due to the fact that the definition of a clique is rather idealistic and, thus, can be too limiting. Consequently, a number of clique relaxation ideas and models have appeared in recent years. In particular, the concept of a quasi-clique is perhaps one of the most popular models in the literature. In this talk, we consider two versions of the quasi-clique concept, namely, an edge-based and a degree-based quasi-clique. We briefly discuss related computational complexity issues, and then focus on exact integer programming based approaches for finding maximum quasi-cliques. The developed approaches also allow handling functional generalizations of the considered clique relaxation models.