A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees - Sorbonne Université Access content directly
Conference Papers Year : 2022

A Massively Parallel Modularity-Maximizing Algorithm with Provable Guarantees

Abstract

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].
No file

Dates and versions

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

Identifiers

Cite

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⟩
19 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More