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.