Skip to yearly menu bar Skip to main content


Improved Parallel Algorithms for Density-Based Network Clustering

Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović

Pacific Ballroom #166

Keywords: [ Large Scale Learning and Big Data ] [ Combinatorial Optimization ] [ Clustering ]

Abstract: Clustering large-scale networks is a central topic in unsupervised learning with many applications in machine learning and data mining. A classic approach to cluster a network is to identify regions of high edge density, which in the literature is captured by two fundamental problems: the densest subgraph and the $k$-core decomposition problems. We design massively parallel computation (MPC) algorithms for these problems that are considerably faster than prior work. In the case of $k$-core decomposition, our work improves exponentially on the algorithm provided by Esfandiari et al.~(ICML'18). Compared to the prior work on densest subgraph presented by Bahmani et al.~(VLDB'12, '14), our result requires quadratically fewer MPC rounds. We complement our analysis with an experimental scalability analysis of our techniques.

Live content is unavailable. Log in and register to view live content