2017/08/18 by Soumendu Sundar Mukherjee, Mukherjee, Soumendu Sundar, Purnamrita Sarkar +3 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Methodology (stat.ME) #Network Traffic and Congestion Control #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1708.05573
openalex publication_date 2017/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this article, we advance divide-and-conquer strategies for solving the\ncommunity detection problem in networks. We propose two algorithms which\nperform clustering on a number of small subgraphs and finally patches the\nresults into a single clustering. The main advantage of these algorithms is\nthat they bring down significantly the computational cost of traditional\nalgorithms, including spectral clustering, semi-definite programs, modularity\nbased methods, likelihood based methods etc., without losing on accuracy and\neven improving accuracy at times. These algorithms are also, by nature,\nparallelizable. Thus, exploiting the facts that most traditional algorithms are\naccurate and the corresponding optimization problems are much simpler in small\nproblems, our divide-and-conquer methods provide an omnibus recipe for scaling\ntraditional algorithms up to large networks. We prove consistency of these\nalgorithms under various subgraph selection procedures and perform extensive\nsimulations and real-data analysis to understand the advantages of the\ndivide-and-conquer approach in various settings.\n