# The Densest Subgraph Problem with a Convex/Concave Size Function

arXiv: https://arxiv.org/abs/1703.03603 · HTML: https://mlsanity.com/paper/1703.03603/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2017.

## Built on by (most cited first, 3 of 3)

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)
- [Differentially Private and Scalable Estimation of the Network Principal Component](https://mlsanity.com/paper/2505.03858/) (2025)

## Abstract (arXiv)

In the densest subgraph problem, given an edge-weighted undirected graph G=(V,E,w), we are asked to find Ssubseteq V that maximizes the density, i.e., w(S)/|S|, where w(S) is the sum of weights of the edges in the subgraph induced by S. This problem has often been employed in a wide variety of graph mining applications. However, the problem has a drawback; it may happen that the obtained subset is too large or too small in comparison with the size desired in the application at hand. In this study, we address the size issue of the densest subgraph problem by generalizing the density of Ssubseteq V. Specifically, we introduce the f-density of Ssubseteq V, which is defined as w(S)/f(|S|), where f:mathbbZ≥ 0rightarrow ℝ≥ 0 is a monotonically non-decreasing function. In the f-densest subgraph problem (f-DS), we aim to find Ssubseteq V that maximizes the f-density w(S)/f(|S|). Although f-DS does not explicitly specify the size of the output subset of vertices, we can handle the above size issue using a convex/concave size function f appropriately. For f-DS with convex function f, we propose a nearly-linear-time algorithm with a provable approximation guarantee. On the other hand, for f-DS with concave function f, we propose an LP-based exact algorithm, a flow-based O(|V|3)-time exact algorithm for unweighted graphs, and a nearly-linear-time approximation algorithm.