The Computational Complexity of Hierarchical Clustering Algorithms for Community Detection: A Review

Abstract

Community detection is a highly active research area that aims to identify groups of vertices with similar properties or interests within complex real-world networks. Over the years, a large number of papers have been published, resulting in the development of various community detection algorithms that consider factors such as the type of networks, the nature of communities, and applications. Despite numerous relevant review and survey papers, the literature lacks a comprehensive analysis of the computational complexity of existing community detection algorithms. This review aims to address this gap by providing a more detailed analysis and evaluation of the computational complexity of hierarchical clustering algorithms for community detection, including two main categories: agglomerative and divisive algorithms. We also highlight the main theoretical concepts, emphasizing the benefits and drawbacks of each approach, both in theory and in practical applications. This review helps researchers and practitioners in this field better understand valuable information on the differences and unique features of community detection algorithms with hierarchical community structure.

Keywords

• Community detection
• Laplacian
• modularity
• networks
• random walks