Improving the performance of algorithms to find communities in networks

Abstract

Many algorithms to detect communities in networks typically work without any information on the cluster structure to be found, as one has no a priori knowledge of it, in general. Not surprisingly, knowing some features of the unknown partition could help its identification, yielding an improvement of the performance of the method. Here we show that, if the number of clusters were known beforehand, standard methods, like modularity optimization, would considerably gain in accuracy, mitigating the severe resolution bias that undermines the reliability of the results of the original unconstrained version. The number of clusters can be inferred from the spectra of the recently introduced non-backtracking and flow matrices, even in benchmark graphs with realistic community structure. The limit of such two-step procedure is the overhead of the computation of the spectra.

9 pages, 6 figures. Published version

References in corpus (13)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Detecting the overlapping and hierarchical community structure of complex networks
• Finding statistically significant communities in networks
• Spectral redemption: clustering sparse networks
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• (Un)detectable cluster structure in sparse networks
• Stochastic fluctuations and the detectability limit of network communities

Cited by in corpus (9)

• Community detection in networks: A user guide
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Finding communities in sparse networks
• Comparative analysis on the selection of number of clusters in community detection
• An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
• Eigenvector dynamics under perturbation of modular networks
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Consistency between ordering and clustering methods for graphs
• Router-level community structure of the Internet Autonomous Systems