Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques

In social network analysis (SNA), relationships between members of a network are encoded in an undirected graph where vertices represent the members of the network and edges indicate the existence of a relationship. One important task in SNA is community detection, that is, clustering the members into communities such that relatively few edges are in the cutsets but relatively many are internal edges. The clustering is intended to reveal hidden or reproduce known features of the network, while the structure of communities is arbitrary. We propose decomposing a graph into the minimum number of relaxed cliques as a new method for community detection especially conceived for cases in which the internal structure of the community is important. Cliques, that is, subgraphs with pairwise connected vertices, can model perfectly cohesive communities, but often they are overly restrictive because many real communities form dense but not complete subgraphs. Therefore, different variants of relaxed cliques have been de?ned in terms of vertex degree and distance, edge density, and connectivity. They allow to impose application-speci?c constraints a community has to ful?ll such as familiarity and reachability among members and robustness of the communities. Standard compact formulations fail in ?nding optimal solutions even for small instances of such decomposition problems. Hence, we develop exact algorithms based on Dantzig-Wolfe reformulation and branch-and-price techniques. Extensive computational results demonstrate the e?ectiveness of all components of the algorithms and the validity of our approach when applied to social network instances from the literature.