Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01083536
Contributor : Dimitrios Thilikos <>
Submitted on : Monday, November 17, 2014 - 2:11:56 PM
Last modification on : Monday, May 4, 2020 - 9:42:03 AM
Document(s) archivé(s) le : Friday, April 14, 2017 - 5:16:23 PM

File

corecluster_aaai14.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01083536, version 1

Collections

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. ⟨lirmm-01083536⟩

Share

Metrics

Record views

602

Files downloads

445