A Monte Carlo Evaluation of Weighted Community Detection Algorithms

Area of Science:

• Network Science
• Computational Neuroscience
• Data Mining

Background:

• Community detection algorithms organize nodes into modular structures.
• Existing algorithms are optimized for large, sparse matrices, with limited testing on smaller graphs or different matrix types common in brain research.
• Reliability of algorithms on smaller graph sizes and various matrix types (sparse count, correlation) remains unclear.

Purpose of the Study:

• To evaluate the performance of leading community detection algorithms across varied graph sizes and matrix types.
• To identify optimal algorithms for specific data structures in network analysis.
• To address the gap in understanding algorithm reliability for smaller graphs and weighted matrices.

Main Methods:

• A Monte Carlo simulation study was conducted.
• Tested algorithms included Newman's spectral approach, Walktrap, Fast Modularity, Louvain method, Label Propagation, and Infomap.
• Evaluated performance across different graph sizes and matrix types: sparse count, correlation, and reflected Euclidean distance.

Main Results:

• For sparse count networks (e.g., diffusion tensor imaging), Label Propagation and Walktrap were the most reliable.
• For dense, weighted networks (e.g., functional connectivity correlation matrices), Walktrap consistently outperformed other methods.
• Algorithm performance varied significantly based on graph size and matrix type.

Conclusions:

• Walktrap is a robust choice for community detection in functional connectivity data.
• Label Propagation and Walktrap are recommended for sparse count network data.
• Algorithm selection should be guided by the specific characteristics of the network data being analyzed.