A comprehensive Evaluation of Community Detection algorithms

Abstract

In many domains, including social network analysis, biology, and beyond, community structure discovery in networks is a basic topic. To find highly connected node groups—often referred to as communities—in these networks, researchers develop a wide range of techniques. While the field evolves rapidly, many comparative studies are carried out to assess the strengths and weaknesses of different algorithms on various types of networks and scenarios. This study attempts to provide a thorough comparative analysis involving both established techniques like Louvain, Label Propagation, Infomap, Girvan-Newman, and Walktrap, as well as newly proposed methods like PercoMVC, Walkscan, and Paris. This is due to the constantly changing landscape of community detection algorithms and the critical importance of understanding their strengths and weaknesses. We carry out a thorough empirical assessment of these eight community recognition methods on a variety of real-world networks, such as biological, social, and collaborative networks, among others with different topologies. A wide range of internal and external quality criteria, including conductance, density-based measurements, modularity, cut ratio, and the Friedman rank test, are incorporated into our analysis. Louvain consistently performs well on dense networks and is the best at optimizing modularity. Large, sparse networks work best with label propagation, effectively reducing the number of intercommunity links. PercoMVC shows high overall resilience and adaptability across a variety of network configurations. Infomap is good at capturing complex community structures and works well on various network types. Walktrap provides a solid balance between accuracy and efficiency and demonstrated high performance on congested networks. Our study provides insights to guide practitioners in selecting the most suitable community detection technique based on the network characteristics at hand, highlighting the complementary strengths of algorithms like Louvain and Label Propagation on dense and sparse networks respectively, and PercoMVC’s versatility.