paper_raw.txt

Finding dense subgraphs in a graph is a fundamental graph
mining task, with applications in several fields. Algorithms
for identifying dense subgraphs are used in biology, in finance, in spam detection, etc. Standard formulations of
this problem such as the problem of finding the maximum
clique of a graph are hard to solve. However, some tractable
formulations of the problem have also been proposed, focusing mainly on optimizing some density function, such as the
degree density. However, maximization of degree density
usually leads to large subgraphs with small density.
In this paper, we introduce the k-clique-graph densest subgraph problem, k ≥ 3, a novel formulation for the discovery
of dense subgraphs. Given an input graph, its k-clique-graph
is a new graph created from the input graph where each vertex of the new graph corresponds to a k-clique of the input
graph and two vertices are connected with an edge if they
share a common k − 1-clique. We define a simple density
function, the k-clique-graph density, which gives compact
and at the same time dense subgraphs, and we project its
resulting subgraphs back to the input graph. In this paper
we focus on the triangle-graph densest subgraph problem
obtained for k = 3. To optimize the proposed function, we
provide two exact algorithms. Furthermore, we present an
efficient greedy approximation algorithm that scales well to
larger graphs.
We evaluate the proposed algorithms on real datasets and
compare them with other algorithms in terms of the size and
the density of the extracted subgraphs. The results verify
the ability of the proposed algorithms in finding high-quality
subgraphs in terms of size and density.