Graph-based data clustering via multiscale community detection

Abstract

We present a graph-theoretical approach to data clustering, which combines the creation of a graph from the data with Markov Stability, a multiscale community detection framework. We show how the multiscale capabilities of the method allow the estimation of the number of clusters, as well as alleviating the sensitivity to the parameters in graph construction. We use both synthetic and benchmark real datasets to compare and evaluate several graph construction methods and clustering algorithms, and show that multiscale graph-based clustering achieves improved performance compared to popular clustering methods without the need to set externally the number of clusters.

arXiv comment16 pages, 5 figures

References in corpus (20)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Geometric deep learning: going beyond Euclidean data
• Statistical Mechanics of Community Detection
• Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
• Laplacian Dynamics and Multiscale Modular Structure in Networks
• Narrow scope for resolution-limit-free community detection
• Local resolution-limit-free Potts model for community detection
• Markov dynamics as a zooming lens for multiscale community detection: non clique-like communities and the field-of-view limit
• Flow-based network analysis of the Caenorhabditis elegans connectome
• The stability of a graph partition: A dynamics-based framework for community detection
• Interest communities and flow roles in directed networks: the Twitter network of the UK riots
• Protein multi-scale organization through graph partitioning and robustness analysis: Application to the myosin-myosin light chain interaction
• Multiscale dynamical embeddings of complex networks
• Uncovering allosteric pathways in caspase-1 with Markov transient analysis and multiscale community detection
• From Free Text to Clusters of Content in Health Records: An Unsupervised Graph Partitioning Approach
• Finding role communities in directed networks using Role-Based Similarity, Markov Stability and the Relaxed Minimum Spanning Tree
• Hopping in the crowd to unveil network topology
• Temporal stability of network partitions
• Scale-variant topological information for characterizing the structure of complex networks

Cited by in corpus (3)

• Geometric graphs from data to aid classification tasks with graph convolutional networks
• Attributed Graph Clustering with Multi-Scale Weight-Based Pairwise Coarsening and Contrastive Learning
• Multiscale methods for signal selection in single-cell data