Performance Trade-offs of Community Detection Algorithms in Dense and Sparse Network Topologies

Abstract

Community detection is commonly used to uncover latent group structure in complex networks, but its effectiveness is highly dependent on the topology of the graph being analyzed. An algorithm that performs well on a dense social network may not show the same behavior on a sparse collaboration network, making it difficult to select a method that generalizes across domains. This paper presents a comparative evaluation of community detection methods under two contrasting network settings: Facebook ego networks, which contain dense local social structures and ground-truth circles, and DBLP collaboration networks, which represent a sparser form of academic interaction. We evaluate a set of community detection configurations drawn from four methodological families: modularity optimization, represented by Louvain and Leiden; embedding-based clustering, represented by Node2Vec followed by HDB-SCAN; label propagation, represented by FLPA; and a hybrid Graph Neural Network (GNN) approach. The results show that no single method dominates across all evaluation dimensions. Node2Vec+HDBSCAN achieves the strongest detection quality on the tested networks, but it requires substantially higher computational cost and may leave part of the graph unassigned because of its density-based clustering mechanism. Louvain and Leiden provide more stable coverage and efficiency, making them strong practical baselines when scalability and complete partitioning are required. In contrast, the hybrid GNN model does not produce the expected improvement despite its higher computational complexity.