Efficient detection of hierarchical block structures in networks

Many complex systems can be meaningfully coarse-grained into modules according to the pattern of interactions between the components or entities of the system. This coarse-graining provides a more interpretable view of the system. One such approach is to represent the system as a network and perform community detection. However, while many complex systems contain relevant information at multiple resolutions, most previous work on community detection has focused on discovering flat community structures, thus allowing information to be captured at a single resolution. Here, we circumvent this issue by developing a hierarchical community detection method to capture network structure across all resolutions.
While previous approaches exist for detecting hierarchical communities, these either rely on approximate heuristics or Markov chain Monte Carlo methods, for which convergence can be slow and difficult to diagnose. We take advantage of recently developed efficient (scaling linearly with the size of the network) spectral methods based on the regularised Laplacian and Bethe Hessian operators. These approaches provide approximate inference for the stochastic blockmodel (SBM), a popular model of network community structure in which nodes are assigned to one of k groups such that the probability of a link within and between groups can
accurately and compactly described according to a k × k mixing matrix Ω. The SBM allows us to capture a wide range of mesoscopic structures that can be assortative, disassortative, core-periphery or a combination therein.
These methods are of particular interest as they have been shown to be “optimal” by being able to detect communities right down to the theoretical limit of detectability. We extend these results and use them to develop an efficient spectral algorithm to determine if hierarchical structure exists and accurately recover it when it does. We achieve this by considering the geometry of spectral clustering in the context of hierarchically structured stochastic blockmodels. Specifically, we show that a hierarchical arrangement gives rise to a so-called
external equitable partition at each level of the hierarchy. This implies certain properties of the eigenvectors, namely that there exists a set of eigenvectors constant on each of the blocks of the partition. We can use these spectral properties to develop an efficient hierarchy detection scheme. By combining such spectral approaches with a model-based technique we can gain fast and easily implementable results. At the same time, we can still relate our results to a specific generative model and all its advantages, such as the ability to do link-prediction, obtain confidence estimates, or to generate surrogate and bootstrap samples after having obtained the model.