Density-friendly graph decomposition

Nikolaj Tatti*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)


Decomposing a graph into a hierarchical structure via k-core analysis is a standard operation in any modern graph-mining toolkit. k-core decomposition is a simple and efcient method that allows to analyze a graph beyond its mere degree distribution. More specifcally, it is used to identify areas in the graph of increasing centrality and connectedness, and it allows to reveal the structural organization of the graph. Despite the fact that k-core analysis relies on vertex degrees, k-cores do not satisfy a certain, rather natural, density property. Simply put, the most central k-core is not necessarily the densest subgraph. This inconsistency between k-cores and graph density provides the basis of our study. We start by defning what it means for a subgraph to be locally dense, and we show that our defnition entails a nested chain decomposition of the graph, similar to the one given by k-cores, but in this case the components are arranged in order of increasing density. We show that such a locally dense decomposition for a graph G = (V, E) can be computed in polynomial time. The running time of the exact decomposition algorithm is O(|V |2|E|) but is signifcantly faster in practice. In addition, we develop a linear-time algorithm that provides a factor-2 approximation to the optimal locally dense decomposition. Furthermore, we show that the k-core decomposition is also a factor-2 approximation, however, as demonstrated by our experimental evaluation, in practice k-cores have different structure than locally dense subgraphs, and as predicted by the theory, k-cores are not always well-aligned with graph density.

Original languageEnglish
Article number54
Pages (from-to)1-29
Number of pages29
JournalACM Transactions on Knowledge Discovery from Data
Issue number5
Publication statusPublished - 1 Sep 2019
MoE publication typeA1 Journal article-refereed


  • Fractional programming
  • Locally-dense graph decomposition
  • Max-flow

Fingerprint Dive into the research topics of 'Density-friendly graph decomposition'. Together they form a unique fingerprint.

Cite this