Detectability of hierarchical communities in networks
arXiv:2009.07525 · doi:10.1103/PhysRevE.110.034306
Abstract
We study the problem of recovering a planted hierarchy of partitions in a network. The detectability of a single planted partition has previously been analysed in detail and a phase transition has been identified below which the partition cannot be detected. Here we show that, in the hierarchical setting, there exist additional phases in which the presence of multiple consistent partitions can either help or hinder detection. Accordingly, the detectability limit for non-hierarchical partitions typically provides insufficient information about the detectability of the complete hierarchical structure, as we highlight with several constructive examples.
arXiv comment7 pages, 4 figures
References in corpus (10)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- The ground truth about metadata and community detection in networks
- The many facets of community detection in complex networks
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- Revealing consensus and dissensus between network partitions
- Hierarchical community structure in networks
- Representative community divisions of networks