The Generalized Mean Densest Subgraph Problem
  Finding dense subgraphs of a large graph is a standard problem in graph
mining that has been studied extensively both for its theoretical richness and
its many practical applications. In this paper we introduce a new family of
dense subgraph objectives, parameterized by a single parameter $p$, based on
computing generalized means of degree sequences of a subgraph. Our objective
captures both the standard densest subgraph problem and the maximum $k$-core as
special cases, and provides a way to interpolate between and extrapolate beyond
these two objectives when searching for other notions of dense subgraphs. In
terms of algorithmic contributions, we first show that our objective can be
minimized in polynomial time for all $p \geq 1$ using repeated submodular
minimization. A major contribution of our work is analyzing the performance of
different types of peeling algorithms for dense subgraphs both in theory and
practice. We prove that the standard peeling algorithm can perform arbitrarily
poorly on our generalized objective, but we then design a more sophisticated
peeling method which for $p \geq 1$ has an approximation guarantee that is
always at least $1/2$ and converges to 1 as $p \rightarrow \infty$. In
practice, we show that this algorithm obtains extremely good approximations to
the optimal solution, scales to large graphs, and highlights a range of
different meaningful notions of density on graphs coming from numerous domains.
Furthermore, it is typically able to approximate the densest subgraph problem
better than the standard peeling algorithm, by better accounting for how the
removal of one node affects other nodes in its neighborhood.
