Degree and distance-based clique relaxations

Abstract

Cliques and graph theoretic clique relaxations are used to model clusters in graph-based data mining, where data is modeled by a graph in which an edge implies some relationship between the entities represented by its end points. The need for relaxations of the clique model arises in practice when dealing with massive datasets which are error-prone, resulting in false or missing edges. The clique definition which requires complete pairwise adjacency in the cluster becomes overly restrictive in such situations. Graph theoretic clique relaxations address this need by relaxing structural properties of a clique in a controlled manner via user-specified parameters. This chapter surveys two well-known clique relaxations, $k$-plexes and $k$-clubs, primarily focusing on formulations, polyhedral results, complexity, and exact algorithms.