  Modular and hierarchical community structures are pervasive in real-world
complex systems. A great deal of effort has gone into trying to detect and
study these structures. Important theoretical advances in the detection of
modular have included identifying fundamental limits of detectability by
formally defining community structure using probabilistic generative models.
Detecting hierarchical community structure introduces additional challenges
alongside those inherited from community detection. Here we present a
theoretical study on hierarchical community structure in networks, which has
thus far not received the same rigorous attention. We address the following
questions: 1) How should we define a hierarchy of communities? 2) How do we
determine if there is sufficient evidence of a hierarchical structure in a
network? and 3) How can we detect hierarchical structure efficiently? We
approach these questions by introducing a definition of hierarchy based on the
concept of stochastic externally equitable partitions and their relation to
probabilistic models, such as the popular stochastic block model. We enumerate
the challenges involved in detecting hierarchies and, by studying the spectral
properties of hierarchical structure, present an efficient and principled
method for detecting them.

Social and Information Networks;Machine Learning