  Dense subgraph discovery methods are routinely used in a variety of
applications including the identification of a team of skilled individuals for
collaboration from a social network. However, when the network's node set is
associated with a sensitive attribute such as race, gender, religion, or
political opinion, the lack of diversity can lead to lawsuits.
  In this work, we focus on the problem of finding a densest diverse subgraph
in a graph whose nodes have different attribute values/types that we refer to
as colors. We propose two novel formulations motivated by different realistic
scenarios. Our first formulation, called the densest diverse subgraph problem
(DDSP), guarantees that no color represents more than some fraction of the
nodes in the output subgraph, which generalizes the state-of-the-art due to
Anagnostopoulos et al. (CIKM 2020). By varying the fraction we can range the
diversity constraint and interpolate from a diverse dense subgraph where all
colors have to be equally represented to an unconstrained dense subgraph. We
design a scalable $\Omega(1/\sqrt{n})$-approximation algorithm, where $n$ is
the number of nodes. Our second formulation is motivated by the setting where
any specified color should not be overlooked. We propose the densest
at-least-$\vec{k}$-subgraph problem (Dal$\vec{k}$S), a novel generalization of
the classic Dal$k$S, where instead of a single value $k$, we have a vector
${\mathbf k}$ of cardinality demands with one coordinate per color class. We
design a $1/3$-approximation algorithm using linear programming together with
an acceleration technique. Computational experiments using synthetic and
real-world datasets demonstrate that our proposed algorithms are effective in
extracting dense diverse clusters.
