A paradox in community detection

Abstract

Recent research has shown that virtually all algorithms aimed at the identification of communities in networks are affected by the same main limitation: the impossibility to detect communities, even when these are well-defined, if the average value of the difference between internal and external node degrees does not exceed a strictly positive value, in literature known as detectability threshold. Here, we counterintuitively show that the value of this threshold is inversely proportional to the intrinsic quality of communities: the detection of well-defined modules is thus more difficult than the identification of ill-defined communities.

5 pages, 3 figures

References in corpus (7)

• Fast unfolding of communities in large networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• 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
• Driving interconnected networks to supercriticality

Cited by in corpus (12)

• Detecting communities using asymptotical Surprise
• Phase Transitions in Spectral Community Detection
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Universal Phase Transition in Community Detectability under a Stochastic Block Model
• Walk modularity and community structure in networks
• Decoding communities in networks
• Detectability thresholds of general modular graphs
• Exploring triad-rich substructures by graph-theoretic characterizations in complex networks
• Uncovering Complex Overlapping Pattern of Communities in Large-scale Social Networks
• Comprehensive spectral approach for community structure analysis on complex networks
• Router-level community structure of the Internet Autonomous Systems
• Detectability threshold in weighted modular networks