A Survey on the Densest Subgraph Problem and Its Variants
arXiv:2303.14467 · doi:10.1145/3653298
Abstract
The Densest Subgraph Problem requires to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest in this problem with several important contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention to the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.
Accepted to ACM Computing Surveys
References in corpus (8)
- Proceedings of the 29th International Conference on Machine Learning (ICML-12)
- Distance-generalized Core Decomposition
- FirmCore Decomposition of Multilayer Networks
- Densest Diverse Subgraphs: How to Plan a Successful Cocktail Party with Diversity
- Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
- On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms
- Network Based Approach to Gene Prioritization at Genome-Wide Association Study Loci
- Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods