Uncovering Hidden Block Structure for Clustering - Algorithmes Parallèles et Optimisation Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Uncovering Hidden Block Structure for Clustering

Résumé

We present a multistage procedure to cluster directed and undirected weighted graphs by finding the block structure of their adjacency matrices. A central part of the process is to scale the adjacency matrix into a doubly-stochastic form, which permits detection of the whole matrix block structure with minimal spectral information (theoretically a single pair of singular vectors suffices). We present the different stages of our method, namely the impact of the doubly-stochastic scaling on singular vectors, detection of the block structure by means of these vectors, and details such as cluster refinement and a stopping criterion. Then we test the algorithm’s effectiveness by using it on two unsupervised classification tasks: community detection in networks and shape detection in clouds of points in two dimensions. By comparing results of our approach with those of widely used algorithms designed for specific purposes, we observe that our method is competitive (for community detection) if not superior (for shape detection) in comparison with existing methods.
Fichier principal
Vignette du fichier
Uncovering Hidden Block Structure for Clustering.pdf (1.93 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03003811 , version 1 (17-11-2020)

Identifiants

Citer

Luce Le Gorrec, Sandrine Mouysset, Iain S. Duff, Philip A. Knight, Daniel Ruiz. Uncovering Hidden Block Structure for Clustering. European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2019), Sep 2019, Würzburg, Germany. pp.140-155, ⟨10.1007/978-3-030-46150-8_9⟩. ⟨hal-03003811⟩
79 Consultations
136 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More