On clique relaxation models in network analysis

Increasing interest in studying community structures, or clusters in complex networks arising in various applications has led to a large and diverse body of literature introducing numerous graph-theoretic models relaxing certain characteristics of the classical clique concept. This paper analyzes the elementary clique-defining properties implicitly exploited in the available clique relaxation models and proposes a taxonomic framework that not only allows to classify the existing models in a systematic fashion, but also yields new clique relaxations of potential practical interest. Some basic structural properties of several of the considered models are identified that may facilitate the choice of methods for solving the corresponding optimization problems. In addition, bounds describing the cohesiveness properties of different clique relaxation structures are established, and practical implications of choosing one model over another are discussed.

► We provide foundations for a systematic study of clique relaxation models in graphs.
► The proposed taxonomy yields new clique relaxations of practical interest.
► Basic structural properties of corresponding optimization problems are identified.
► Rigorous bounds describing the fundamental cohesiveness properties are established.
► Practical implications of choosing one model over another are discussed.