Timezone: »

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

Wed Jun 12 06:30 PM -- 09:00 PM (PDT) @ Pacific Ballroom #166
in Posters Wed »
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.
Keywords: Clustering · Combinatorial Optimization · Large Scale Learning and Big Data

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