Hierarchical community structure in networks

  • 2020-09-15 16:18:26
  • Michael T. Schaub, Leto Peel
  • 1

Abstract

Modular and hierarchical structures are pervasive in real-world complexsystems. A great deal of effort has gone into trying to detect and study thesestructures. Important theoretical advances in the detection of modular, or"community", structures have included identifying fundamental limits ofdetectability by formally defining community structure using probabilisticgenerative models. Detecting hierarchical community structure introducesadditional challenges alongside those inherited from community detection. Herewe present a theoretical study on hierarchical community structure in networks,which has thus far not received the same rigorous attention. We address thefollowing questions: 1)~How should we define a valid hierarchy of communities?2)~How should we determine if a hierarchical structure exists in a network? and3)~how can we detect hierarchical structure efficiently? We approach thesequestions by introducing a definition of hierarchy based on the concept ofstochastic externally equitable partitions and their relation to probabilisticmodels, such as the popular stochastic block model. We enumerate the challengesinvolved in detecting hierarchies and, by studying the spectral properties ofhierarchical structure, present an efficient and principled method fordetecting them.

 

Quick Read (beta)

loading the full paper ...