CORECLUSTER: A Degeneracy Based Graph Clustering Framework

Abstract : Graph clustering or community detection constitutes an important task forinvestigating the internal structure of graphs, with a plethora of applications in several domains. Traditional tools for graph clustering, such asspectral methods, typically suffer from high time and space complexity. In thisarticle, we present \textsc{CoreCluster}, an efficient graph clusteringframework based on the concept of graph degeneracy, that can be used along withany known graph clustering algorithm. Our approach capitalizes on processing thegraph in a hierarchical manner provided by its core expansion sequence, anordered partition of the graph into different levels according to the $k$-coredecomposition. Such a partition provides a way to process the graph inan incremental manner that preserves its clustering structure, whilemaking the execution of the chosen clustering algorithm much faster due to thesmaller size of the graph's partitions onto which the algorithm operates.
Type de document :
Communication dans un congrès
IAAA: Innovative Applications of Artificial Intelligence, Jul 2014, Quebec City, Canada. Twenty-Sixth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-14), July 29–31, 2014 in Québec City, Québec, Canada., 2014
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083536
Contributeur : Dimitrios M. Thilikos <>
Soumis le : lundi 17 novembre 2014 - 14:11:56
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : vendredi 14 avril 2017 - 17:16:23

Fichier

corecluster_aaai14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-01083536, version 1

Citation

Christos Giatsidis, Fragkiskos Malliaros, Dimitrios M. Thilikos, Michalis Vazirgiannis. CORECLUSTER: A Degeneracy Based Graph Clustering Framework. IAAA: Innovative Applications of Artificial Intelligence, Jul 2014, Quebec City, Canada. Twenty-Sixth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI-14), July 29–31, 2014 in Québec City, Québec, Canada., 2014. 〈lirmm-01083536〉

Partager

Métriques

Consultations de la notice

206

Téléchargements de fichiers

269