Dense clusters in hypergraphs

Publication date 5 April 2023

Density (toughness, etc.) (05C42) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Abstract: In this paper we solve the problem of finding in a given weighted hypergraph a subhypergraph with a maximum possible density. We introduce the notion of a support matrix and prove that the density of an optimal subhypergraph is equal to

| A^{T} A |

for an optimal support matrix

A

. Alternatively, the maximum density of a subhypergraph is equal to the solution of a minimax problem for column sums of support matrices. We introduce the spectral 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 spectral decomposition for a given weighted hypergraph.

This page was built for publication: Dense clusters in hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432250)