Densest subgraph discovery (DSD) is a fundamental problem in graph mining. It
has been studied for decades, and is widely used in various areas, including
network science, biological analysis, and graph databases. Given a graph G, DSD
aims to find a subgraph D of G with the highest density (e.g., the number of
edges over the number of vertices in D). Because DSD is difficult to solve, we
propose a new solution paradigm in this paper. Our main observation is that a
densest subgraph can be accurately found through a k-core (a kind of dense
subgraph of G), with theoretical guarantees. Based on this intuition, we
develop efficient exact and approximation solutions for DSD. Moreover, our
solutions are able to find the densest subgraphs for a wide range of graph
density definitions, including clique-based and general pattern-based density.
We have performed extensive experimental evaluation on eleven real datasets.
Our results show that our algorithms are up to four orders of magnitude faster
than existing approaches.

本文提出了一种新的解决模式来找到具有最高密度的图 G 的亚图 D，并通过 k-core 的方法开发了一些有效的解决方案来寻找包括基于团和一般模式定义密度的各种图的最密亚图，实验结果表明该算法比现有方法快四个数量级。