Modularity-based Sparse Soft Graph Clustering

Alexandre Hollocou 1, 2 Thomas Bonald 3, 1 Marc Lelarge 4, 2
2 DYOGENE - Dynamics of Geometric Networks
Inria de Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : Clustering is a central problem in machine learning for which graph-based approaches have proven their efficiency. In this paper, we study a relaxation of the modularity maxi-mization problem, well-known in the graph partitioning literature. A solution of this relaxation gives to each element of the dataset a probability to belong to a given cluster, whereas a solution of the standard modular-ity problem is a partition. We introduce an efficient optimization algorithm to solve this relaxation, that is both memory efficient and local. Furthermore, we prove that our method includes, as a special case, the Louvain optimization scheme, a state-of-the-art technique to solve the traditional modularity problem. Experiments on both synthetic and real-world data illustrate that our approach provides meaningful information on various types of data.
Type de document :
Communication dans un congrès
AISTATS 2019 - 22nd International Conference on Artificial Intelligence and Statistics, Apr 2019, Naha, Okinawa, Japan
Liste complète des métadonnées

https://hal.archives-ouvertes.fr/hal-02005331
Contributeur : Thomas Bonald <>
Soumis le : lundi 4 février 2019 - 07:24:02
Dernière modification le : samedi 16 mars 2019 - 01:55:17

Fichier

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

Identifiants

  • HAL Id : hal-02005331, version 1

Citation

Alexandre Hollocou, Thomas Bonald, Marc Lelarge. Modularity-based Sparse Soft Graph Clustering. AISTATS 2019 - 22nd International Conference on Artificial Intelligence and Statistics, Apr 2019, Naha, Okinawa, Japan. 〈hal-02005331〉

Partager

Métriques

Consultations de la notice

82

Téléchargements de fichiers

105