### Distance-generalized Core Decomposition

**Distance-generalized Core Decomposition**

A summary of the SIGMOD 2019 research paper by Francesco Bonchi, Arijit Khan, and Lorenzo Severini

**Background:**Extracting dense structures from large graphs has emerged as a key graph-mining primitive in a variety of application scenarios, ranging from web mining, to biology, and finance. Many different definitions of dense subgraphs have been proposed (e.g., cliques, n-cliques, n-clans, k-plexes, f-groups, n-clubs, lambda sets), but most of them are NP-hard or at least quadratic. In this respect, the concept of core decomposition is particularly appealing because (i) it can be computed in linear time, and (ii) it is related to many of the various definitions of a dense subgraph and it can be used to speed-up or approximate their computation.

*The k-core of a graph is defined as a maximal subgraph in which every vertex is connected to at least k other vertices within that subgraph.*The set of all k-cores of a graph, for each k, forms its core decom…