The Core Decomposition of Networks: Theory, Algorithms and Applications - CentraleSupélec Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2019

The Core Decomposition of Networks: Theory, Algorithms and Applications

Résumé

The core decomposition of networks has attracted significant attention due to its numerous applications in real-life problems. Simply stated, the core decomposition of a network (graph) assigns to each graph node v, an integer number c(v) (the core number), capturing how well v is connected with respect to its neighbors. This concept is strongly related to the concept of graph degeneracy, which has a long history in Graph Theory. Although the core decomposition concept is extremely simple, there is an enormous interest in the topic from diverse application domains, mainly because it can be used to analyze a network in a simple and concise manner by quantifying the significance of graph nodes. Therefore, there exists a respectable number of research works that either propose efficient algorithmic techniques under different settings and graph types or apply the concept to another problem or scientific area. Based on this large interest in the topic, in this survey, we perform an in-depth discussion of core decomposition, focusing mainly on: i) the basic theory and fundamental concepts, ii) the algorithmic techniques proposed for computing it efficiently under different settings, and iii) the applications that can benefit significantly from it.
Fichier principal
Vignette du fichier
core_decomposition_arXiv.pdf (2.31 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01986309 , version 1 (18-01-2019)
hal-01986309 , version 2 (31-01-2019)
hal-01986309 , version 3 (03-12-2019)

Identifiants

  • HAL Id : hal-01986309 , version 1

Citer

Fragkiskos Malliaros, Christos Giatsidis, Apostolos Papadopoulos, Michalis Vazirgiannis. The Core Decomposition of Networks: Theory, Algorithms and Applications. 2019. ⟨hal-01986309v1⟩
1227 Consultations
5462 Téléchargements

Partager

Gmail Facebook X LinkedIn More