  In the densest subgraph problem, given an edge-weighted undirected graph
$G=(V,E,w)$, we are asked to find $S\subseteq 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
$S\subseteq V$. Specifically, we introduce the $f$-density of $S\subseteq V$,
which is defined as $w(S)/f(|S|)$, where $f:\mathbb{Z}_{\geq 0}\rightarrow
\mathbb{R}_{\geq 0}$ is a monotonically non-decreasing function. In the
$f$-densest subgraph problem ($f$-DS), we aim to find $S\subseteq 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.
