Title: Two provably consistent divide and conquer clustering algorithms for large networks,
Abstract: In this article, we advance divide-and-conquer strategies for solving the
community detection problem in networks. We propose two algorithms which
perform clustering on a number of small subgraphs and finally patches the
results into a single clustering. The main advantage of these algorithms is
that they bring down significantly the computational cost of traditional
algorithms, including spectral clustering, semi-definite programs, modularity
based methods, likelihood based methods etc., without losing on accuracy and
even improving accuracy at times. These algorithms are also, by nature,
parallelizable. Thus, exploiting the facts that most traditional algorithms are
accurate and the corresponding optimization problems are much simpler in small
problems, our divide-and-conquer methods provide an omnibus recipe for scaling
traditional algorithms up to large networks. We prove consistency of these
algorithms under various subgraph selection procedures and perform extensive
simulations and real-data analysis to understand the advantages of the
divide-and-conquer approach in various settings.