mlsanityData to 14 Oct 2026

A Survey on the Densest Subgraph Problem and Its Variants

arXiv 2303.14467 ↗First posted 25 Mar 2023cs.DS cs.AIcited by 8

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 63 of its 244 references that are in the map. First posted on arXiv 25 Mar 2023.

Builds on

63 of 244 references.

References · 63

  1. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  2. 2013Clustering and Community Detection in Directed Networks: A Surveycited by 38
  3. 2020CLIPPER: A Graph-Theoretic Framework for Robust Data Associationcited by 28
  4. 2020Explainable Classification of Brain Networks via Contrast Subgraphscited by 26
  5. 2013Recent Advances in Graph Partitioningcited by 25
  6. 2022AntiBenford Subgraphs: Unsupervised Anomaly Detection in Financial Networkscited by 18
  7. 2020Hypergraph Cuts with General Splitting Functionscited by 14
  8. 2017DenseAlert: Incremental Dense-Subtensor Detection in Tensor Streamscited by 13
  9. 2022Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphscited by 13
  10. 2016The Densest k-Subhypergraph Problemcited by 10
  11. 2021Differentially Private Densest Subgraph Detectioncited by 7
  12. 2015Densest Subgraph in Dynamic Graph Streamscited by 6
38 more
  1. 2016Peeling Bipartite Networks for Dense Subgraph Discoverycited by 6
  2. 2018No Place to Hide: Catching Fraudulent Entities in Tensorscited by 6
  3. 2020Contextual Reserve Price Optimization in Auctions via Mixed-Integer Programmingcited by 6
  4. 2021Differentially Private Densest Subgraphcited by 6
  5. 2022FirmCore Decomposition of Multilayer Networkscited by 6
  6. 2022Spade: A Real-Time Fraud Detection Framework on Evolving Graphs (Complete Version)cited by 6
  7. 2022Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphscited by 6
  8. 2015Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streamscited by 5
  9. 2019Near-Optimal Fully Dynamic Densest Subgraphcited by 5
  10. 2019EnsemFDet: An Ensemble Approach to Fraud Detection based on Bipartite Graphcited by 5
  11. 2020Statistical and computational thresholds for the planted k-densest sub-hypergraph problemcited by 5
  12. 2021The Generalized Mean Densest Subgraph Problemcited by 5
  13. 2018Mining Density Contrast Subgraphscited by 4
  14. 2018Finding events in temporal networks: Segmentation meets densest-subgraph discoverycited by 4
  15. 2018Core Decomposition in Multilayer Networks: Theory, Algorithms, and Applicationscited by 4
  16. 2019Efficient Algorithms for Densest Subgraph Discoverycited by 4
  17. 2020Online Dense Subgraph Discovery via Blurred-Graph Feedbackcited by 4
  18. 2014Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositionscited by 3
  19. 2017The Densest Subgraph Problem with a Convex/Concave Size Functioncited by 3
  20. 2019Novel Dense Subgraph Discovery Primitives: Risk Aversion and Exclusion Queriescited by 3
  21. 2019Graph Mining Meets Crowdsourcing: Extracting Experts for Answer Aggregationcited by 3
  22. 2019Faster width-dependent algorithm for mixed packing and covering LPscited by 3
  23. 2019Flowless: Extracting Densest Subgraphs Without Flow Computationscited by 3
  24. 2015Applications of Uniform Sampling: Densest Subgraph and Beyondcited by 2
  25. 2016Best Friends Forever (BFF): Finding Lasting Dense Subgraphscited by 2
  26. 2018On Finding Dense Common Subgraphscited by 2
  27. 2018Metric Sublinear Algorithms via Linear Samplingcited by 2
  28. 2019On solving the densest k-subgraph problem on large graphscited by 2
  29. 2019Convex optimization for the densest subgraph and densest submatrix problemscited by 2
  30. 2019Distributed Dense Subgraph Detection and Low Outdegree Orientationcited by 2
  31. 2020Parallel Clique Counting and Peeling Algorithmscited by 2
  32. 2021Exploring the Subgraph Density-Size Trade-off via the Lov'asz Extensioncited by 2
  33. 2022A New Dynamic Algorithm for Densest Subhypergraphscited by 2
  34. 2022A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysiscited by 2
  35. 2022Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networkscited by 2
  36. 2015Towards Realistic Team Formation in Social Networks based on Densest Subgraphscited by 1
  37. 2018Risk-Averse Matchings over Uncertain Graph Databasescited by 1
  38. 2018Robust Densest Subgraph Discoverycited by 1

50 most cited of 63 All 63 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 2; 2026: 2.

8 papers.

  1. 2024Graph Transformers: A Surveycited by 32
  2. 2023Detection of Dense Subhypergraphs by Low-Degree Polynomialscited by 7
  3. 2024Bandits with Abstention under Expert Advicecited by 3
  4. 2023Jaccard-constrained dense subgraph discoverycited by 0
  5. 2025Differentially Private and Scalable Estimation of the Network Principal Componentcited by 0
  6. 2025Fast and Simple Densest Subgraph with Predictionscited by 0
  7. 2026Provably Finding a Hidden Dense Submatrix among Many Planted Dense Submatrices via Convex Programmingcited by 0
  8. 2026The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networkscited by 0