Analysis of a regularized continuous formulation for the maximum s-plex problem

Community detection is an important task in social network analysis (SNA), that is, clustering the members of a network into communities. In SNA, relationships between members are encoded in an undirected graph where vertices represent the members of the network, and edges indicate the existence of a relationship between them. Subgraphs with pairwise connected vertices are called cliques and can model perfectly cohesive communities, but often in concrete world applications they are overly restrictive since many real communities form dense but not complete subgroups. For this reason, different variants of relaxed cliques have been defined in terms of vertex degree and distance, edge density and connectivity. This thesis analyzes the s-plex clique relaxation model and investigates the maximum s-plex problem starting from its Motzkin-Straus (MS) cubic continuous formulation, which provides a non-trivial characterization of the s-plex number for a given graph. However, a well-known drawback of this formulation is the presence of spurious solutions from which it is difficult to recover a maximum s-plex structure. Therefore, in this thesis, a continuous optimization framework based on regularization is provided for the maximum s-plex problem. In particular, two possible alternatives of regularization terms are included in the cubic formulation in order to guarantee equivalence between the continuous regularized problem and the original one in both a global and a local sense. The good behavior of these regularized formulations makes them very attractive in the context of continuous nonlinear optimization to develop future competitive algorithms to search for maximum s-plexes within a network.