Oral
Improved Parallel Algorithms for Density-Based Network Clustering
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović

Wed Jun 12th 02:40 -- 03:00 PM @ Room 102

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. In literature this approach 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.

Author Information

Mohsen Ghaffari (ETH Zurich)
Silvio Lattanzi (Google Zurich)
Slobodan Mitrović (MIT)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors