Timezone: »
Poster
Improved Parallel Algorithms for Density-Based Network Clustering
Mohsen Ghaffari · Silvio Lattanzi · Slobodan Mitrović
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.
Author Information
Mohsen Ghaffari (ETH Zurich)
Silvio Lattanzi (Google Zurich)
Slobodan Mitrović (MIT)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Oral: Improved Parallel Algorithms for Density-Based Network Clustering »
Wed. Jun 12th 09:40 -- 10:00 PM Room Room 102
More from the Same Authors
-
2023 Poster: Speeding Up Bellman Ford via Minimum Violation Permutations »
Silvio Lattanzi · Ola Svensson · Sergei Vassilvitskii -
2023 Poster: Fully Dynamic Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Poster: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2022 Oral: Deletion Robust Submodular Maximization over Matroids »
PAUL DUETTING · Federico Fusco · Silvio Lattanzi · Ashkan Norouzi-Fard · Morteza Zadimoghaddam -
2022 Spotlight: Online and Consistent Correlation Clustering »
Vincent Cohen-Addad · Silvio Lattanzi · Andreas Maggiori · Nikos Parotsidis -
2021 Poster: Correlation Clustering in Constant Many Parallel Rounds »
Vincent Cohen-Addad · Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2021 Oral: Correlation Clustering in Constant Many Parallel Rounds »
Vincent Cohen-Addad · Silvio Lattanzi · Slobodan Mitrović · Ashkan Norouzi-Fard · Nikos Parotsidis · Jakub Tarnawski -
2019 Poster: A Better k-means++ Algorithm via Local Search »
Silvio Lattanzi · Christian Sohler -
2019 Oral: A Better k-means++ Algorithm via Local Search »
Silvio Lattanzi · Christian Sohler -
2019 Poster: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2019 Oral: Submodular Streaming in All Its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity »
Ehsan Kazemi · Marko Mitrovic · Morteza Zadimoghaddam · Silvio Lattanzi · Amin Karbasi -
2018 Poster: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Oral: Parallel and Streaming Algorithms for K-Core Decomposition »
Hossein Esfandiari · Silvio Lattanzi · Vahab Mirrokni -
2018 Poster: Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams »
Ashkan Norouzi-Fard · Jakub Tarnawski · Slobodan Mitrovic · Amir Zandieh · Aidasadat Mousavifar · Ola Svensson -
2018 Oral: Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams »
Ashkan Norouzi-Fard · Jakub Tarnawski · Slobodan Mitrovic · Amir Zandieh · Aidasadat Mousavifar · Ola Svensson -
2017 Poster: Robust Submodular Maximization: A Non-Uniform Partitioning Approach »
Ilija Bogunovic · Slobodan Mitrovic · Jonathan Scarlett · Volkan Cevher -
2017 Talk: Robust Submodular Maximization: A Non-Uniform Partitioning Approach »
Ilija Bogunovic · Slobodan Mitrovic · Jonathan Scarlett · Volkan Cevher -
2017 Poster: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii -
2017 Talk: Consistent k-Clustering »
Silvio Lattanzi · Sergei Vassilvitskii