On clique relaxation models in network analysis

On clique relaxation models in network analysis

0.00 Avg rating0 Votes
Article ID: iaor2013398
Volume: 226
Issue: 1
Start Page Number: 9
End Page Number: 18
Publication Date: Apr 2013
Journal: European Journal of Operational Research
Authors: , ,
Keywords: graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.