Detectability of hierarchical communities in networks

Area of Science:

• Network science
• Statistical physics
• Data analysis

Background:

• Detecting single planted partitions in networks is well-understood, with a known phase transition.
• Hierarchical structures introduce complexities not captured by single partition analysis.

Purpose of the Study:

• To investigate the detectability of planted hierarchies of partitions in networks.
• To explore how multiple consistent partitions influence detection.
• To identify new phase transitions in hierarchical network structures.

Main Methods:

• Theoretical analysis of network partition models.
• Development of constructive examples to illustrate detectability limits.
• Comparison of hierarchical and non-hierarchical partition detection.

Main Results:

• Identified additional phases in hierarchical settings where multiple partitions can help or hinder detection.
• Demonstrated that single partition detectability limits are insufficient for hierarchical structures.
• Provided constructive examples showcasing these complex detectability behaviors.

Conclusions:

• The detectability of hierarchical network partitions is more nuanced than previously thought.
• Understanding these additional phases is crucial for accurate network analysis.
• Future research should focus on the interplay of multiple partitions in complex networks.