Timezone: »

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

Wed Jun 12 02:40 PM -- 03:00 PM (PDT) @ Room 102
in Combinatorial Optimization »
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.
[ Slides] 

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