A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees - Sorbonne Université
Communication Dans Un Congrès Année : 2022

A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees

Résumé

Graph clustering is one of the most basic and popular unsupervised learning problems. Among the different formulations of the problem, the modularity objective has been particularly successful in helping design impactful algorithms; Most notably, the Louvain algorithm has become one of the most used algorithm for clustering graphs. However, one major limitation of the Louvain algorithm is its sequential nature which makes it impractical in distributed environments and on massive datasets. In this paper, we provide a parallel version of Louvain which works in the massively parallel computation model (MPC). We show that it recovers the ground-truth clusters in the classic stochastic block model in only a constant number of parallel rounds, and so for a wider regime of parameters than the standard Louvain algorithm as shown recently in [Cohen-Addad et al. 2020].
Fichier non déposé

Dates et versions

hal-03944613 , version 1 (18-01-2023)

Identifiants

Citer

Vincent Cohen-Addad, Frederik Mallmann-Trenn, David Saulpic. A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees. PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, Jul 2022, Salerno, Italy. pp.356-365, ⟨10.1145/3519270.3538449⟩. ⟨hal-03944613⟩
41 Consultations
0 Téléchargements

Altmetric

Partager

More