Clique Relaxation

Abstract

Clique relaxation models that were originally introduced in the literature on social network analysis are not only gaining increasing popularity in a wide spectrum of complex network applications, but also keep garnering attention of mathematicians, computer scientists, and operations researchers as a promising avenue for fruitful theoretical investigations. This chapter describes the origins of clique relaxation concepts and provides a brief overview of mathematical programming formulations for the corresponding optimization problems, algorithms proposed to solve these problems, and selected real-life applications of the models of interest.

1 Introduction

Social networks represent certain types of social interaction, such as acquaintance, friendship, or collaboration between people or groups of people that are referred to as actors. In social networks, vertices (nodes, dots) usually stand for actors, and edges (arcs, links, lines) represent the pairwise relations or interactions between the actors. As an illustration of a...