Improving the performance of algorithms to find communities in networks
arXiv:1311.3984 · doi:10.1103/PhysRevE.89.032809
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.
arXiv comment9 pages, 6 figures. Published version
References in corpus (23)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Fast algorithm for detecting community structure in networks
- Maps of random walks on complex networks reveal community structure
- Functional cartography of complex metabolic networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Community detection algorithms: a comparative analysis
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- 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
- Multiresolution community detection for megascale networks by information-based replica correlations
- Local resolution-limit-free Potts model for community detection
- (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