Detecting Informationally-Dense Subsets

Identifying locally dense subgraphs aims to pinpoint subgraphs characterized by tight internal connectivity. However, existing methods for identifying dense subgraphs based on density can lead to loose internal connections. This paper addresses this issue by introducing a concept of strength to detect strong subsets. Our approach encompasses the existing work that finds a nested chain of densest k-subgraphs as a special case and reveals subgraphs that have tight internal connections overlooked by existing methods. The strong subsets exhibit a laminar structure and can be computed in polynomial time. In contrast to previous works defining locally densest subgraphs without a natural extension to weighted graphs, our method accommodates both weighted and unweighted, directed and undirected graphs, as well as hypergraphs. Furthermore, it extends to a broader notion of information density, surpassing the scope of weighted graphs.