Distance-generalized Core Decomposition

摘要: The $k$-core of a graph is defined as the maximal subgraph in which every vertex connected to at least $k$ other vertices within that subgraph. In this work we introduce distance-based generalization notion $k$-core, refer $(k,h)$-core, i.e., has distance $\leq h$ We study properties $(k,h)$-core showing it preserves many nice features classic core decomposition (e.g., its connection with distance-generalized chromatic number) and usefulness speed-up or approximate notions dense structures, such $h$-club. Computing over large networks intrinsically complex. However, by exploiting clever upper lower bounds can partition computation set totally independent subcomputations, opening door top-down exploration multithreading, thus achieving an efficient algorithm.