2019/06/14 by Ryan A. Rossi, Rossi, Ryan A., Nesreen K. Ahmed +5
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #Data Visualization and Analytics #Distributed #FOS: Computer and information sciences #Parallel #Social and Information Networks (cs.SI) #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1906.06432
openalex publication_date 2019/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Community detection in graphs has many important and fundamental applications including in distributed systems, compression, image segmentation, divide-and-conquer graph algorithms such as nested dissection, document and word clustering, circuit design, among many others. Finding these densely connected regions of graphs remains an important and challenging problem. Most work has focused on scaling up existing methods to handle large graphs. These methods often partition the graph into two or more communities. In this work, we focus on the problem of hierarchical community detection (i.e., finding a hierarchy of dense community structures going from the lowest granularity to the largest) and describe an approach that runs in linear time with respect to the number of edges and thus fast and efficient for large-scale networks. The experiments demonstrate the effectiveness of the approach quantitatively. Finally, we show an application of it for visualizing large networks with hundreds of thousands of nodes/links.