Two provably consistent divide-and-conquer clustering algorithms for large networks

Soumendu Sundar Mukherjee

doi:10.1073/pnas.2100482118

Two provably consistent divide-and-conquer clustering algorithms for large networks

2021-10-29

6

OA

AI

S

Soumendu Sundar Mukherjee *

DOI：10.1073/pnas.2100482118

Original

Original request for help

Save

Abstract

En 中文

In this article, we advance divide-and-conquer strategies for solv -ing the community detection problem in networks. We propose two algorithms that perform clustering on several small sub-graphs and finally patch the results into a single clustering. The main advantage of these algorithms is that they significantly bring down the computational cost of traditional algorithms, including spectral clustering, semidefinite programs, modularity-based methods, likelihood-based methods, etc., without losing accuracy, and even improving accuracy at times. These algorithms are also, by nature, parallelizable. Since most traditional algo-rithms are accurate, and the corresponding optimization prob-lems are much simpler in small problems, our divide-and-conquer methods provide an omnibus recipe for scaling traditional algo-rithms up to large networks. We prove the consistency of these algorithms under various subgraph selection procedures and per -form extensive simulations and real-data analysis to understand the advantages of the divide-and-conquer approach in various settings.

Keywords:

networks

divide-and-conquer

clustering

Two provably consistent divide-and-conquer clustering algorithms for large networks

Abstract

Journal

Organization