Min-max communities in graphs: Complexity and computational properties

Community detection in graphs aims at identifying modules within a network and, possibly, their hierarchical organization by only using the information encoded in the graph modeling the network. Generally speaking, a community in a network is a subset of its nodes showing higher degree of interconnection with each other than to the remaining nodes. This is an informal characterization and different formal definitions of communities have been proposed in the literature, also in relation to the available information. For most such definitions, the problem of detecting a proper partition of the given network into a prefixed number of community is NP-hard.In this paper, we consider the case in which a weight is associated to each edge of the graph, measuring the amount of interconnection between the corresponding pair of nodes. Under this hypothesis, we introduce and explore a new definition of community, that is, min-max communities, to model highly connected sets of nodes: a min-max community is a set of vertices such that the weakest (minimal) relation inside the community is stronger than the strongest (maximal) relation outside. By analyzing the structural properties induced by this definition, we prove that the problem of partitioning a complete weighted graph into k>. 0 communities is tractable. We also show that a slight modification to this framework results into an NP-complete problem.