Discounted average degree density metric and new algorithms for the densest subgraph problem

Abstract

Detecting the densest subgraph is one of the most important problems in graph mining and has a variety of applications. Although there are many possible metrics for subgraph density, there is no consensus on which density metric we should use. In this article, we suggest a new density metric, the discounted average degree, which has some desirable properties of the subgraph's density. We also show how to obtain an optimum densest subgraph for small graphs with respect to several density metrics, including our new density metric, by using mixed integer programming. Finally, we develop a new heuristic algorithm to quickly obtain a good approximate solution for large graphs. Our computational experiments on real-world graphs showed that our new heuristic algorithm outperformed other heuristics in terms of the quality of the solutions. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(1), 3–15 2018.