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, subsets of vertices inducing complete subgraphs, can model perfectly cohesive communities, but often they are overly restrictive because many real communities form dense, but not complete subgraphs. Therefore, di erent variants of relaxed cliques have been defined in terms of vertex degree and distance, edge density, and connectivity. They allow to impose application-specific constraints a community has to fulfill such as familiarity and reachability among members and robustness of the communities. By discussing the results obtained for some very prominent social networks widely studied in the SNA literature we demonstrate the applicability of our approach.