Hierarchical Community Decomposition Via Oblivious Routing Techniques

The detection of communities and their structure in real-world large-scale complex networks is an important and active research topic. Numerous methods, such as, k-means and spectral cuts, have been developed to identify "best" communities. The focus of this article is on developing scalable methods for finding a hierarchical community decomposition (HCD). A common approach in the literature for finding an HCD is to apply community detection methods iteratively. We take a different approach based on a decomposition method of Racke originally designed for oblivious routing. We extend his ideas to formulate a definition of an HCD that takes a more global view of community structure. Our approach has numerous advantages. For example, our method guarantees theoretically that the returned communities have high internal connectivity but weak connectivity to the rest of the graph. Further, the hierarchical decomposition is carried out without a pre-specified number of communities or depth of decomposition. We then describe a practical implementation of Racke's method and apply it to numerous synthetic and real-world networks. We discuss a number of options, including spectral cuts and local methods, for efficiently checking a small number of cuts to decide whether the connectivity requirements are satisfied. We finish by discussing future directions including scalability in the context of hierarchical decomposition.