Community Detection and Classification in Hierarchical Stochastic Blockmodels
This work addresses the challenge of analyzing complex networks for researchers in fields like neuroscience and social science, though it appears incremental as it builds on existing stochastic blockmodel frameworks.
The authors tackled the problem of community detection and comparison in graphs by proposing a robust, scalable method that embeds graphs into Euclidean space, clusters vertices, and recursively applies these steps to identify hierarchical structure, demonstrating effectiveness in simulated data and real-world networks like the Drosophila connectome and Friendster.
We propose a robust, scalable, integrated methodology for community detection and community comparison in graphs. In our procedure, we first embed a graph into an appropriate Euclidean space to obtain a low-dimensional representation, and then cluster the vertices into communities. We next employ nonparametric graph inference techniques to identify structural similarity among these communities. These two steps are then applied recursively on the communities, allowing us to detect more fine-grained structure. We describe a hierarchical stochastic blockmodel---namely, a stochastic blockmodel with a natural hierarchical structure---and establish conditions under which our algorithm yields consistent estimates of model parameters and motifs, which we define to be stochastically similar groups of subgraphs. Finally, we demonstrate the effectiveness of our algorithm in both simulated and real data. Specifically, we address the problem of locating similar subcommunities in a partially reconstructed Drosophila connectome and in the social network Friendster.