On clique relaxation models in network analysis |
| |
Authors: | Jeffrey Pattillo Nataly Youssef Sergiy Butenko |
| |
Institution: | 1. Department of Mathematics, Texas A&M University, College Station, TX 77843-3131, United States;2. Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02139-4307, United States;3. Department of Industrial and Systems Engineering, Texas A&M University, College Station, TX 77843-3131, United States |
| |
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. |
| |
Keywords: | Clique relaxations Maximum clique problem Social network analysis Cohesive subgroups Biological networks |
本文献已被 ScienceDirect 等数据库收录! |
|