A maximal clique-based integer programming method for overlapping community detection

Community detection, which requires the clustering of the vertices of a network graph, is an important component of network science. A variety of mathematical programming models and heuristics have been developed for community detection and they seek to optimize criteria such as the modularity score (Q) or the modularity density function. These methods typically establish a partition of the vertices; however, there are many network applications where a partition is overly restrictive. In such instances, overlapping community detection methods are useful because they allow vertices to have membership in more than one community. Cliques are a critical building block for some overlapping clustering methods, including those designed for weighted networks that are of particular interest herein. One recently-proposed method assembles candidate communities from maximal cliques and then uses a set-covering approach to select from the candidates. The method is limited by the heuristic nature of the process for establishing the candidate communities. In this paper, we remedy this problem by presenting a mathematical programming model that will directly construct the communities from the cliques, thus obviating the need to build candidate communities. This ‘modified’ method incorporates ideas from recent advancements for network clustering to establish constraints in the assembly of cliques to form communities.