Distance-generalized Core Decomposition
| Autor: | Francesco Bonchi, Lorenzo Severini, Arijit Khan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Social and Information Networks (cs.SI)
FOS: Computer and information sciences Computer science Computation Computer Science - Social and Information Networks 02 engineering and technology Upper and lower bounds Graph Vertex (geometry) Combinatorics 020204 information systems Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Partition (number theory) 020201 artificial intelligence & image processing Data Structures and Algorithms (cs.DS) |
| Zdroj: | SIGMOD Conference |
| Popis: | The $k$-core of a graph is defined as the maximal subgraph in which every vertex is connected to at least $k$ other vertices within that subgraph. In this work we introduce a distance-based generalization of the notion of $k$-core, which we refer to as the $(k,h)$-core, i.e., the maximal subgraph in which every vertex has at least $k$ other vertices at distance $\leq h$ within that subgraph. We study the properties of the $(k,h)$-core showing that it preserves many of the nice features of the classic core decomposition (e.g., its connection with the notion of distance-generalized chromatic number) and it preserves its usefulness to speed-up or approximate distance-generalized notions of dense structures, such as $h$-club. Computing the distance-generalized core decomposition over large networks is intrinsically complex. However, by exploiting clever upper and lower bounds we can partition the computation in a set of totally independent subcomputations, opening the door to top-down exploration and to multithreading, and thus achieving an efficient algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|