Detectability of hierarchical communities in networks
This work addresses the problem of community detection in networks for researchers in network science, showing incremental insights by extending prior single-partition analyses to hierarchical settings.
The paper investigates the detectability of hierarchical community structures in networks, revealing that multiple consistent partitions can either aid or impede detection, leading to additional phases beyond the known single-partition phase transition.
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.