Google Research

Improved Parallel Algorithms for Density-Based Network Clustering

icml (2019)


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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work