Eigenvalue Approach to Dense Clusters in Hypergraphs

ABSTRACT In this article, we investigate the problem of finding in a given weighted hypergraph a subhypergraph with the maximum possible density. Using the notion of a support matrix we prove that the density of an optimal subhypergraph is equal to for an optimal support matrix . Alternatively, the maximum density of a subhypergraph is equal to the solution of a minimax problem for column sums of support matrices. We study the density decomposition of a hypergraph and show that it is a significant refinement of the Dulmage–Mendelsohn decomposition. Our theoretical results yield an efficient algorithm for finding the maximum density subhypergraph and more generally, the density decomposition for a given weighted hypergraph.