  The problem of finding the densest subgraph in a given graph has several
applications in graph mining, particularly in areas like social network
analysis, protein and gene analyses etc. Depending on the application, finding
dense subgraphs can be used to determine regions of high importance, similar
characteristics or enhanced interaction. The densest subgraph extraction
problem is a fundamentally a non-linear optimization problem. Nevertheless, it
can be solved in polynomial time by an exact algorithm based on the iterative
solution of a series of maximum flow sub-problems. Despite its polynomial time
complexity, the computing time required by the exact algorithms on very large
graphs could be prohibitive. Thus, to approach graphs with millions of vertices
and edges, one has to resort to heuristic algorithms. We provide an efficient
implementation of a greedy heuristic from the literature that is extremely fast
and has some nice theoretical properties. We also introduce a new heurisitic
algorithm that is built on top of the greedy and the exact methods. An
extensive computational study is presented to evaluate the performance of
various solution methods on a benchmark composed of 86 instances taken from the
literature. This analysis shows that the proposed heuristic algorithm proved
very effective on a large number of test instances, often providing either the
optimal solution or near-optimal solution within short computing times.
